06Building the Adder

Chapter 5 ended on a promise I now have to keep. The adder is built out of gates you already own. You've owned every one of them since Chapter 2 — the AND, the OR, the NOT, the NAND, the NOR, the XOR. Two of those six were doing arithmetic the whole time, and nobody told you. This is the chapter where you find out which two, and why. It's one of my favourites in the book, because it's the exact seam where logic turns into math. We'll start as small as it gets: adding a single 1 to a single 1, and watching two output bits fall out — a sum and a carry. Then comes the jolt. I'm not going to hand you that one; you're going to catch it. All I'll promise is this: it isn't a coincidence you have to memorize. It's a thing you can see. And once you see it, the addition table stops being arithmetic you were taught and becomes a circuit you can wire. From there we climb one honest rung at a time. A half adder from those two gates. A full adder that can accept a carry coming in. Eight of them chained into a real 8-bit adder — the arithmetic spine of every processor ever shipped. Then, in one tight closing move, a single control wire that makes the very same block subtract on command. That last block has a name you've heard: the ALU. There's no magic anywhere in it — just gates settling into the answer we cornered them into giving.

01When gates became arithmetic

Let's start with the smallest addition there is. Take two single bits — call them A and B — and add them the way grade school taught you, one column at a time. Three of the four cases are boring: 0+0 is 0, 0+1 is 1, 1+0 is 1. It's the fourth that's interesting, and it's the one binary forces on us early: 1+1. In our two-symbol world there's no digit "2" to write. So the column rolls over: you write 0 and carry a 1 to the next column up. That's exactly the roll-over you watched on the binary odometer in Chapter 4. So here's the honest truth. Adding two bits doesn't produce one bit — it produces two: a sum bit for this column and a carry bit for the next. Toggle A and B below and watch both outputs.

Now stare at just the sum column of that table — the low bit, ignoring the carry for a second. It reads: 0, 1, 1, 0. Don't let me name it yet. You walked out of Chapter 2 owning six gates, and one of them already produces that exact column from those exact inputs. Go and find it before you read on. Here's your only clue: the sum is 1 exactly when the two inputs disagree, and 0 when they match. Got it? It's XOR. "Output 1 only when the inputs differ" was XOR's whole personality, and that personality is the sum of two bits. Not a resemblance. The same four rows, in the same order, letter for letter. Here's XOR again below — read its output column, then look back at the sum column, and watch them turn out to be one column printed twice.

Now do the same with the carry column — the high bit that only fires on the last row. It reads: 0, 0, 0, 1. A carry happens in exactly one case: when both inputs are 1, and never otherwise. That's the most demanding gate in the family, the one that insists on both: the AND gate, also straight from Chapter 2. So the carry of a one-bit addition is simply A AND B. Here's AND again — check its single lit row against the carry column above.

Sit with what just happened, because it's the hinge of the whole chapter. We didn't design a circuit to add two bits. We noticed that a circuit we already had, wired the obvious way, was the addition. The sum is XOR. The carry is AND. Feed the same two inputs into both gates at once, and you get both output bits in a single settling step. That little two-gate assembly has a name — the half adder — and it is the atom of all arithmetic in the machine. Toggle the inputs below. Watch the sum lamp (XOR) and the carry lamp (AND) light independently, together giving you the two-bit answer to A+B.

02The full adder: room for a carry

The half adder is beautiful, and it is also not quite enough. I want you to run into its limitation yourself rather than take my word for it. Think about adding two multi-bit numbers — say two bytes — the way you add long numbers by hand: column by column, right to left. The rightmost column has just two bits to add, so a half adder handles it fine. But look at the second column. It has three things to add: its own two bits plus the carry that came in from the column to its right. A half adder has only two inputs. It has nowhere to put that incoming carry. Below, try to feed three bits into a two-input adder and watch it come up a wire short.

