Carry-Lookahead Adder

Every program you run adds numbers thousands of times per second. Deep inside the CPU, binary addition seems trivial: line up the bits, add each pair, carry the one. But that "carry the one" is the problem.

In a ripple-carry adder — the most naive design — each bit position must wait for the carry from the position below it. Adding two 64-bit numbers means the carry signal may have to ripple through 64 stages before the answer is ready. The delay grows linearly with the number of bits.

The carry-lookahead adder (CLA), invented in its modern form by Gerald Weinberger and J. L. Smith at IBM in 1958 and formalized by Flores shortly after, breaks this chain. Instead of waiting, it precomputes whether each bit position will generate a carry on its own, or merely propagate a carry from below — and then combines these signals in a tree so that all carries are known simultaneously.

The result: addition delay grows as $O(\log n)$ gate levels instead of $O(n)$. For a 64-bit adder that is the difference between 64 gate delays and roughly 6. Modern processors use variants of this idea (Kogge-Stone, Brent-Kung, Han-Carlson trees) in every arithmetic unit.

Choose two numbers and hit Add. The demo simulates both a ripple-carry adder and a carry-lookahead adder on the same inputs, counting how many gate-delay steps each one needs.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{lbl_a}} <input id="inA" type="number" min="0" max="255" value="178"/></label>
  <label>{{lbl_b}} <input id="inB" type="number" min="0" max="255" value="93"/></label>
  <button id="btnAdd" type="button">{{btn_add}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="result-row">
  <span class="result-label">{{lbl_result}}</span>
  <span id="resultDec" class="result-val">—</span>
  <span class="result-bin" id="resultBin"></span>
</div>
<div class="section-title">{{title_ripple}}</div>
<div id="rippleBits" class="bit-row"></div>
<div class="delay-bar">
  <span class="delay-label">{{lbl_delay}}</span>
  <span id="rippleDelay" class="delay-num">—</span>
  <span class="delay-unit">{{unit_gates}}</span>
</div>
<div class="section-title">{{title_cla}}</div>
<div id="claBits" class="bit-row"></div>
<div class="delay-bar">
  <span class="delay-label">{{lbl_delay}}</span>
  <span id="claDelay" class="delay-num">—</span>
  <span class="delay-unit">{{unit_gates}}</span>
</div>
<div id="status" class="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem; align-items: center; margin-bottom: .6rem; }
label { font-size: .88rem; display: flex; align-items: center; gap: .3rem; }
input[type=number] { width: 68px; padding: .25rem .4rem; border: 1px solid #adb1b8; border-radius: 6px; font: inherit; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result-row { display: flex; align-items: center; gap: .5rem; margin: .3rem 0 .6rem; font-size: .9rem; }
.result-label { color: #555; }
.result-val { font-weight: 700; font-size: 1.05rem; }
.result-bin { font-family: ui-monospace, monospace; font-size: .78rem; color: #666; }
.section-title { font-size: .8rem; font-weight: 600; color: #1d3557; text-transform: uppercase; letter-spacing: .06em; margin: .5rem 0 .2rem; }
.bit-row { display: flex; flex-wrap: wrap; gap: 3px; margin-bottom: .3rem; }
.bit { width: 26px; height: 26px; display: flex; align-items: center; justify-content: center; font: 700 11px ui-monospace, monospace; border-radius: 5px; background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; transition: background .25s, color .25s; }
.bit.carry { background: #e63946; color: #fff; border-color: #c92f3c; }
.bit.active { background: #f4a261; color: #fff; border-color: #e07b3e; }
.bit.done { background: #2a9d8f; color: #fff; border-color: #1d7a6e; }
.delay-bar { display: flex; align-items: center; gap: .35rem; font-size: .88rem; color: #444; margin-bottom: .3rem; }
.delay-num { font-weight: 700; font-size: 1.1rem; color: #1d3557; }
.delay-unit { font-size: .78rem; color: #888; }
.status { min-height: 1.3em; font-size: .9rem; font-weight: 600; color: #0a7d33; margin-top: .4rem; }

// Code not found

Watch the carry chain light up from right to left in the ripple adder — each stage waits for its neighbor. In the lookahead adder all carries are resolved after just two logic levels (generate/propagate, then combine), regardless of how many bits are involved.

The key insight is two simple signals per bit position $i$, given input bits $a_i$ and $b_i$:

• Generate: $G_i = a_i \mathbin{\&} b_i$ — this position produces a carry no matter what arrives from below.
• Propagate: $P_i = a_i \mathbin{|} b_i$ — this position passes on a carry if one arrives from below.

The carry out of position $i$ is then:

$$C_{i+1} = G_i \mathbin{|} (P_i \mathbin{\&} C_i)$$

A ripple adder evaluates this recurrence sequentially — each $C_{i+1}$ must wait for $C_i$, giving $O(n)$ depth.

A lookahead adder instead expands the recurrence for every position simultaneously. For a 4-bit group:

$$C_4 = G_3 \mathbin{|} P_3 G_2 \mathbin{|} P_3 P_2 G_1 \mathbin{|} P_3 P_2 P_1 G_0 \mathbin{|} P_3 P_2 P_1 P_0 C_0$$

Every carry can now be computed with just two gate levels after the $G$ and $P$ signals are ready. For wider adders, prefix trees (Kogge-Stone, Brent-Kung) generalize the idea: carry from position $j$ to $i$ is computed in $O(\log n)$ levels using the associative operator $(G_{j:i}, P_{j:i}) = (G_{j:k} | P_{j:k} G_{k-1:i},\; P_{j:k} P_{k-1:i})$.

The trade-off is hardware: a 64-bit ripple adder needs ~64 full adders wired in a chain; a Kogge-Stone adder needs $O(n \log n)$ gates but only $O(\log n)$ delay. In modern VLSI, speed wins — you can afford the extra gates. See also fast multiplication for how similar prefix-tree tricks speed up the multiplier.

The carry-lookahead principle is not a curiosity — it is in every piece of arithmetic hardware you use:

• CPU arithmetic logic units (ALUs): every integer add, subtract, compare, and address calculation uses a fast adder. Modern x86 and ARM cores use 64-bit adders clocking at multi-GHz; ripple carry would make arithmetic the bottleneck.
• Floating-point units: adding IEEE 754 floats requires aligning mantissas and then adding them. The mantissa adder is a classic CLA target.
• GPUs: thousands of shader cores each contain fast adders that execute in parallel. The area/speed tradeoff of Brent-Kung (fewer gates, slightly more depth) vs Kogge-Stone (more gates, minimum depth) is a live design choice.
• FPGAs: carry-chain primitives are built into FPGA fabrics specifically to let designers implement fast adders in reconfigurable logic.
• Cryptography: big-number addition in RSA or elliptic-curve arithmetic runs on multi-word CLA trees implemented in hardware accelerators.

Understanding the CLA is a stepping stone to deeper topics: see fast multiplication for how Wallace trees extend the same idea to multipliers, or circuit complexity for the theoretical framework that bounds how fast any circuit can add.

The carry-lookahead adder solves a problem that is easy to state and surprisingly deep: in binary addition, every carry depends on the carry below it. Breaking that chain of dependencies requires looking ahead — computing, in parallel, whether each position will generate or propagate a carry.

The result is an $O(\log n)$ depth circuit instead of an $O(n)$ one, achieved with a constant-depth generate/propagate layer followed by a prefix tree. It is one of the earliest and most elegant examples of turning a sequential process into a parallel one, and its fingerprint is in every ALU that has ever run your code.

The next time you see an integer addition complete in a single nanosecond, remember: underneath, a prefix tree of generate-and-propagate signals raced to the answer before the carry had a chance to ripple at all.