Logic Gates to ALU: How a CPU Physically Computes Math

When you write int sum = a + b; in C, or ADD eax, ebx in assembly, there’s a chain of abstraction between that instruction and the silicon executing it. The CPU has no concept of numbers in the way we do — no notion of magnitude, no decimal system, no counting. What it has is transistors: microscopic switches that either pass current or don’t.

Two voltage states. High ( $\approx$ 3.3V or 5V, logical 1) and Low ( $\approx$ 0V, logical 0). Every computation a processor performs — adding integers, comparing pointers, encrypting a packet — reduces to routing those two states through carefully arranged networks of switches. The abstraction that bridges voltages and arithmetic is Boolean logic.

The Building Blocks: Gates

Three primitive operations define Boolean logic: AND, OR, and NOT. From these, every other logical function can be constructed.

A useful thing to know upfront: NAND alone is sufficient. Every AND, OR, NOT, and XOR can be built from NAND gates exclusively. This property — called functional completeness — is why NAND is the gate most commonly implemented in CMOS silicon. Fabrication simplifies when you only need one gate type, which is why you’ll see “NAND implementation” in most physical logic descriptions even when the boolean algebra uses AND/OR/NOT notation.

For arithmetic specifically, the most important gate is XOR (Exclusive-OR). XOR isn’t primitive — it’s derived:

$A \oplus B = (A \cdot \bar{B}) + (\bar{A} \cdot B)$

(In Boolean algebra, $\cdot$ is AND and $+$ is OR — not multiplication and addition, which is a notation collision worth noting explicitly.)

XOR’s truth table:

A	B	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

Compare this to binary addition: $0+0=0$ , $0+1=1$ , $1+0=1$ , $1+1=10$ . XOR gives the correct sum bit in all four cases. The only case where XOR fails is $1+1$ , where it outputs $0$ instead of $10$ — it computes the sum bit correctly but discards the carry. That’s what we need to capture next.

The Half Adder

A Half Adder adds two single bits and produces two outputs: the sum bit and a carry bit.

$S = A \oplus B$ $C_{out} = A \cdot B$

The carry is 1 only when both inputs are 1 — exactly AND. Two gates, two wires in, two wires out.

The “half” in the name is the limitation: there’s no input for a carry arriving from a previous stage. That makes it useless for adding multi-bit numbers in a chain, because bit position 1’s carry needs to feed into bit position 2’s calculation.

The Full Adder

A Full Adder adds three bits: $A$ , $B$ , and a carry-in $C_{in}$ . It’s built by chaining two Half Adders:

First Half Adder: compute $A \oplus B$ (intermediate sum) and $A \cdot B$ (first carry)
Second Half Adder: compute $(A \oplus B) \oplus C_{in}$ (final sum) and $(A \oplus B) \cdot C_{in}$ (second carry)
OR the two carry outputs together to get $C_{out}$

In Boolean algebra:

$S = (A \oplus B) \oplus C_{in}$ $C_{out} = (A \cdot B) + (C_{in} \cdot (A \oplus B))$

The OR on the carry is correct because both Half Adder stages can’t both generate a carry simultaneously (that would require three 1-bits summing to at least 3, but the maximum is $1+1+1=11_2$ , carry 1 from one stage only). So the two carry signals are mutually exclusive in the worst case, and OR captures whichever one fires.

The Ripple Carry Adder

Chain eight Full Adders and you have an 8-bit adder. The $C_{out}$ of bit position 0 connects to the $C_{in}$ of bit position 1, and so on up to bit 7. The first $C_{in}$ is wired to ground (logic 0). The final $C_{out}$ is the overflow/carry flag.

This is called a Ripple Carry Adder because the carry signal propagates sequentially from LSB to MSB. Each Full Adder must wait for the previous stage’s carry before it can produce a valid output.

That sequential dependency is the architecture’s main weakness. In an $N$ -bit ripple carry adder, the worst-case path — a carry that propagates all the way from bit 0 to bit $N-1$ — takes $2N$ gate delays. For an 8-bit adder that’s 16 gate delays; for a 64-bit adder, 128. At GHz clock rates, that latency is unacceptable.

Modern CPUs use Carry Lookahead Adders (CLA) instead. A CLA precomputes, for each bit position, whether that position will generate a carry ( $G_i = A_i \cdot B_i$ ) or propagate an incoming carry ( $P_i = A_i \oplus B_i$ ). With those signals available in parallel, the carry into any bit position can be computed directly without waiting for preceding stages. A 4-bit CLA computes all carries simultaneously in a constant number of gate delays, and 64-bit adders are built as trees of CLA blocks. The ripple carry design is what you implement to understand the concept; CLA is what ends up in silicon.

Subtraction via Two’s Complement

A separate subtractor circuit would waste silicon. Instead, the adder handles subtraction through a mathematical trick: Two’s Complement.

In Two’s Complement representation, negating a number means inverting all bits and adding 1. So $A - B$ becomes $A + (-B) = A + (\bar{B} + 1)$ .

Both steps map directly onto the existing adder hardware:

Bit inversion uses XOR with a control signal. Recall that $B \oplus 0 = B$ and $B \oplus 1 = \bar{B}$ . Route all $B$ bits through XOR gates with a shared control wire:

control = 0: B passes unchanged → addition
control = 1: B is inverted → first step of negation

Adding 1 is free: wire control directly to the first Full Adder’s $C_{in}$ . When control = 1, the initial carry-in is 1 — exactly the +1 Two’s Complement requires.

One control wire. No extra adder stages. The same eight Full Adders that add can subtract.

Overflow Detection

A detail the basic ALU description often skips: how do you know when the result is wrong?

For 8-bit unsigned arithmetic, the valid range is 0–255. For 8-bit signed (Two’s Complement), it’s −128 to 127. Adding 105 + 42 = 147 looks fine unsigned, but as a signed result it’s wrong — 147 exceeds 127 and wraps into negative territory. That’s a signed overflow.

The hardware test for signed overflow is elegant: overflow occurs when the carry into the sign bit (bit 7) differs from the carry out of the sign bit:

$\text{Overflow} = C_{in,7} \oplus C_{out,7}$

One XOR gate on two carry wires. Real ALUs expose this as the overflow flag (OF in x86), which is distinct from the carry flag (CF). The simulation below tracks the final carry out but doesn’t implement overflow detection — adding it means comparing carry before and after the last Full Adder stage.

The Logic Operations

The “L” in ALU isn’t decorative. A real ALU also performs bitwise logical operations — AND, OR, XOR — which operate on all 8 bits independently with no carry chain at all. The operation selector (a 2-bit or wider opcode) routes the inputs through the appropriate gate network. In the simulation, we keep it to ADD and SUB, but a production ALU would multiplex between arithmetic and logic results based on the opcode, then feed the selected output to the register file.

Simulation in C

The code below simulates the 8-bit ALU at gate level — no + or - operators, only the bitwise equivalents of physical gates: ^ for XOR, & for AND, | for OR.

#include <stdio.h>
#include <stdint.h>

/*
 * Simulate one Full Adder cell.
 * All parameters represent single-bit values (0 or 1) stored in uint8_t.
 */
void full_adder(uint8_t a, uint8_t b, uint8_t c_in,
                uint8_t *sum, uint8_t *c_out)
{
    uint8_t axb     = a ^ b;
    *sum            = axb ^ c_in;
    uint8_t carry1  = a & b;
    uint8_t carry2  = axb & c_in;
    *c_out          = carry1 | carry2;
}

/*
 * 8-bit ripple-carry ALU.
 * control=0 → ADD, control=1 → SUB (via Two's Complement inversion + carry-in=1)
 */
uint8_t alu_8bit(uint8_t A, uint8_t B, uint8_t control)
{
    uint8_t result = 0;
    uint8_t carry  = control;   /* carry-in to bit 0: 0 for ADD, 1 for SUB */

    for (int i = 0; i < 8; i++) {
        uint8_t bit_a = (A >> i) & 1;
        uint8_t bit_b = (B >> i) & 1;

        /* XOR with control wire: inverts B bits when subtracting */
        uint8_t modified_b = bit_b ^ control;

        uint8_t sum_bit, next_carry;
        full_adder(bit_a, modified_b, carry, &sum_bit, &next_carry);

        carry  = next_carry;
        result |= (sum_bit << i);
    }

    return result;
}

int main(void)
{
    uint8_t a = 105, b = 42;

    printf("ADD: %u + %u = %u\n", a, b, alu_8bit(a, b, 0));
    printf("SUB: %u - %u = %u\n", a, b, alu_8bit(a, b, 1));

    /* Underflow: 5 - 10 wraps to 251 in unsigned, which is -5 in signed 8-bit */
    uint8_t small = 5, big = 10;
    printf("SUB (underflow): %u - %u = %u  (-5 in signed 8-bit)\n",
           small, big, alu_8bit(small, big, 1));

    return 0;
}

ADD: 105 + 42 = 147
SUB: 105 - 42 = 63
SUB (underflow): 5 - 10 = 251  (-5 in signed 8-bit)

The underflow case is worth dwelling on. alu_8bit(5, 10, 1) computes $5 + \overline{10} + 1 = 5 + 245 + 1 = 251$ in unsigned 8-bit arithmetic, and the carry out of bit 7 is 1 (discarded by uint8_t). Interpreted as signed, 251 is $-5$ in Two’s Complement — which is the mathematically correct answer. The “wrapping” isn’t a hardware failure; it’s exactly what Two’s Complement is supposed to do.

There’s no addition happening in that loop in any abstract sense. Each iteration extracts one bit, routes it through five Boolean operations, and passes a carry wire to the next iteration. Run it eight times and the bit pattern in result happens to be the binary representation of the sum. The arithmetic is a property of the pattern, not something the silicon knows about.

That gap between “gate operations” and “arithmetic” is what computer architecture is built on. Understanding it at this level makes higher abstractions — pipeline hazards, out-of-order execution, superscalar dispatch — considerably less mysterious, because you can see what the hardware is actually constrained by.