So we need a slightly bigger part: one that adds three input bits — A, B, and a carry-in we'll call Cin — and still produces a sum and a carry-out. This is the full adder. The good news is that we build it almost entirely out of the half adder we just made. Take the sum first. But here's a snag worth stopping on. You learned XOR as "the inputs differ", and "differ" is a question you can only ask of two things. Three bits don't differ. So go back to XOR's four rows and count this time, instead of comparing. The two rows that light have exactly one input at 1. The two dark rows have zero ones and two ones. So "differ" was never the real rule. It was a two-input disguise for a bigger one: an odd number of my inputs are 1. That property has a name — parity — and unlike "differ", it doesn't care how many bits you hand it. Now the extension is free. When you add three bits, the sum is 1 whenever an odd number of them are 1. And you get that by asking the parity question twice: S = A ⊕ B ⊕ Cin. First XOR the two data bits, then XOR the carry-in into that result.

And one more turn, because "the sum is the parity" shouldn't be a thing you take on my word. Ask what a column of three bits actually hands you. It hands you a count — how many of the three are 1 — and that count can only be 0, 1, 2 or 3. Write those four in binary: 00, 01, 10, 11. The digit you write down in the column is the low bit of that count. The carry is the high bit. So read the low bits of 0, 1, 2, 3 in order: 0, 1, 0, 1. That is precisely whether the count is odd. So the sum digit is the parity — not by resemblance, but because that is what a low bit means. XOR was never imitating addition. It was counting all along. Toggle all three inputs below and watch the sum track the parity.

Now for the piece the source I learned from quietly skipped. It built the sum, then cut away before finishing the carry-out. Let's actually complete it, because it's not hard and you deserve the whole part. When does adding three bits carry to the next column? Whenever at least two of them are 1 — that's a majority vote. So let's not wave at the cases; let's name every row where it happens. With three bits there are exactly four: (0,1,1), (1,0,1), (1,1,0) and (1,1,1). Now watch them split. Two of those rows have both data bits at 1 — (1,1,0) and (1,1,1) — and Cin makes no difference in either. That's A AND B, the half adder's own carry. The other two — (0,1,1) and (1,0,1) — are the rows where the data bits disagree, so their XOR is 1, and the carry-in is what tips the balance. That's (A⊕B) AND Cin. Count them off: four rows, two terms, every row caught once and no row caught twice. The two cases can't both fire, and together they cover every carry there is. So OR them and you're done — not on trust, on bookkeeping: Cout = A·B + (A⊕B)·Cin. Notice that we reuse the sum's XOR — nothing wasted. Build the carry-out gate live below.

That's the complete full adder: three inputs, two outputs, all of it made from two XORs, two ANDs, and one OR. Every one of those you built from transistors back in Chapter 2. Before we trust it, let's do the honest thing and check it against every possible input, not just the ones I'd cherry-pick. Three inputs means 2³ = eight rows — few enough to walk in full. Step through all eight below. Confirm that on every single row, the two output bits spell the correct count of ones among the inputs: 0 through 3, in binary, as Cout and S.

Now the move that makes everything above scale. It's a habit of mind more than a circuit. We've verified the full adder does exactly what it claims on all eight inputs. So we're allowed to stop looking inside it. We seal the whole tangle of XORs and ANDs and the OR behind a single labelled box — three pins in (A, B, Cin), two pins out (S, Cout). From here on we draw that box and never reopen it. This is abstraction, or black-boxing. Once a circuit's behaviour is trusted, its structure stops mattering. You get to build on top of the promise instead of the parts. It's the same license that let us treat a gate as a symbol instead of four transistors. Flip between the guts and the box below.

03Ripple-carry: eight in a chain

Here's the payoff of building the full adder with a carry-in: the parts now snap together like train cars. Take two of our black-boxed full adders. Wire the carry-out of the one handling the low bit straight into the carry-in of the one handling the next bit up. That's the whole trick. The carry that "rolls over" from column to column in hand arithmetic is now a literal wire running from one adder to the next. Set the two low bits of each number below and watch a carry born in the first adder travel into the second.

Do that eight times and you have the 8-bit adder. Eight full adders in a row — the same little atom, chained. Each one takes one bit of A and the matching bit of B. Each one's carry-out feeds the next one's carry-in, with the very first carry-in tied to 0. Feed it two whole bytes and it hands you their sum, one settling wave later. This is the arithmetic spine of every processor you have ever used, and there is nothing inside it that wasn't in that first pair of gates. Set A and B below, then watch the carry ripple left. That visible wavefront threading through the adders is the reason this design has a name: ripple-carry.

