Building an Adder: Where Arithmetic Comes From
XOR gives you the sum bit, AND gives you the carry, and that is a half adder. Chain them and you can add any width — but the carry has to travel through every stage in turn, and that dependency is the reason adder design is a real engineering problem.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The half adder is two gates
Add two single bits and there are four cases. 0+0 is 0. 0+1 and 1+0 are 1. 1+1 is 2, which does not fit in one bit — it is 0 with a carry of 1. Write out the two output columns and they are recognisable immediately: the sum column is exactly XOR, and the carry column is exactly AND.
So a half adder is one XOR and one AND, sharing the same two inputs. That is the whole construction, and it is worth sitting with for a moment: the arithmetic operation everyone treats as primitive turns out to be two Boolean functions that were already available from Boolean Logic: The Four Operations Hardware Actually Has.
It is called a *half* adder because it cannot accept a carry coming in. That is fine for the lowest bit position, where there is nothing to carry from, and useless for every other position.
| A | B | Sum (A XOR B) | Carry (A AND B) | Decimal |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 + 0 = 0 |
| 0 | 1 | 1 | 0 | 0 + 1 = 1 |
| 1 | 0 | 1 | 0 | 1 + 0 = 1 |
| 1 | 1 | 0 | 1 | 1 + 1 = 2, i.e. 0 carry 1 |
The full adder, and chaining it
Every position above the lowest needs three inputs: two operand bits and the carry from below. That is a full adder, and it is built from two half adders plus an OR — add A and B, then add the carry-in to that result, and a carry is produced if either addition generated one.
Chain N full adders, wiring each carry-out to the next carry-in, and you have an N-bit ripple-carry adder. It is correct, it is the minimum gate count, and it is how addition is explained. It is also slow in a specific and instructive way.
The problem is visible in the timing below. Bit 0 settles quickly, but bit 7 cannot produce its final sum until the carry has rippled through all seven positions beneath it. Delay grows linearly with width, so a 64-bit ripple-carry adder would have a critical path of well over a hundred gate delays — which, per Logic Gates: Where Software Stops and Physics Starts, would force a clock period nobody would accept.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| bit 0 | s | s | s | s | s | s | s | s |
| bit 1 | w | s | s | s | s | s | s | s |
| bit 2 | w | w | s | s | s | s | s | s |
| bit 3 | w | w | w | s | s | s | s | s |
| bit 4 | w | w | w | w | s | s | s | s |
| bit 5 | w | w | w | w | w | s | s | s |
| bit 6 | w | w | w | w | w | w | s | s |
| bit 7 | w | w | w | w | w | w | w | s |
Breaking the dependency by computing ahead
The fix is to stop waiting for the carry and compute it directly instead. Each bit position can say two things about carries without knowing the incoming one: it generates a carry if both its operand bits are 1, and it propagates an incoming carry if either is 1. Generate is AND; propagate is OR or XOR depending on the formulation.
From generate and propagate signals, the carry into any position can be expressed as a formula over all the positions below it, and evaluated in constant depth rather than by rippling. That is carry-look-ahead, and it converts linear delay into roughly logarithmic delay at the cost of substantially more gates. Real designs use hybrids that split the width into blocks, because a full look-ahead across 64 bits would be enormous.
The generalisable lesson is the trade in the last row of the table: more parallel hardware to shorten a dependency chain. That is precisely the trade Out-of-Order Execution makes with instructions, Prefetching: The Hardware Guesses What You Will Read Next makes with memory, and Branch Prediction: Guessing Well Enough to Matter makes with control flow. The carry chain is where the pattern is easiest to see, because the dependency is a single wire.
| Design | Delay with width N | Gate cost | Where it is used |
|---|---|---|---|
| Ripple-carry | Linear in N | Minimal | Narrow additions; teaching |
| Carry-look-ahead | Roughly logarithmic in N | Substantially higher | Wide adders, usually in blocks |
| Carry-select | Roughly square root of N | Roughly double | Computes both possible results, then selects |
| Hybrid block designs | Close to logarithmic | Tuned per target | What production ALUs actually use |
| The pattern | Shorter dependency chain | More parallel hardware | Recurs at every level of this domain |
Key points
- A half adder is one XOR (sum) and one AND (carry) — arithmetic composed from Boolean logic.
- A full adder accepts a carry-in, which is what allows positions to be chained.
- Ripple-carry is minimal in gates but its delay grows linearly with width, because each position waits for the one below.
- Carry-look-ahead computes generate and propagate signals to break the chain, trading many more gates for roughly logarithmic delay.
- Spending parallel hardware to shorten a dependency chain is the recurring pattern of the entire domain.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Operand bits → XOR: the sum bit for each position is produced from the two operand bits and the carry-in.
- 2Operand bits → AND/OR: generate and propagate signals are computed for each position independently.
- 3Carry → next position: in a ripple design the carry must physically settle before the position above can finish.
- 4Look-ahead logic → all carries: alternatively, every carry is computed in parallel from the generate and propagate signals.
- 5Final sum → register: once the slowest bit settles, the complete result is available to be latched at the next clock edge.
- • Assuming addition takes constant time regardless of width; latency depends on the design and the operand width.
- • Believing hardware is fast because it is "closer to the metal" rather than because it is massively parallel.
- • Thinking carry-look-ahead is free; it costs a great deal of area and power to buy the shorter path.
Consequences, controls and cost
- • Addition latency depends on operand width and on the adder design, not on the values being added.
- • Adder depth is a major contributor to the critical path, and therefore to achievable clock frequency.
- • Wide additions cost disproportionately more hardware than narrow ones, which is one reason narrow types can be cheaper in silicon.
- • The same dependency-chain problem reappears at instruction and memory level, with the same class of solution.
- • Nothing directly — adder design is fixed long before software runs.
- • Recognise the dependency-chain shape when it appears in your own code: a serial chain of dependent operations cannot be overlapped, whether it is carries, instructions or pointer loads ([[pointer-chasing]]).
- • Expect the hardware to spend parallelism to hide latency, and structure code so that parallelism is available to spend.
- • Not directly observable from software. Instruction latency tables published by vendors show the result — typically one cycle for integer addition on contemporary cores.
- • Compare a long chain of dependent additions against the same number of independent ones; the difference exposes the dependency limit, not the adder ([[instruction-level-parallelism]]).
- • Faster adders cost area and power, which competes with cache and cores for the same silicon budget.
- • Deeper arithmetic logic can force a longer clock period unless it is pipelined across stages.
- • Narrow arithmetic is cheaper in hardware but requires more instructions when the data is wider.
Scope
§224 — what these claims are specific to.
- SIMPLIFIEDReal ALUs use hybrid multi-level schemes tuned to a specific process and target frequency, not the textbook ripple or full look-ahead shown here.
- MICROARCH-SPECIFICInteger addition is single-cycle on most contemporary cores, but multiplication, division and floating-point operations have longer and quite different latencies that vary by microarchitecture.