How Binary Arithmetic Logic Units Actually Add Numbers

The Speed of Light in Copper and the Ripple-Carry Wall

When a software engineer writes c = a + b, the central processing unit has less than a single clock tick—often less than 250 picoseconds ($0.25\text{ ns}$) in a $4\text{ GHz}$ chip—to accept two 64-bit binary numbers, compute their sum, generate arithmetic condition flags, and store the result into a register.

In elementary binary arithmetic, addition is performed column by column from right to left, exactly like pencil-and-paper decimal addition:

    Carries:   1 1 1 0 0 0
    Operand A: 0 0 1 1 1 0 1 1  (59)
  + Operand B: 0 0 0 1 0 1 1 1  (23)
  ─────────────────────────────
    Sum:       0 1 0 1 0 0 1 0  (82)

To implement this in silicon, digital designers build a circuit called a 1-bit Full Adder. A full adder accepts three 1-bit inputs—Operand $A_i$, Operand $B_i$, and an incoming carry bit $C_i$ from the column to the right—and produces two outputs: the Sum bit $S_i$ and an outgoing Carry bit $C_{i+1}$.

The Boolean equations for a full adder are derived directly from binary truth tables:

$$S_i = A_i \oplus B_i \oplus C_i$$

$$C_{i+1} = (A_i \cdot B_i) + (C_i \cdot (A_i \oplus B_i))$$

         Ai ────────┬────────────────┐
                    │                │
         Bi ─────┬──┼────────────┐   │
                 │  │            │   │
               ┌─┴──┴─┐        ┌─┴───┴┐
               │ XOR1 │        │ AND1 │
               └──┬───┘        └───┬──┘
                  │ (A ^ B)        │ (A & B)
         Ci ───┬──┼────────┐       │
               │  │        │       │
             ┌─┴──┴─┐    ┌─┴───┐   │
             │ XOR2 │    │AND2 │   │
             └──┬───┘    └──┬──┘   │
                │           │      │
             Sum (Si)       └──┬───┘
                               │
                             ┌─┴──┐
                             │ OR │
                             └─┬──┘
                               │
                           Carry Out (C_i+1)

In physical CMOS logic, the XOR gate and the AND-OR logic each introduce approximately two gate delays (roughly $15\text{ to }25\text{ picoseconds}$ per stage in modern silicon).

If you connect 64 of these full adders in a linear chain—where the $C_{out}$ of stage 0 feeds the $C_{in}$ of stage 1, the $C_{out}$ of stage 1 feeds stage 2, and so on—you construct a Ripple-Carry Adder (RCA).

 A0 B0 C0       A1 B1          A2 B2                  A63 B63
  │  │  │        │  │           │  │                    │  │
┌─▼──▼──▼─┐    ┌─▼──▼──┐      ┌─▼──▼──┐               ┌─▼──▼──┐
│ Full    │ C1 │ Full  │  C2  │ Full  │               │ Full  │ C64
│ Adder 0 ├────► Adder ├──────► Adder ├─── ... ───────► Adder ├────► Overflow
└────┬────┘    └─1──┬──┘      └──2─┬──┘               └──63┬──┘
     │              │              │                       │
     S0             S1             S2                     S63

Now consider what happens in the worst-case scenario: adding $1$ to a number consisting of 63 consecutive ones (0111...111 + 0000...001).

The carry bit generated at bit position 0 must physically ripple through all 64 adders before bit 63 can calculate its sum bit $S_{63}$. If each full adder takes $25\text{ picoseconds}$ to resolve its carry output, the total carry propagation delay is:

$$t_{delay} = 64 \times 25\text{ ps} = 1,600\text{ ps} = 1.6\text{ nanoseconds}$$

An adder that takes $1.6\text{ nanoseconds}$ cannot operate faster than $625\text{ MHz}$. At $4\text{ GHz}$, the processor's clock cycle is only $250\text{ ps}$. The ripple-carry adder is six times too slow for modern computing.

The Breakthrough: Carry-Lookahead Logic