That ripple is gorgeous to watch, and it is also the design's one real weakness. So let's be honest about it. The source waved at "settling time," but there's a precise cost here worth naming. Each full adder cannot compute its carry-out until its carry-in has arrived and settled. So the top adder is waiting on the seventh, which is waiting on the sixth, all the way down. The carry has to physically walk the entire chain, one adder's propagation delay at a time, before the highest sum bit is trustworthy. Add more bits, and the worst-case delay grows in a straight line with the width. It's a row of dominoes: the last one can't fall until every one before it has. Watch the wave march below.

Engineers hated waiting on that walk, so they invented a way around it. It's worth knowing the name, even though we won't build it in full: carry-lookahead. First, a unit to count in. One gate delay — written Δ — is simply the time a single gate takes to settle after its inputs change. That's the currency. A ripple stage costs about 2Δ, so four bits of ripple is 8Δ before the top sum bit can be trusted. Now the insight: you don't actually have to wait for a carry to arrive to know whether it will arrive. Each column either generates a carry on its own — both bits 1, which we write g = A·B — or propagates one that reaches it, meaning the bits disagree, written p = A⊕B. Both depend only on the input bits, and the input bits are all sitting there at once. So a lookahead unit computes every column's carry in parallel with extra gates instead of threading them one by one, and they all settle together at about 3Δ. Eight against three: you trade more hardware for far less delay — the classic engineering bargain. The trick works at any width — the wide ones nest lookahead units inside lookahead units — so we'll watch it on four bits, where every column fits on screen, and then go back to all eight. Compare the two schemes side by side below.

Ripple or lookahead, though, the behaviour is identical: same two bytes in, same sum out. And that means we get to do the black-box move one more time, at a bigger scale. The whole eight-adder chain, carries and all, collapses into a single rectangle: two 8-bit inputs, one 8-bit output, one carry-out off the top. We'll draw it as ADD and never again worry which of the two internal schemes is wired inside. That trusted rectangle is now a component — the piece we'll drop into the processor a few chapters from now without a second thought. Collapse the chain into the block below.

One more look at that rectangle before we use it, because what it doesn't know is the reason the next move is free. The ADD block has no idea what your bits mean. Hand it 1111 1111 and 0000 0001 and it hands back 0000 0000 with the top carry-out lit — and it does that whether you were thinking 255 + 1, or thinking −1 + 1. Same eight wires, same eight voltages, same dumb column-add. Nothing in the copper tells those two stories apart. Two's complement, back in Chapter 5, never changed a single bit; it changed how you read them. Signedness is a convention living in your head, not a signal the machine can sense. That also settles something you may have started nagging at. At the 8-bit adder I made a fuss of the top carry-out: light it and the unsigned sum didn't fit in eight bits. In a moment you'll watch a subtraction throw that same bit away. Both are true, and the pin never budges. It answers one question — did the column-add run off the end of the byte? — and you decide what that answer is worth. Read the byte as unsigned and running off the end is overflow. Read it on Chapter 5's wheel and running off the end is one full lap, worth exactly 0. One pin, one behaviour, two readings, because you brought two conventions.

04Subtraction for free — the ALU

We built an adder. We are about to get a subtractor without building anything that deserves the name. This is where Chapter 5 comes back to collect. Recall the prize from last chapter: subtraction was defined away. A − B is just A + (−B). And in two's complement, you make −B by inverting every bit of B and adding one. Our adder already does the "+". All we need is a way to hand it an inverted B and an extra 1. Here's that idea again — subtraction riding the same adder — before we wire it into hardware.

So how do we invert B — but only sometimes, on command — so the block can add when we want and subtract when we want? The answer is a gate we've been underusing. Look hard at XOR with one input tied to a control line C. When C is 0, B ⊕ 0 = B — the bit passes through untouched. When C is 1, B ⊕ 1 = NOT B — the bit comes out flipped. So a single XOR is a controlled inverter: a NOT gate with a switch on it. Toggle the control line below and watch one XOR either wave the bit through or flip it.

So the invert is handled. Eight of those XORs, one on each B line, and every bit of B flips the moment you say so. But read what two's complement actually asked for: invert and add one. So where is that +1 coming from? Not a second adder — refusing to build one is the whole point. Not a new gate either; adding 1 to an eight-bit number is precisely the job we just spent a chapter on. Sit in that for a second before you scroll on. Everything you need is already on the page, and has been for a while. Play with the control line below, and while you do, go looking for it.

