Part IFoundations

Arithmetic Hardware, Adders, Multipliers, Dividers, Shifters

July 31, 2026·18 min read·advanced

Digital Logic and Timing used a ripple-carry adder to show glitches and critical paths. This note explains why nobody builds one at speed.

01.Part 1, the one idea

Digital Logic and Timing used a ripple-carry adder to show glitches and critical paths. This note explains why nobody builds one at speed.

The answer is always the same sentence. The carry is the critical path. Every clever adder in existence is a scheme for computing carries faster, and once you see that, the whole zoo of named structures becomes one idea with variations.

Keep a second idea in front throughout. Every structure below trades area and power for delay. None is universally best. The interview question is almost never "what is the fastest adder," it is "which would you pick here and why," and the answer depends on whether the adder is on the critical path.

02.Part 2, addition

2.1 Ripple-carry, the baseline

Chain $N$ full adders, each waiting for the carry from the one below. The delay is

$t_{ripple} = N \cdot t_{FA}$

Linear in $N$ . For the 4-bit case at 2 ns per stage that was 8 ns. Scale it up and the problem becomes obvious.

Width	Delay at 2 ns per stage
4 bits	8 ns
16 bits	32 ns
64 bits	128 ns

A 64-bit ripple-carry adder would limit a chip to under 8 MHz. Completely unusable in a CPU.

But do not dismiss it. It is the smallest and lowest-power adder there is, with no extra logic beyond the full adders themselves. In a block where the adder is nowhere near the critical path, for example incrementing a slow counter or computing an address that is not needed for several cycles, ripple-carry is the right answer and anything fancier is wasted area and power. Knowing when not to use the fast structure is part of the skill.

2.2 The insight, generate and propagate

Watch what the carry chain is actually doing and you will notice something.

Consider one bit position with inputs $a_i$ and $b_i$ . Ask what it does with a carry, before knowing whether a carry arrives.

If both inputs are 1, the position produces a carry out regardless of the carry in. $1 + 1 = 10$ , carry out, and an incoming carry only affects the sum bit. Call this generate.
If exactly one input is 1, then a carry out happens if and only if a carry comes in. $1 + 0 + 0 = 1$ , no carry. $1 + 0 + 1 = 10$ , carry. Call this propagate.
If neither input is 1, no carry out ever, regardless. Call this kill.

Formally,

$g_i = a_i \cdot b_i \qquad p_i = a_i \oplus b_i$

Here is why this matters enormously. Both $g_i$ and $p_i$ depend only on $a_i$ and $b_i$ , which are available at time zero. You do not need to wait for anything. Every bit position can compute its own generate and propagate simultaneously, in one gate delay, before any carry has moved anywhere.

The carry out of position $i$ is then

$c_{i+1} = g_i + p_i \cdot c_i$

which reads, "a carry comes out if this position generates one, or if it propagates one that came in."

2.3 Carry-lookahead, unrolling the recursion

That equation still looks recursive, since $c_{i+1}$ depends on $c_i$ . But now you can substitute repeatedly and the recursion disappears.

$c_1 = g_0 + p_0 c_0$ $c_2 = g_1 + p_1 c_1 = g_1 + p_1 g_0 + p_1 p_0 c_0$ $c_3 = g_2 + p_2 c_2 = g_2 + p_2 g_1 + p_2 p_1 g_0 + p_2 p_1 p_0 c_0$

Read $c_3$ in words. A carry comes out of position 3 if position 2 generates, or position 1 generates and position 2 propagates it, or position 0 generates and positions 1 and 2 both propagate it, or a carry came in and all three propagated it.

Every term is a product of things known at time zero. So every carry is now a two-level AND-OR function of the inputs, computable in roughly two gate delays, rather than rippling through $N$ stages.

The catch is visible in the equations. $c_3$ needs a 4-input AND. $c_{15}$ would need a 16-input AND, and $c_{63}$ a 64-input AND. Real gates cannot have arbitrary fan-in, because each additional input adds capacitance and series resistance, so a 64-input AND is either unbuildable or so slow it defeats the purpose.