In 1958, computer scientists realised that a circuit does not actually need to wait for a carry to ripple down the line to know whether one will be created or passed along.

By examining only the two input bits $A_i$ and $B_i$ at stage $i$, the circuit can immediately determine two fundamental properties before any carry arrives:

1. Generate ($G_i$): If both $A_i = 1$ and $B_i = 1$, this bit position will guarantee the creation of a carry out, regardless of whether a carry came in from the right: $$G_i = A_i \cdot B_i$$

2. Propagate ($P_i$): If either $A_i = 1$ or $B_i = 1$ (or in XOR form, exactly one is 1), any incoming carry from the right will be propagated through to the next stage: $$P_i = A_i \oplus B_i \quad (\text{or } A_i + B_i)$$

With $G_i$ and $P_i$ established, the carry-out equation simplifies into an elegant linear expression:

$$C_{i+1} = G_i + P_i \cdot C_i$$

"The carry out of stage $i$ is 1 if stage $i$ generated a carry, OR if stage $i$ propagated an incoming carry."

Now comes the mathematical leap: recursive substitution. We can write every carry bit purely in terms of the initial carry-in $C_0$ and the immediately available $G$ and $P$ signals:

For Stage 0: $$C_1 = G_0 + P_0 C_0$$

For Stage 1: $$C_2 = G_1 + P_1 C_1 = G_1 + P_1(G_0 + P_0 C_0) = G_1 + P_1 G_0 + P_1 P_0 C_0$$

For Stage 2: $$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$$

For Stage 3: $$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$$

Look closely at the equation for $C_4$. It does not depend on $C_1$, $C_2$, or $C_3$. It depends only on $C_0$ and the input bits of the preceding stages.

In physical silicon, this means that $C_4$ can be calculated using a two-level AND-OR circuit. The carry signal does not ripple through four sequential full adders; it is evaluated in exactly two gate delays, regardless of word length.

Logarithmic Scaling: Parallel Prefix Trees (Kogge-Stone)

While the carry-lookahead equation works brilliantly for 4 bits, a practical limitation arises when expanding to 64 bits: gate fan-in.

Look at the equation for $C_4$: the final AND gate requires four inputs ($P_3 P_2 P_1 P_0$). For bit 64, an elementary carry-lookahead gate would require an AND gate with 65 physical inputs, and an OR gate with 65 physical inputs.

In physical CMOS, connecting 65 transistor gates in series would create a channel resistance so immense that the circuit would become slower than a ripple-carry adder. In standard cell libraries, the maximum allowable fan-in for a single gate is typically 4.

To solve this, modern microprocessors arrange the carry calculations into a Parallel Prefix Network. The most celebrated of these architectures is the Kogge-Stone Adder, invented by Peter Kogge and Harold Stone in 1973.

The Kogge-Stone adder relies on the mathematical fact that carry generation is an associative operator. We define a carry operator $\circ$ acting on pairs of $(G, P)$ signals:

$$(G'', P'') \circ (G', P') = (G'' + P'' \cdot G',; P'' \cdot P')$$

Because this operation is associative:

$$(A \circ B) \circ C = A \circ (B \circ C)$$

Carries can be combined in any grouping. Instead of a linear sequence of 64 steps ($O(N)$), the Kogge-Stone adder organizes the calculation into a binary tree of logarithmic depth:

$$\text{Levels} = \log_2(64) = 6\text{ levels}$$

Bit:      7       6       5       4       3       2       1       0
Input:   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)  (Level 0)
           │       │       │       │       │       │       │       │
Step 1:    ├───┐   ├───┐   ├───┐   ├───┐   ├───┐   ├───┐   ├───┐   │    (Distance 1)
           ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼   │
Step 2:    ├───────┼───┐   ├───────┼───┐   ├───────┼───┐   │   │   │    (Distance 2)
           ▼       ▼   ▼   ▼       ▼   ▼   ▼       ▼   ▼   ▼   ▼   │
