Adding

Numbers in binary treated the adder as a box: two bytes go in, a byte comes out, along with a carry and an overflow. This page opens the box and builds it from the gates of Switches and gates, with the same colours: orange is 1, grey is 0. Then it asks how fast it is, which turns out to be the more interesting question.

1 · Adding by hand, in binary

Binary adding works just like adding in decimal with pencil and paper: line the numbers up, add one column at a time from the right, and when a column comes to more than one digit can hold, write down the last digit and carry the rest into the next column. The only difference is how soon that happens. In binary, 1 + 1 is already too much for one digit: it’s 2, which is 10, so write 0 and carry 1. With a carry coming in as well, a column can reach 1 + 1 + 1 = 3, which is 11: write 1, carry 1.

Click Next column to add one column at a time, right to left, as on paper; the carries appear above. The example is 7 + 3: three columns in a row make a carry. Click the bits for your own, or New sum for a random one.

Every column does the same small job: take three bits (a digit from each number, and the carry coming in), and make two (a digit of the answer, and a carry going out). Build a circuit for that job once, and an adder of any size is just copies of it.

2 · The half adder

Start with the rightmost column, where no carry comes in: two bits in, a sum digit and a carry out. Its truth table has four rows, and both outputs are gates from the first page. The sum is 1 when exactly one input is 1: that’s XOR. The carry is 1 only when both are: that’s AND.

Click A and B. Two gates add two bits. Read the outputs together, carry then sum, and they’re the answer as a two-bit binary number: 1 + 1 = 10.

It’s called a half adder because it can only do half the job: there’s nowhere for a carry to come in.

3 · The full adder

A full adder takes three bits, A, B and a carry in, and it can be built from two half adders. The first adds A and B. The second adds that sum to the carry in, and its sum is the full adder’s sum. Either half adder might make a carry, so an OR gate joins them into the carry out. (They can never both make one: if the first carries, its sum is 0, and then the second has nothing to carry.)

Click the three inputs and follow them through: five gates in all. Read carry out and sum together again, and they count how many of the three inputs are 1, from 00 to 11.

4 · A ripple-carry adder

Now put full adders side by side, one per column, and connect each one’s carry out to the next one’s carry in, just as the carries on paper move one column left. The first column has no carry coming in, so its carry in is fixed at 0. That’s a ripple-carry adder: for 8 bits, eight full adders, 40 gates.

Four full adders (each box is the circuit from section 3), adding a (a3 to a0) and b, with the least significant column on the right. Click the bits. 5 + 3 sends a carry along three columns; 15 + 1 sends one all the way out of the top. That last carry is the carry out, which a processor keeps as its carry flag.

5 · Why it’s slow

Nothing in a circuit happens instantly. Each gate takes a moment to switch: its transistors have to charge or drain the wires it drives. Call that time one gate delay. A full adder’s sum is ready 2 gate delays after its inputs change (two XORs), and its carry out after 3.

The trouble is the chain. Column 1 can’t finish until column 0’s carry has arrived, column 2 has to wait for column 1’s, and so on: the carry ripples along, 2 gate delays per column (an AND, then an OR). The worst case is a carry made in the first column that has to travel the whole way, like 1111 1111 + 1.

Each row is one output over time, in gate delays from when the inputs change: orange is 1. Under it is the number the outputs make at each moment, in red while it’s wrong. From 0 + 0 to 1111 1111 + 1, the carry climbs a staircase and the adder settles after 16 gate delays. With 0111 1111 + 1, the sum reads as several wrong numbers on the way to 128. With 0101 0101 + 1010 1010, no column makes a carry, and it’s done after 2. Click the bits to make your own change; it’s timed from the numbers before.

Those wrong values on the way are glitches, and every circuit has them: its outputs are only right once everything has settled. A processor deals with this by waiting. Its clock ticks only as often as its slowest path can settle, so the adder’s worst case sets a limit on the clock speed.