The practical answer is to do lookahead in blocks, typically 4 bits, then treat each block as a super-position with its own block-generate and block-propagate, and apply the same trick again one level up. Delay becomes roughly $O(\log N)$ at a real cost in area.

2.4 Parallel prefix, the industrial answer

Here is the observation that turns adder design into a solved problem.

The carry operation is associative. Define an operator on generate-propagate pairs,

$(g, p) \circ (g', p') = (g + p \cdot g',\ p \cdot p')$

Check that it composes correctly and you will find $(g,p) \circ ((g',p') \circ (g'',p'')) = ((g,p) \circ (g',p')) \circ (g'',p'')$ .

Associativity is a big deal, because it means you can group the computation any way you like and get the same answer. Computing all the carries is therefore a prefix problem, mathematically identical to computing all running sums of an array, and prefix problems have well-studied parallel structures with $\log_2 N$ depth.

That reframing is why adder design is not ad hoc. You are choosing a point in a known design space.

Kogge-Stone. Minimum depth, exactly $\log_2 N$ stages, with uniform fanout of two. For 64 bits that is 6 stages. It is the fastest and it pays in cell count and wiring, because the number of operator cells is large and the wire crossings are dense. In physical design a Kogge-Stone adder is a routing problem as much as a logic one.

Brent-Kung. Builds a reduction tree upward and then a distribution tree back down, roughly $2\log_2 N$ stages, so about twice the depth. In exchange it uses far fewer cells and much less wiring.

The trade in one line. Kogge-Stone buys depth with wires. Brent-Kung buys wires with depth. Real designs land between them, and hybrids such as Han-Carlson use Kogge-Stone stages in the middle and Brent-Kung stages at the edges to get most of the speed at a fraction of the wiring.

2.5 Carry-select, the brute-force trick

A different idea, and easy to explain in an interview.

Split the adder in half. The lower half computes normally. For the upper half, you do not know the incoming carry yet, so compute it twice in parallel, once assuming the carry is 0 and once assuming it is 1. When the real carry finally arrives from the lower half, a multiplexer selects the correct precomputed answer.

The upper half's addition time is now completely off the critical path, replaced by a single mux delay. You paid roughly double the area of the upper half to buy that.

Carry-skip is the cheap relative. If all the propagate signals in a block are 1, then a carry entering that block will certainly exit it, so route it around the block with a single AND-OR rather than letting it ripple through. Small extra logic, useful speedup, nowhere near lookahead.

2.6 Choosing

Structure	Delay	Area	Use when
Ripple-carry	$O(N)$	smallest	off the critical path, power-sensitive
Carry-skip	better than ripple	small	modest speedup needed cheaply
Carry-select	good	roughly 1.5x	moderate width, easy to pipeline
Brent-Kung	$O(\log N)$ , deeper	moderate	wiring-constrained, good compromise
Kogge-Stone	$O(\log N)$ , minimum	largest	genuinely on the critical path

03.Part 3, multiplication

3.1 What multiplication is, in hardware

Multiplication is addition of shifted copies, exactly like long multiplication by hand.

Multiply $A \times B$ where $B$ is $n$ bits. For each bit $b_i$ of $B$ , form a partial product, which is $A$ shifted left by $i$ positions if $b_i$ is 1, and zero if $b_i$ is 0. Then sum all $n$ partial products.

Work $1101 \times 0101$ , which is $13 \times 5 = 65$ .

Plain Text

        1101        (A = 13)
      x 0101        (B = 5)
      ------
        1101        b0 = 1, so A shifted by 0
      0000         b1 = 0, so zero
      1101          b2 = 1, so A shifted by 2
    0000           b3 = 0, so zero
  ---------
    1000001        = 65