Step 3:    ├───────────────┼───────┼───┐   │       │   │   │   │   │    (Distance 4)
           ▼               ▼       ▼   ▼   ▼       ▼   ▼   ▼   ▼   │
Carries:  C7      C6      C5      C4      C3      C2      C1      C0    (All Carries Ready)

In a Kogge-Stone adder:

• At Step 1, each bit combines its $(G, P)$ with its immediate neighbor (distance 1).
• At Step 2, each node combines with the node 2 positions away.
• At Step 3, each node combines with the node 4 positions away.
• By Step 6, every single bit position from 0 to 63 has received the combined prefix of all preceding bits.

Total time to resolve all 64 carries: just 6 logic levels, completing in approximately $120\text{ picoseconds}$. The addition completes well within the $250\text{ ps}$ clock budget of a $4\text{ GHz}$ CPU.

Two's Complement: Subtraction with the Same Hardware

In elementary mathematics, addition ($+$) and subtraction ($-$) are distinct operations requiring different algorithms. If a microprocessor required a separate set of 64-bit subtractor circuits alongside its adders, the arithmetic core would consume double the silicon area and double the electrical power.

Instead, computer hardware exploits a beautiful property of modular arithmetic: Two's Complement representation.

To subtract $B$ from $A$:

$$A - B = A + (-B)$$

In binary, the negative of a two's complement number is obtained by inverting every bit (one's complement, $\sim B$) and adding 1:

$$-B = \sim B + 1$$

Therefore:

$$A - B = A + (\sim B) + 1$$

Look at that formula: subtraction is simply an addition where operand $B$ is bit-inverted, and the carry-in to the lowest bit ($C_0$) is set to 1.

             B63             B1              B0
              │               │               │
  SUB ────┬───┼───────────┬───┼───────────┬───┼──────── (SUB Control Line)
          │ ┌─┴─┐         │ ┌─┴─┐         │ ┌─┴─┐
          └─┤XOR│         └─┤XOR│         └─┤XOR│
            └─┬─┘           └─┬─┘           └─┬─┘
              │ B63'          │ B1'           │ B0'
              │   A63         │   A1          │   A0
              │    │          │    │          │    │
            ┌─▼────▼─┐      ┌─▼────▼─┐      ┌─▼────▼─┐
            │ Stage  │      │ Stage  │      │ Stage  │
            │   63   │◄─...─┤   1    │◄─────┤   0    │◄─── SUB (C0 = 1)
            └────────┘      └────────┘      └────────┘

Chip architects place an XOR gate on every bit line of Operand $B$. The second input of each XOR gate is tied to a single control wire called SUB:

1. When performing Addition (SUB = 0):
   • $B_i \oplus 0 = B_i$ (Operand $B$ passes through unchanged).
   • $C_0 = 0$.
   • The circuit computes $A + B + 0 = A + B$.
2. When performing Subtraction (SUB = 1):
   • $B_i \oplus 1 = \sim B_i$ (Every bit of Operand $B$ is cleanly inverted).
   • $C_0 = 1$ (The carry-in is injected directly into stage 0).
   • The circuit computes $A + (\sim B) + 1 = A - B$.

A single wire transforms a 64-bit adder into a high-speed subtractor with zero additional adder hardware.

The Generation of Condition Flags

When an ALU executes an arithmetic operation, software frequently needs to branch based on the result:

• if (x == y) (Branch if equal)
• if (x < y) (Branch if less than)
• if (overflow) (Handle numeric overflow)

A CPU does not perform a second calculation to test these conditions. During the exact picoseconds that the sum bits are settling, dedicated CMOS logic monitors the internal voltages of the ALU and asserts four standardized Condition Code Flags in the CPU's Status Register (often named EFLAGS or RFLAGS on x86, or CPSR on ARM):

┌───────────────────────────────────────────────────────────┐
│                      ALU Flags Register                   │
├─────────────┬─────────────┬───────────────┬───────────────┤
│   Zero (Z)  │  Sign (N)   │   Carry (C)   │  Overflow (V) │
└─────────────┴─────────────┴───────────────┴───────────────┘

