Arithmetic
How a binary adder works
Computers add the way you learned at school: one column at a time, carrying into the next. The only difference is that each column holds a 0 or a 1, which makes the rules short enough to build out of gates.
Counting in binary
In decimal each column is worth ten times the one to its right: ones, tens, hundreds. In binary each column is worth twice the one to its right: 1, 2, 4, 8, 16 and so on. The number 13 is 8 + 4 + 1, so it is written 1101. Eight bits make a byte, which can hold any whole number from 0 to 255.
Adding on paper
Binary addition has only four facts to learn: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10, which means “write 0, carry 1”. When a carry arrives at a column that already holds two 1s, you get 1 + 1 + 1 = 11: write 1, carry 1. That is the whole algorithm. Try it below by clicking the bits of A and B.
The half adder: one column, two bits
The simplest adding circuit handles one column with no carry coming in. It takes two bits and produces a two-bit answer: a sum bit for this column and a carry bit for the next.
| A | B | CARRY | SUM |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Look at the two output columns on their own. Each one is a truth table you may have seen before, perhaps on the logic gates page. Recognising which gates they are is half of building a half adder. The other half is a puzzle in the game, so we will leave it there.
The full adder: one column, three bits
Every column except the rightmost may receive a carry, so a real column adds three bits: A, B and the carry-in. The answer is still at most 3 (11 in binary), so two output bits are still enough.
| A | B | Cin | Cout | SUM |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Two patterns are worth noticing. SUM is 1 when an odd number of the inputs are 1. Cout is 1 when at least two of them are, a majority vote. A full adder is a small, very well-studied circuit, and the smallest NAND-only version is a classic optimisation target.
Ripple carry: chaining the columns
Put eight full adders side by side, connect each one’s carry-out to the next one’s carry-in, and you have an 8-bit adder. This is a ripple-carry adder, and it is exactly the paper method in hardware.
It is simple and small, but it has a catch. The top column cannot settle on its answer until the carry from the column below has arrived, and that one waits for the column below it, and so on. In the worst case, such as adding 1 to 11111111, a carry has to travel through every column in turn. The delay grows in step with the number of bits, so a 64-bit ripple adder is eight times slower than an 8-bit one.
Faster adders
Because nearly everything a CPU does involves adding (addresses, loop counters, comparisons), designers have worked hard on that carry chain. Carry-lookahead, carry-select and prefix adders (Kogge–Stone, Brent–Kung and others) spend more gates to work out many carries at once, so the delay grows roughly with the logarithm of the width instead of the width itself. That is the classic trade of area for speed, and it is one of the optional challenges in the game.
Overflow and carry out
Eight bits can hold 0 to 255. Add 200 and 100 and the true answer, 300, needs nine bits. An 8-bit adder keeps the low eight bits (300 − 256 = 44) and raises its carry out, which CPUs record in a carry flag so programs can chain additions across several words. For signed numbers the warning sign is different, because there the problem is crossing from the largest positive value to the most negative. Two’s complement explains why the same adder works for negative numbers too, which is why CPUs have no separate subtraction circuit for signed numbers.