```text
So a multiplier is two problems. **Generate** the partial products, which is trivial since it is just AND gates and wiring. **Sum** them, which is the hard part, because you are adding $n$ numbers rather than two.

### 3.2 The array multiplier

The naive approach sums them in a regular grid of full adders, one row per partial product. It is beautifully regular, easy to lay out, and its delay is **linear in $n$**, because each row's carries must settle before the next row can finish.

Same problem as ripple-carry, one order up. For a 64-bit multiplier this is far too slow.

### 3.3 Carry-save, the key trick

Here is the insight that makes fast multipliers possible, and it is worth sitting with because it is genuinely clever.

The reason adding is slow is **carry propagation**, from Part 2. So what if you simply **do not propagate the carries** until the very end?

A **carry-save adder** takes **three** numbers and produces **two**, a sum vector and a carry vector, such that the sum vector plus the carry vector shifted left by one equals the sum of the three inputs.

Crucially, it does this in **the delay of a single full adder**, independent of width, because each bit position operates completely independently. Bit 5's full adder does not wait for bit 4, because its carry output goes into the carry **vector** rather than into bit 6's carry input.

<Figure src="/figures/hardware-interview-prep/iv-05-Arithmetic-Hardware-fig01.svg" alt="A carry-save adder takes three input vectors and returns two, a sum vector and a carry vector, in the delay of a single full adder, because every bit position compresses on its own and no carry ever travels sideways." caption="A carry-save adder takes three input vectors and returns two, a sum vector and a carry vector, in the delay of a single full adder, because every bit position compresses on its own and no carry ever travels sideways." id="fig:05-Arithmetic-Hardware-1" />

So you can compress many numbers to two very quickly, and you pay for exactly **one** real carry-propagate addition, right at the end, using a fast adder from Part 2.

### 3.4 Wallace and Dadda trees

A **Wallace tree** applies carry-save reduction as aggressively as possible. Take the $n$ partial products, group them in threes, reduce each group of 3 to 2, and repeat. Each level reduces the count by a factor of roughly $3/2$, so reaching 2 numbers takes $O(\log n)$ levels.

For 16 partial products the reduction goes 16, 11, 8, 6, 4, 3, 2, which is 6 levels. Compare that with 16 levels for an array multiplier.

A **Dadda tree** does the same thing with a different schedule, deferring reductions until they are actually needed to hit the next target height. It uses fewer adder cells for the same depth, at the cost of a slightly larger final adder.

### 3.5 Booth encoding

The tree attacks the summation. **Booth encoding** attacks the other side, the **number** of partial products.

The observation is that a run of consecutive 1s in the multiplier can be replaced by a subtraction and an addition. For example $0111$, which is 7, equals $1000 - 0001$, which is $8 - 1$. So instead of three partial products for three 1 bits, you need two.

**Radix-4 Booth** systematizes this. Inspect overlapping groups of **3 bits** of the multiplier, sliding by 2 each time, and emit **one** partial product per group chosen from the set $\{0, +A, -A, +2A, -2A\}$.

| 3-bit group | Partial product |
|---|---|
| 000 | 0 |
| 001 | $+A$ |
| 010 | $+A$ |
| 011 | $+2A$ |
| 100 | $-2A$ |
| 101 | $-A$ |
| 110 | $-A$ |
| 111 | 0 |

Every one of those is cheap to produce. $2A$ is a shift, $-A$ is a two's complement which is an invert plus a carry-in, and 0 is nothing.

The payoff is that a 64-bit multiplier goes from **64 partial products to 32**, halving the height of the tree and removing about one level of reduction depth plus a great deal of area.

That is why essentially every production multiplier is the same three-part recipe. **Booth encoding to halve the partial products, a compression tree to reduce them to two, and a parallel prefix adder to finish.** If asked to describe a modern multiplier, that sentence is the answer.

---

## Part 4, division

### 4.1 Why division is the hard one

"Why is divide so slow" is a common question and the answer is structural rather than incidental.

Multiplication decomposes beautifully. All the partial products can be **generated simultaneously** because each depends only on the inputs, and then summed in a tree. Division cannot do this, because **each quotient digit depends on the remainder left by the previous one**. You genuinely cannot compute digit 5 before digit 4. The dependence is inherently sequential.

That is the whole story. Multiply is parallelizable, divide is iterative, and no amount of cleverness removes the fundamental dependence.

### 4.2 Restoring and non-restoring

**Restoring division** is binary long division exactly as taught by hand. Shift the remainder left, subtract the divisor, and if the result went negative, add the divisor back to restore the old remainder and record a quotient bit of 0. Otherwise keep the result and record 1.

**One quotient bit per iteration**, and the wasteful part is the add-back when the subtraction guessed wrong.

**Non-restoring division** avoids the add-back by allowing the remainder to go negative and correcting on the **next** step instead. If the remainder is positive, subtract the divisor. If negative, add it. Same one bit per iteration, less work per iteration.

Either way, a 64-bit divide takes **64 iterations**, each involving a full-width add or subtract with its own carry propagation. That is the source of the latency.

### 4.3 SRT division

The production algorithm, and the reason it is faster is worth understanding.

In restoring division, choosing the next quotient digit requires comparing the full-width remainder against the divisor, which needs a full carry propagation. That comparison is inside the loop, so it is paid every iteration.

**SRT** uses a **redundant** quotient digit set, for example $\{-2, -1, 0, 1, 2\}$ for radix 4 rather than just $\{0,1,2,3\}$. Redundancy means several digit choices lead to a valid final answer, so the choice does not have to be exactly right, only close enough to be correctable later.

Because the choice can be approximate, it can be made by inspecting **only a few leading bits** of the remainder and divisor, looked up in a small table. That removes the full-width comparison from the loop entirely, and it lets the remainder be kept in carry-save form so no carry propagation happens per iteration either.

Higher radix retires more bits per iteration. Radix 4 gives 2 bits per iteration, halving the iteration count.

**The Pentium FDIV bug** is the famous cautionary tale here. Intel's radix-4 SRT implementation had a quotient-selection lookup table with a handful of missing entries, which produced wrong results for certain rare operand combinations. It cost roughly 475 million dollars in 1994 and it is a good story to know, both as history and as an illustration of why formal verification of arithmetic units matters, which links to [Verification Methodology](/learn/hardware-interview-prep/verification-methodology).

### 4.4 Newton-Raphson and Goldschmidt

A completely different strategy. Rather than producing quotient digits, **compute the reciprocal $1/B$ and multiply**.

Newton-Raphson finds roots of $f(x) = 0$ by iterating $x_{n+1} = x_n - f(x_n)/f'(x_n)$. To compute $1/B$, choose $f(x) = 1/x - B$, which gives the iteration

$$x_{n+1} = x_n (2 - B x_n)$$

which needs only multiplications and a subtraction, no division.

The remarkable property is **quadratic convergence**. Each iteration roughly **doubles** the number of correct bits. Start with a seed from a small lookup table giving 8 correct bits, and one iteration gives 16, two gives 32, three gives 64.

So a 64-bit reciprocal takes about **three iterations**, each a couple of multiplies, and it reuses the multiplier hardware you already built rather than needing a dedicated divider array. Goldschmidt is a variant that restructures the same idea for better pipelining.

The catch is **correct rounding**. The iterative result is very close to correct but the final rounding to the exact IEEE 754 result requires care, often a final correction step, which is where implementations get subtle.

### 4.5 The summary an interviewer wants

**Addition is cheap** and can be made $O(\log N)$. **Multiplication is a tree**, is $O(\log n)$ in depth, and pipelines beautifully so throughput can be one per cycle even though latency is 3 to 5. **Division is iterative**, is long-latency, rarely fully pipelined because pipelining would require replicating the iteration hardware, and is therefore something compilers work hard to avoid, for example by converting division by a constant into multiplication by a precomputed reciprocal.

Those relative costs drive the execution port asymmetry in [Execution Units](/learn/hardware-interview-prep/execution-units).

---

## Part 5, shifters

### 5.1 Barrel shifter

Shifting by a variable amount looks easy and is not, because the shift amount is data rather than a constant.

A **barrel shifter** shifts by any amount in a single pass using $\log_2 N$ layers of multiplexers. Layer $k$ either shifts by $2^k$ or does not, controlled by bit $k$ of the shift amount.

To shift by 13, note $13 = 8 + 4 + 1 = 1101_2$. So the layer-3 stage shifts by 8, the layer-2 stage shifts by 4, the layer-1 stage passes through, and the layer-0 stage shifts by 1.

<Figure src="/figures/hardware-interview-prep/iv-05-Arithmetic-Hardware-fig02.svg" alt="A barrel shifter is a chain of mux layers, each of which either applies its own fixed power-of-two shift or passes the data straight through, selected by one bit of the shift amount, so any shift completes in a single pass." caption="A barrel shifter is a chain of mux layers, each of which either applies its own fixed power-of-two shift or passes the data straight through, selected by one bit of the shift amount, so any shift completes in a single pass." id="fig:05-Arithmetic-Hardware-2" />

For 64 bits that is 6 mux layers. The same structure handles logical shifts, arithmetic shifts by feeding in the sign bit, and rotates by feeding in the wrapped bits, with modest extra control.

### 5.2 Why it surprises people in physical design

A barrel shifter contains almost no arithmetic. It is **muxes and wires**. Every layer's output must be able to reach positions far away, so the wiring is long and dense.

That makes it **wire-dominated** rather than gate-dominated, which has two consequences. Its delay does not improve with process scaling as much as logic does, since wire delay scales poorly, and it is a frequent source of routing congestion in [STA Synthesis and Physical Design](/learn/hardware-interview-prep/sta-synthesis-and-physical-design).

**Funnel shifters** generalize the structure by concatenating two words and selecting a window from the pair, which implements rotates and unaligned byte extraction, useful for the misaligned access handling in [Load Store and Memory Ordering](/learn/hardware-interview-prep/load-store-and-memory-ordering).

---

## Part 7, check yourself

1. Why is the carry the critical path in an adder? (1)
2. Define generate and propagate. What is the crucial property that makes them useful? (2.2)
3. Read the expanded expression for $c_3$ in words. Why does the lookahead approach hit a limit? (2.3)
4. Why does associativity of the carry operator matter? What problem class does it put adders into? (2.4)
5. Compare Kogge-Stone and Brent-Kung in one sentence each. When would you pick each? (2.4)
6. Explain carry-select and state exactly what it costs. (2.5)
7. Your adder is nowhere near the critical path and the block is power-sensitive. What do you build, and why is that not a cop-out? (2.1, 2.6)
8. What does a carry-save adder do, and why is its delay independent of width? (3.3)
9. How many reduction levels does a Wallace tree need for 16 partial products? (3.4)
10. What does Booth encoding reduce, by how much, and why is each Booth partial product cheap to produce? (3.5)
11. Describe a modern production multiplier in one sentence. (3.5)
12. Why is division fundamentally harder to parallelize than multiplication? (4.1)
13. What does SRT's redundant digit set buy, and what does it remove from the loop? (4.3)
14. Why does each Newton-Raphson iteration double the correct bits, and what is the remaining difficulty? (4.4)
15. How many mux layers in a 64-bit barrel shifter, and why is it a physical design problem? (5.1, 5.2)

---

## Part 8, related notes

- [Digital Logic and Timing](/learn/hardware-interview-prep/digital-logic-and-timing) for critical path and the delay model underneath all of this
- [Execution Units](/learn/hardware-interview-prep/execution-units) for how these become ports, and why divider latency shapes scheduling
- [Integer Arithmetic Inside the CPU](/learn/computer-architecture/integer-arithmetic) for the vault's deeper multiply and divide treatment
- [Floating-Point Arithmetic](/learn/computer-architecture/floating-point) for IEEE 754, FMA, and rounding
- [STA Synthesis and Physical Design](/learn/hardware-interview-prep/sta-synthesis-and-physical-design) for why wire-dominated structures like shifters cause congestion

Book mode