Every add, sub, cmp and inc the CPU executes goes through the ALU, the arithmetic logic unit, and at the heart of the ALU is an adder. This chapter builds one from the gates of the previous chapter, then grows it into an ALU that also produces the flags the assembly level reads.
Adding two bits: the half adder
Adding two 1-bit numbers gives a result from 0 to 2, so it needs two output bits: a sum and a carry. Their truth tables are two gates you already know:
- Sum = A XOR B (1 when exactly one input is 1);
- Carry = A AND B (1 only for 1 + 1).
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Adds two bits: Sum = A XOR B, Carry = A AND B. The two outputs read together as a 2-bit number, A + B.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
It's called a half adder because it can't accept a carry coming in from a lower bit.
Adding three bits: the full adder
In the middle of a multi-bit addition, each column adds three bits: A, B and the carry in from the column to its right. A full adder does that, and it's built from two half adders and an OR:
| A | B | Cin | Sum | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Two half adders plus an OR: Sum = A ⊕ B ⊕ Cin, Cout = AB + (A ⊕ B)·Cin. It adds three bits, so full adders chain: each one's Cout is the next one's Cin.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
- Sum = A ⊕ B ⊕ Cin: 1 when an odd number of inputs are 1.
- Carry out = AB + (A ⊕ B)·Cin: 1 when at least two inputs are 1. That's the majority function from the previous chapter, in another form.
Adding numbers: the ripple-carry adder
Chain n full adders, each one's carry out feeding the next one's carry in, and you can add two n-bit numbers. The carry into bit 0 is normally 0:
Four full adders, the carry rippling from bit 0 (top) to bit 3. Each stage adds two gate delays to the carry path, so the worst case (e.g. 1111 + 0001) takes about 2n gate delays: step through it to watch the carry travel.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
It starts at 1111 + 0000 = 1111. Turn auto off, then set B0 to 1 and press step repeatedly to watch 1111 + 0001 resolve. The carry leaves bit 0, which makes bit 1 produce a carry, then bit 2, then bit 3. The answer, 1 0000, is only correct once the carry has rippled through every stage. It takes 8 gate delays to settle, and the adder's longest path is 9.
Each stage adds about two gate delays to the carry chain, so an n-bit ripple adder takes about 2n. That's fine for 4 bits, but a 64-bit adder would need about 128 gate delays, while a clock cycle in a 4 GHz CPU is only 250 ps — on the order of 15 to 25 gate delays. The adder has to finish within a cycle, so real CPUs use faster designs.
Faster adders
- Carry select. Split the adder into a lower and an upper half, and build the upper half twice: once assuming a carry in of 0, once assuming 1. Both run while the lower half works, and when its real carry arrives, a multiplexer picks the right upper result. The work is duplicated, but the time is roughly halved, and the trick can be applied again inside each half.
- Carry lookahead. Each bit position can tell early whether it will generate a carry (g = A·B) or propagate an incoming one (p = A ⊕ B). The carry out of bit i is then cᵢ₊₁ = gᵢ + pᵢ·cᵢ, and expanding that formula lets a circuit compute several carries directly from the g's and p's instead of waiting for them one by one.
- Parallel prefix adders (Kogge–Stone, Brent–Kung, and others) arrange those g/p combinations as a tree, so a 64-bit carry takes about log₂ 64 = 6 levels instead of 64 stages. That's what fast CPU adders use: more gates in exchange for much less delay.
Subtraction is addition
The adder can subtract, too. In two's complement, −B is NOT B + 1, so:
A − B = A + (NOT B) + 1
An ALU subtracts by inverting B and setting the carry in to 1. Here is 7 − 5, as 0111 + 1010 + 1:
Four full adders, the carry rippling from bit 0 (top) to bit 3. Each stage adds two gate delays to the carry path, so the worst case (e.g. 1111 + 0001) takes about 2n gate delays: step through it to watch the carry travel.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
The four sum bits read 0010 = 2. The carry out is 1, which in a subtraction means "no borrow". That's why x86 sets CF to the opposite of the adder's carry out after a sub or cmp: CF = 1 means the subtraction had to borrow, i.e. A < B as unsigned numbers. The same adder, fed differently, handles add, sub, cmp, inc, dec and neg.
The ALU: one slice per bit
An ALU computes one of several operations on two inputs, chosen by control lines. The classic design is a bit slice: a small circuit for one bit position, containing the logic operations and a full adder, with a multiplexer that selects which result to output. Place 64 slices side by side, chain their carries, and you have a 64-bit ALU.
Every function is computed in parallel (AND, OR, full-adder sum, XOR) and a 4-to-1 multiplexer picks one: Op 00 = AND, 01 = OR, 10 = ADD, 11 = XOR. Cout is the adder's carry. Chain 64 of these slices, carry to carry, and you have the ALU of a 64-bit CPU.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
Here Op1·Op0 picks the operation: 00 = AND, 01 = OR, 10 = ADD, 11 = XOR. With A = B = 1 and ADD selected, the slice outputs sum 0 and carry out 1. Switch to AND, OR or XOR and only the multiplexer changes. Each gate computes all the time; the control lines just choose which result gets out.
Bit slices used to be real chips that designers bought and wired together. Today they're blocks in a design library, replicated by software, but the idea is the same. Tanenbaum's ALU slice also has inputs to force A or B to zero and to invert A. Those extra controls let one circuit compute results like B, −A or A + 1 without separate hardware.
Where the flags come from
The ALU also reports facts about its result, and those are the flags that cmp sets and conditional jumps read. Each one is a few more gates:
| Flag | Meaning | Circuit |
|---|---|---|
| ZF | result is zero | NOR of all result bits |
| SF | result is negative | the top result bit |
| CF | unsigned carry (or borrow) | the carry out of the top bit (inverted for subtraction on x86) |
| OF | signed overflow | carry into the top bit XOR carry out of it |
Overflow is the subtle one. Signed overflow happens when two numbers of the same sign produce a result of the other sign — exactly when the carry into the top bit differs from the carry out of it. Try it on 4 bits:
Four full adders, the carry rippling from bit 0 (top) to bit 3. Each stage adds two gate delays to the carry path, so the worst case (e.g. 1111 + 0001) takes about 2n gate delays: step through it to watch the carry travel.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
0111 + 0001 = 1000. As unsigned numbers that's 7 + 1 = 8, correct, with no carry out: CF = 0. As signed 4-bit numbers it's 7 + 1 = −8, which is wrong. A carry went into bit 3 but none came out, so OF = 1. The same bits, read two ways, give two different flags. That's why x86 has separate jumps for unsigned (jb, ja, which read CF) and signed (jl, jg, which read SF and OF) comparisons.
Beyond the adder
The rest of an integer unit uses similar building blocks:
- a shifter moves bits left or right. A barrel shifter shifts by any amount in one step, using layers of multiplexers that shift by 1, 2, 4, 8… positions;
- a multiplier is essentially many adders: partial products added in a tree, which is why
imultakes a few cycles rather than one; - a divider usually works iteratively, a few bits per cycle, which is why
divis so much slower.
Takeaways
- A half adder is XOR + AND. A full adder adds three bits, and its carry is the majority function.
- A ripple-carry adder chains full adders, so its delay grows with the width, about 2n gate delays.
- Carry-select, carry-lookahead and parallel-prefix adders spend more gates to bring that down to about log n.
- Subtraction is A + NOT B + 1, so one adder serves
add,sub,cmp,inc,decandneg. - An ALU is a row of bit slices plus a multiplexer per slice. ZF, SF, CF and OF are a few extra gates on its result and carries.