1. The Zero Flag ($Z$)

• Meaning: Asserted (1) if every single bit of the 64-bit result is 0.
• Physical Circuit: A 64-input NOR tree. If any sum bit $S_0, S_1, \dots, S_{63}$ is HIGH, the NOR output drops to 0. If and only if all 64 bits are LOW, the output floats to $V_{DD}$ (1).
• Software Use: Powers equality checks (CMP A, B followed by JE / BEQ). If $A - B = 0$, the $Z$ flag is set, confirming $A = B$.

2. The Negative/Sign Flag ($N$ or $S$)

• Meaning: Asserted (1) if the arithmetic result is negative in two's complement.
• Physical Circuit: In two's complement representation, the most significant bit (MSB, bit 63) is the sign bit. The circuit requires zero logic gates: it is a direct copper trace tapping bit $S_{63}$ straight into the flags register: $$N = S_{63}$$

3. The Carry Flag ($C$)

• Meaning: Asserted (1) if an unsigned operation generated a carry out of the most significant bit, or if a borrow occurred during subtraction.
• Physical Circuit: The carry out of the final prefix tree stage: $$C = C_{64}$$
• Software Use: Enables multi-precision arithmetic. To add two 256-bit numbers on a 64-bit CPU, the processor executes four sequential ADC (Add with Carry) instructions, with each stage consuming the $C$ flag left behind by the preceding 64-bit addition.

4. The Overflow Flag ($V$ or $O$)

• Meaning: Asserted (1) if a signed two's complement operation produced a result that exceeds the representable range (for 64-bit signed integers, $-2^{63}$ to $+2^{63}-1$).
• Physical Phenomenon: Occurs when two positive numbers are added and produce a negative number, or when two negative numbers are added and produce a positive number.
• Physical Circuit: An XOR gate comparing the carry entering the most significant bit with the carry leaving the most significant bit: $$V = C_{63} \oplus C_{64}$$
• If $C_{63} \neq C_{64}$, signed overflow has occurred.

Datapath Multiplexing: The Complete Arithmetic Unit

An ALU is not merely an adder; it must also perform logical operations: bitwise AND, OR, XOR, NOT, and bit-shifting.

In modern silicon, these operations are computed in parallel simultaneously. When operands $A$ and $B$ arrive from the register file, they are dispatched concurrently to:

1. The 64-bit Parallel Prefix Adder/Subtractor
2. A bank of 64 parallel AND gates
3. A bank of 64 parallel OR gates
4. A bank of 64 parallel XOR gates
5. A barrel shifter circuit

                   Operand A [63:0]    Operand B [63:0]
                          │                   │
             ┌────────────┼───────────────────┼────────────┐
             │            │                   │            │
           ┌─▼────────────▼─┐               ┌─▼────────────▼─┐
           │ Prefix Adder / │               │  Bitwise Logic │
           │   Subtractor   │               │ (AND, OR, XOR) │
           └───────┬────────┘               └───────┬────────┘
                   │                                │
                   │  ┌─────────────────────────────┘
                   ▼  ▼
           ┌──────────────────┐
           │ Output 64-to-1   │◄─── ALU Opcode Control Lines
           │   Multiplexer    │     (from Instruction Decoder)
           └────────┬─────────┘
                    │
                    ▼
          ALU Result Bus [63:0] ──► Register Writeback

While the adder is evaluating its carry tree, the simple AND, OR, and XOR gates resolve their results in a single gate delay ($15\text{ ps}$).

The final output is selected by an output multiplexer controlled by opcode wires arriving from the CPU's Instruction Decoder. The decoder simply asserts the address of the desired operation, and the multiplexer passes the selected 64-bit result onto the CPU's internal datapath to be written back into a register on the rising edge of the clock.

Through this breathtaking choreography of Boolean algebra, modular arithmetic, and logarithmic tree routing, the ALU converts raw electric voltage into the unstoppable computational powerhouse of modern civilization.