Skip to main content
Be Bitwise

Binary Arithmetic

Binary & Number Systems · Foundations track

5 min read

Part ofSystems Programming Companion, week 2

In this module

Arithmetic in Binary

You already know how to add numbers in decimal. Binary arithmetic plays by the same rules. There are just fewer digits to juggle. Once the pattern clicks, it becomes second nature.

Binary Addition

In decimal, if you add two digits and the result is 10 or more, you write down the ones digit and carry 1 to the next column. Binary works identically. The threshold is 2 instead of 10.

The complete addition table for single bits:

  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 = 10 (write 0, carry 1)

Walk through adding 0011 (3) and 0101 (5):

text
0011 (3)
+ 0101 (5)
------
1000 (8)

Starting from the right: 1 + 1 = 10, write 0, carry 1. Next column: 1 + 0 + 1(carry) = 10, write 0, carry 1. Next: 0 + 1 + 1(carry) = 10, write 0, carry 1. Finally: 0 + 0 + 1(carry) = 1. Result: 1000, which is 8.

Key Concept

Binary addition works just like decimal addition. The only difference is that you carry when a column sums to 2 or more, instead of 10 or more.

Binary Subtraction

Subtraction mirrors decimal too. When the top digit is smaller than the bottom digit, you borrow from the next column. In binary, borrowing turns a 1 in the next column into 0 and adds 10 (which is 2 in decimal) to the current column.

Subtract 0010 (2) from 0101 (5):

text
0101 (5)
- 0010 (2)
------
0011 (3)

Right column: 1 - 0 = 1. Next column: 0 - 1. Can't do that, so we borrow from the next column. That gives us 10 - 1 = 1, and the column we borrowed from drops from 1 to 0. The remaining columns: 0 - 0 = 0. Result: 0011, which is 3.

Shifting: Multiplying and Dividing by Two

In decimal, sticking a zero on the end of a number multiplies it by ten. In binary, it multiplies by two. Shift 0101 (5) one place left and you get 1010 (10). Shift it two places and you get 10100 (20). Shifting right does the reverse, halving and dropping any remainder: 1011 (11) shifted right once is 0101 (5).

CPUs have dedicated shift instructions, and they're about as cheap as an instruction gets. Compilers know this, so x * 8 in your C code often turns up in the assembly as a left shift by 3.

Try it on the puzzle below. You start at 11 (00001011) and need to reach 20 (00010100) using only SHL and SHR, in two moves. Type the shift amount in the operand box before you press apply, and watch which bits fall off the right-hand end.

Bit Manipulation Puzzle

2 steps left
Current
0
0
0
0
1
0
1
1
110x0B
Target
0
0
0
1
0
1
0
0
200x14

Overflow

Every computer works with a fixed number of bits. When an addition result needs more bits than are available, the extra bit gets lost. We call this overflow.

Add 1111 (15) and 0001 (1) in a 4-bit system:

text
1111 (15)
+ 0001 (1)
------
10000 (16)

The result wants 5 bits, but we've only got 4. The leading 1 falls off the end, and the stored result is 0000. Zero. The value has "wrapped around."

Key Concept

Overflow happens when an arithmetic result exceeds the bit width of the system. The extra bits are silently dropped, which can produce wildly incorrect results. Understanding overflow matters for writing correct low-level code.

Overflow is a baked-in consequence of fixed-width arithmetic, and the hardware is behaving exactly as designed when it happens. Programmers have to plan around it, and CPUs raise special flags when it occurs so software can spot and handle it.

Worked Example: Two Flags for Two Kinds of Overflow

The adder in a CPU doesn't know whether the bits it's adding are meant as unsigned or signed numbers. So it reports on both, working out two separate flags from the same addition at the same moment. On x86 they're called CF (carry flag) and OF (overflow flag).

  • CF is set when the result doesn't fit as an unsigned number: a carry fell off the top.
  • OF is set when the result doesn't fit as a signed number: two positives made a negative, or two negatives made a positive.

Here are two 8-bit additions that look similar and behave very differently:

BitsAs unsignedAs signedStored resultCFOF
11001000 + 01100100200 + 100 = 300−56 + 100 = 4400101100 (44)10
01100100 + 01100100100 + 100 = 200100 + 100 = 20011001000 (200, or −56 signed)01

In the first row a carry falls off the top, so unsigned 300 becomes 44, but read as signed numbers the answer 44 is exactly right. In the second row nothing falls off and unsigned 200 is correct, but two positive signed numbers produced a pattern whose top bit is set, which signed code would read as −56.

The compiler picks which flag to test based on the types in your code: unsigned comparisons use the carry flag, signed ones use the overflow and sign flags. That's how the same add instruction serves both kinds of number.

Predict: in 4 bits, 0111 + 0001. Which flags get set?

OF only. The result is 1000. As unsigned numbers, 7 + 1 = 8, which fits in 4 bits, so no carry. As signed numbers, 7 + 1 should be 8 but 1000 reads as −8, so the signed result is wrong and OF is set.