Found it? It's the one pin in this whole machine that we tied off and never used again. When we chained eight full adders, we grounded the lowest carry-in, because in ordinary addition nothing carries into the ones column. But grounding it was a choice, not a weld. It's an input like any other, and look where it sits: the ones column, place value 2⁰. So driving it to 1 adds exactly one to the total — not two, not eight, one — and it costs no gate at all. The cheapest +1 in the building. Now watch the whole thing close in one move, and notice that it's a single wire, not a second machine. Put one controlled inverter on each of the eight B lines. Then run one control wire — call it the add/subtract line — to every one of those XORs and to that forgotten carry-in at the same time. Set that line to 0, and B passes straight through, carry-in is 0, and the block adds. Set it to 1, and every bit of B inverts and the carry-in becomes the "+1". That's exactly invert-and-add-one, exactly −B, so the block subtracts. One toggle, eight XORs, and the adder you already trusted now does both. Flip it below.

Give that block its real name. An adder that also subtracts on command — an 8-bit datapath that performs an arithmetic operation you select — is the germ of the ALU, the arithmetic logic unit, the calculating core at the centre of every CPU. Ours does two operations so far, add and subtract, chosen by one line. One thing to settle before we seal it, because this one catches working engineers for years. Subtract 5 from 7 and the top carry-out lights up. Subtract 7 from 5 and it stays dark. Read that the natural way round and you'd say the lamp means "it borrowed" — and you'd have it exactly backwards. A lit carry-out means the subtraction never needed to borrow: A was at least as big as B. Dark means it did. Same pin, same behaviour it has always had; only the question you're asking of it changed. A real ALU stacks a few more operations — the bitwise AND, OR, XOR of Chapter 18 hang off the very same operand lines — and widens the selector to pick among them. But the shape is already here: operands in, an op-select in, one result out. Black-box it, label it ALU, and meet the last component we'll build before the machine starts to remember. Explore it below.

One claim this big shouldn't rest on the handful of examples I chose to show you. So let's check it the honest way: exhaustively, in code. Here's a full adder written as pure gate logic — literally XOR, AND, and OR on single bits. It's composed eight times into a ripple-carry adder, then run against the language's own + for a spread of byte pairs, with the results diffed. Not "usually" right: bit-for-bit identical, because the gates are the arithmetic. Read it and run it below.

# a FULL ADDER — three logic gates on single bits (0 or 1)
def full_adder(a, b, cin):
    s    = a ^ b ^ cin                 # XOR  → sum bit
    cout = (a & b) | (cin & (a ^ b))   # AND,AND,OR → carry
    return s, cout

# chain 8 of them; the carry ripples low → high
def ripple_add(A, B):                  # A, B are bytes 0..255
    carry, out = 0, 0
    for i in range(8):
        a, b = (A >> i) & 1, (B >> i) & 1
        s, carry = full_adder(a, b, carry)
        out |= s << i
    return out | (carry << 8)          # 9th bit = final carry

# the whole point — no math, just gates:
for A in range(256):
    for B in range(256):
        assert ripple_add(A, B) == A + B

And that's Chapter 6 — a working ALU, built from nothing but the gates of Chapter 2 and the number sense of Chapters 4 and 5. The whole climb was one idea, reused. The sum of two bits is XOR and their carry is AND, so a half adder is two gates. A full adder adds a carry-in, so the parts chain. Eight chained is an 8-bit adder, its ripple-carry paid for in propagation delay. And one add/subtract line through eight controlled inverters buys subtraction for free. At every step we black-boxed what we trusted and built on the promise. Here's a caveat to carry forward, honestly: this machine does whole numbers only. There are no fractions on these wires, no decimal point anywhere in the byte. Making one is a whole separate story the machine doesn't tell for a long time. But here's the deeper problem, the one that opens the next chapter. You've built a calculator that answers the instant you set its inputs — and that's exactly the trouble. Touch an input and the old answer vanishes. The sum lives only while you hold the operands still. To reuse a result — to feed today's sum into tomorrow's addition — you have to make the machine hold a value on its own. And pure gates, which only ever react, cannot. For that we need something that can remember. Memory, it turns out, is what you get when you do the one thing we've carefully never done: bend a wire back on itself.