The ripple adder’s worst case grows with its width: 16 gate delays for 8 bits, and 128 for 64. For scale: an Intel Core i7-6700K, a desktop processor from 2015 running at 4 GHz, has a quarter of a nanosecond per clock cycle, and adds two 64-bit numbers within a single cycle. A carry rippling through 128 gate delays would never fit; fast processors don’t add this way.

6 · Subtracting with the same adder

Numbers in binary showed how to make a number negative: flip every bit and add 1. So a − b is a + (b flipped) + 1, and an adder can subtract with two small changes.

Flipping b: an XOR gate flips one input exactly when the other is 1, and passes it straight through when it’s 0. So put an XOR on each bit of b, with their other inputs joined to one control line, sub.
Adding 1: the first column’s carry in, fixed at 0 until now, is exactly where an extra 1 can go. Connect it to sub too.

With sub at 0, b passes through and nothing is added: the circuit adds. With sub at 1, it subtracts.

Click sub to switch between adding and subtracting, and the bits to change a and b. 6 − 2 = 4. Now try 2 − 6: as unsigned numbers it can’t be done (there’s no −4), and the carry out is 0; as signed numbers the answer, −4, is right. Subtracting, a carry out of 1 means “no borrow was needed”. Try 7 − (−1) for an overflow.

The carry out works backwards when subtracting: 1 when a ≥ b (as unsigned numbers), 0 when the answer had to “borrow”. The 6502 uses exactly this circuit. Its subtract instruction, SBC, feeds the carry flag in as the extra 1, which is why 6502 programs set the carry (SEC) just before subtracting, and clear it (CLC) before adding.

Overflow is easy to spot too: a signed result is wrong exactly when the carry into the top column differs from the carry out of it. That’s one more XOR gate.

7 · Carry look-ahead

The ripple adder is slow because each column waits to hear about the carry from the column before. But each column can say in advance what it will do with a carry, from its own two bits alone:

If both bits are 1, it generates a carry, whatever comes in: g = a·b.
If exactly one is 1, it propagates one: a carry that comes in goes straight out. p = a ⊕ b.
If both are 0, it stops any carry.

So the carry into column 2 is “column 1 generates one, or column 1 propagates one that column 0 generated, or both propagate the carry in”. As a formula, that’s a sum of products, as in Combining gates:

c_2 = g_1 + p_1 \cdot g_0 + p_1 \cdot p_0 \cdot c_0

Every carry can be written the same way, straight from the inputs, and a sum of products is just an AND level and an OR level. So a carry look-ahead adder works out all the carries at once: a gate delay for g and p, two for the carries, and one for the sums. Four gate delays, however wide it is.

The same changes as before, timed in a ripple-carry adder and a carry look-ahead adder. For 1111 1111 + 1, ripple settles after 16 gate delays and look-ahead after 4. Look-ahead takes no longer than 4 for any change.

Nothing is free. This 8-bit look-ahead adder uses 68 gates against the ripple adder’s 40, and the carry into the top column needs an AND gate with 9 inputs. Wider still, the gates get impossibly wide. So real designs look ahead over small groups, four columns at a time, and then look ahead over the groups. A tree of these makes the delay grow with the logarithm of the width: doubling the width adds a step, not double the time. The fastest adders, prefix adders such as Kogge and Stone’s (1973), are a tidy version of that tree, and adders like that are what lets a 64-bit addition fit in a quarter of a nanosecond.

Summary

Adding in binary is column addition: 1 + 1 = 10, write 0 and carry 1.
A half adder adds two bits: XOR for the sum, AND for the carry. A full adder adds three (with a carry in), from two half adders and an OR.
A ripple-carry adder chains full adders, each carry out into the next carry in. It’s small, but slow: the carry crosses the columns one at a time, 2 gate delays each, so the worst case grows with the width.
Outputs glitch before they settle; a processor’s clock waits for its slowest path.
The same adder subtracts: XOR gates flip b, and the carry in adds the 1. Overflow is the carry into the top column differing from the carry out.
Carry look-ahead works out every carry at once from generate (a·b) and propagate (a ⊕ b): constant delay, at the cost of more, wider gates; real adders use a tree of them.