Perform binary addition showing carries, and explain overflow when a result exceeds the fixed width of a register

What this dot point is asking

SEAB wants you to add binary numbers by hand, showing the carries, and to explain overflow: what happens when an addition produces a result that does not fit in the fixed number of bits the register has. The central idea is that binary addition works exactly like denary addition, but you carry whenever a column reaches the base, which in binary is $2$.

The answer

The four addition rules

Adding two bits (plus any carry coming in) follows four simple cases:

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

The last case happens when there is also a carry into the column.

Adding column by column

Start at the rightmost column (the least significant bit) and work left. Add the two digits and any incoming carry, write the result digit, and pass any carry to the next column:

  carries:   1 1 0
             0 1 0 1
           + 0 0 1 1
           ---------
             1 0 0 0

Here $0101_2 = 5$ and $0011_2 = 3$, and $1000_2 = 8$, which checks.

Checking with denary

Always confirm a binary addition by converting both numbers and the result to denary. If $a + b$ in denary does not equal the denary value of your binary result, you have dropped a carry somewhere.

Fixed-width registers

A register stores a fixed number of bits, often $8$. An unsigned 8-bit register can hold the values $0$ to $255$, because $2^8 = 256$ patterns. The largest unsigned value is $2^n - 1$ for $n$ bits.

Overflow

Overflow happens when an addition produces a carry out of the most significant bit, because the result needs more bits than the register has. The extra bit is lost, so the stored answer is wrong. You detect overflow by checking for a carry out of the top column, or by checking whether the true result exceeds $2^n - 1$.

Examples in context

Example 1. A counter wrapping round. An 8-bit counter that reads $255 = 11111111_2$ and is told to add $1$ overflows: the carry ripples out of the top bit and the counter wraps to $00000000_2 = 0$. This is why an odometer or a game score can suddenly reset to zero.

Example 2. Adding bytes in a program. When two byte values are added in low-level code, the programmer must know the register width. If two large bytes are added without room for the carry, the result silently wraps, causing a bug that a denary check during testing would reveal.

Try this

Q1. Add $00001111_2$ and $00000001_2$ and give the 8-bit result. [2 marks]

• Cue. $15 + 1 = 16 = 00010000_2$; the run of ones rolls over with carries to set the next bit.

Q2. State the largest value an unsigned 8-bit register can hold, and why. [2 marks]

• Cue. $255$, because $8$ bits give $2^8 = 256$ patterns, from $0$ to $255$.

Q3. Add $10000000_2$ and $10000000_2$ in an 8-bit register and explain the result. [3 marks]

• Cue. $128 + 128 = 256$, which needs $9$ bits; the carry out of the top bit is lost, so the register stores $00000000_2 = 0$, an overflow.