← All Posts 📖 The Human DeveloperEarly access → what makes developers irreplaceable in the age of AI

How Your CPU Does Math

From x * y to transistors: the arithmetic your programming language pretends is primitive

Reading time: ~15 minutes

You wrote x * y. A number came back. You moved on.

That result came from a sequence of additions. Those additions came from a cascade of logic gates. Those gates are transistors switching between two voltage levels — roughly 0V and 3.3V — in patterns that, when arranged just right, implement the rules of arithmetic. The * operator in your source code is not primitive. It's a shorthand for a reduction chain that goes all the way to physics.

This bothers me more than it probably should. I've written x * y ten thousand times without thinking about the fact that multiplication isn't in the instruction set at a fundamental level. It's compiled down. The ALU is an addition machine with some boolean logic bolted on, and everything else — multiplication, division, exponentiation, floating-point trig — is a pattern of adds, shifts, and comparisons that runs in a loop or gets unrolled into a circuit.

Here's the full chain.

Binary: before the CPU can do math

Before any arithmetic can happen, numbers need a physical form. The CPU stores them as bits — positions in a register that are either 0 or 1, corresponding to two distinct voltage levels. An eight-bit register holds eight such positions. A 64-bit register holds 64.

Unsigned integers are straightforward: the bit pattern 00001010 is $0 \cdot 128 + 0 \cdot 64 + \ldots + 1 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 0 \cdot 1 = 10$. Positional notation in base 2, same idea as decimal.

Signed integers are where it gets elegant. The obvious approach — dedicate the high bit as a sign flag, store the magnitude in the rest — seems natural but creates a mess. You'd have two representations of zero (+0 and -0), and addition of signed numbers would need special cases depending on the signs.

Two's complement solves all of this. To negate a number: flip all the bits, then add 1. That's it. The beautiful consequence is that addition works identically for signed and unsigned numbers. The hardware doesn't need to know the sign. You just add, and the encoding handles it.

Overflow wraps. In a 4-bit two's complement register, 7 is 0111. Add 1: you get 1000, which represents -8. You asked for 8 and got -8. That's not a bug in the encoding — that's the encoding being honest that 8 doesn't fit in four signed bits. C compilers will warn you. Rust won't compile the unchecked version. The behavior is defined by the bit width you chose.

The gate level: how addition actually works

An adder is the fundamental circuit. Everything else is built on top of it.

Start with the simplest case: adding two single bits. A and B. There are four combinations:

A B Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

The Sum column is XOR. The Carry column is AND. These are not analogies — those are literally the two gates you need. This is a half adder: two inputs, two outputs, four transistors.

The problem is that real addition carries. If you're adding the second bit position and there's already a carry coming in from the first position, a half adder can't handle it. You need a full adder: three inputs (A, B, carry-in), two outputs (sum, carry-out).

S   = A XOR B XOR Cin
Cout = (A AND B) OR (B AND Cin) OR (A AND Cin)

Build 64 of these in a chain — each one's carry-out feeding the next one's carry-in — and you have a ripple-carry adder that adds two 64-bit numbers.

The carry ripple is the performance bottleneck. A 64-bit ripple-carry adder has a critical path 64 gates long — each gate takes a few hundred picoseconds, so you're waiting roughly 20 nanoseconds for the carry to propagate across all positions before the output is stable. For CPUs running at 3 GHz (one clock every 333 ps), this is unacceptable.

The fix is carry-lookahead. Instead of waiting for the carry to ripple, compute all carries simultaneously using parallel combinational logic. If you define: - Generate: $G_i = A_i \wedge B_i$ (this bit position generates a carry regardless of carry-in) - Propagate: $P_i = A_i \vee B_i$ (this position propagates an incoming carry)

Then the carry into position $i+1$ is: $C_{i+1} = G_i \vee (P_i \wedge C_i)$. Expand this recursively and you can compute all carries in $O(\log n)$ gate delays instead of $O(n)$. More gates, but faster. Modern ALUs use carry-lookahead (or variations like carry-select) and can add 64-bit numbers in a handful of gate delays — under 1 ns.

Here's a ripple-carry adder in software. It's illustrative of the hardware, not a practical implementation:

def half_adder(a: int, b: int) -> tuple[int, int]:
    return a ^ b, a & b  # sum, carry

def full_adder(a: int, b: int, cin: int) -> tuple[int, int]:
    s1, c1 = half_adder(a, b)
    s2, c2 = half_adder(s1, cin)
    return s2, c1 | c2  # sum, carry-out

def ripple_carry_add(x: int, y: int, bits: int = 8) -> int:
    result, carry = 0, 0
    for i in range(bits):
        a = (x >> i) & 1
        b = (y >> i) & 1
        s, carry = full_adder(a, b, carry)
        result |= s << i
    return result  # overflow discarded; carry out is lost

fn full_adder(a: u8, b: u8, cin: u8) -> (u8, u8) {
    let sum = a ^ b ^ cin;
    let cout = (a & b) | (b & cin) | (a & cin);
    (sum, cout)
}

fn ripple_carry_add(x: u8, y: u8) -> u8 {
    let mut result = 0u8;
    let mut carry = 0u8;
    for i in 0..8 {
        let a = (x >> i) & 1;
        let b = (y >> i) & 1;
        let (s, c) = full_adder(a, b, carry);
        result |= s << i;
        carry = c;
    }
    result  // wraps on overflow, like hardware
}

Multiplication is shift-and-add

With addition in hand, multiplication is a pattern you've probably done by hand on paper: multiply by each digit separately, shift left by its position, sum the partials.

In binary, this simplifies dramatically. Multiplying by a single bit is trivial: if the bit is 1, include the shifted value; if it's 0, don't. So a * b becomes: for each bit of b, if it's set, add a shifted left by that bit's position.

Naively that's $O(n)$ additions where $n$ is the value of the multiplier. The smarter version — Russian peasant multiplication, or binary multiplication, or shift-and-add, depending on where you learned it — gets to $O(\log n)$:

result = 0
while b > 0:
    if b is odd:
        result += a
    a <<= 1   # double a (shift left)
    b >>= 1   # halve b  (shift right)

Each iteration: if the low bit of b is set, add a to the result, then double a and halve b. The loop runs once per bit of b. The connection to hardware is direct: the shift operations are free at the circuit level (you're just routing wires to different positions), and the conditional additions are the actual work.

def peasant_multiply(a: int, b: int) -> int:
    result = 0
    while b > 0:
        if b & 1:          # low bit set: this power of 2 contributes
            result += a
        a <<= 1            # double: shift left
        b >>= 1            # halve: shift right
    return result

fn peasant_multiply(mut a: u64, mut b: u64) -> u64 {
    let mut result = 0u64;
    while b > 0 {
        if b & 1 == 1 {    // low bit set
            result += a;
        }
        a <<= 1;           // double
        b >>= 1;           // halve
    }
    result
}

uint64_t peasant_multiply(uint64_t a, uint64_t b) {
    uint64_t result = 0;
    while (b > 0) {
        if (b & 1) result += a;  /* bit test: is this power of 2 active? */
        a <<= 1;                 /* left shift = double */
        b >>= 1;                 /* right shift = halve */
    }
    return result;
}

Hardware multipliers — Wallace trees, Dadda multipliers — are parallelised versions of this exact algorithm. Instead of running the additions sequentially in $O(\log n)$ steps, they use a tree of carry-save adders to compute all the partial products simultaneously. The depth of the tree is $O(\log n)$; each level uses one row of adders; the whole multiplication completes in a handful of clock cycles rather than $O(n)$ additions.

The MUL instruction in your CPU is not a primitive operation any more than a subroutine call is. It's a Wallace tree, unrolled in silicon.

Division: subtract until you can't

Division runs the other direction. Integer division $a \div b$ is asking: how many times can you subtract $b$ from $a$ before going negative?

The direct version:

quotient = 0
remainder = a
while remainder >= b:
    remainder -= b
    quotient += 1

That's $O(a/b)$ subtractions — terrible for large quotients. The fast version mirrors peasant multiplication: find the largest power-of-two multiple of $b$ that fits in a, subtract it, mark that bit in the quotient, repeat. $O(\log^2(a/b))$ operations.

Modern hardware dividers use variants of the SRT algorithm — independently developed by Sweeney (IBM, 1957), Robertson (University of Illinois, 1958), and Tocher (Imperial College London, 1958). SRT uses a lookup table to select two or three quotient digits per cycle, dramatically reducing the number of iterations. The details involve redundant number representations and are fiddly.

The fiddliness is relevant, because Intel got it wrong.

In 1994, Intel shipped the Pentium with an SRT floating-point divider. The implementation used a programmable logic array with 2,048 cells, of which 1,066 should have been populated. Five entries that should have held the value +2 were missing — they contained zero instead. The error was in a region of the table that the designers assumed would never be reached, but could be. The result: for specific combinations of dividend and divisor, roughly 1 in 9 billion random double-precision divisions returned an answer wrong in the fourth significant digit.

Intel acknowledged the flaw but claimed it would not affect most users, initially offering replacements only to those who could prove they were impacted. The backlash was immediate. By December 1994, Intel reversed course and offered to replace all affected Pentiums on request. The pre-tax charge: $475 million. The Pentium FDIV bug, as it became known, was discovered by Thomas Nicely, a mathematics professor at Lynchburg College, who noticed inconsistencies while running code to enumerate primes and twin primes. It remains a standard case study in what happens when you get a lookup table wrong in a divider implemented in silicon.

Floating point: when addition itself gets complicated

Everything so far has been integers. For floating-point, the encoding is different and addition becomes more involved.

IEEE 754 is the standard. A 64-bit double-precision float uses: - 1 sign bit - 11 exponent bits (biased by 1023) - 52 mantissa bits (plus an implicit leading 1)

The value represented is $(-1)^S \times 1.\text{mantissa} \times 2^{\text{exponent} - 1023}$.

So 0.1 in floating point isn't actually 0.1. It's the closest value the format can represent, which is 0.1000000000000000055511151231257827021181583404541015625. The gap exists because 0.1 is a repeating fraction in binary — $1/10 = 0.0\overline{0011}_2$ — just as 1/3 is repeating in decimal. The format truncates it.

>>> 0.1 + 0.2
0.30000000000000004
>>> 0.1 + 0.2 == 0.3
False

fn main() {
    println!("{:.17}", 0.1_f64 + 0.2_f64);  // 0.30000000000000004
    println!("{}", 0.1_f64 + 0.2_f64 == 0.3_f64);  // false
}

package main
import "fmt"
func main() {
    fmt.Printf("%.17f\n", 0.1+0.2) // 0.30000000000000004
    fmt.Println(0.1+0.2 == 0.3)    // false
}

console.log(0.1 + 0.2);        // 0.30000000000000004
console.log(0.1 + 0.2 === 0.3) // false

Floating-point addition is not just addition. To add two floats with different exponents, you first have to align them — shift the smaller mantissa right until the exponents match, then add, then normalise the result back to the canonical $1.xxx \times 2^n$ form, then round to fit the 52-bit mantissa. Each step is its own circuit. Floating-point addition is slower than integer addition not because the math is different but because the alignment and normalisation hardware takes more gate delays.

The special cases

IEEE 754 includes a few exceptional values that are not bugs:

Denormals (subnormals): numbers too small for the normal exponent range, encoded with a zero exponent and non-zero mantissa. They exist to preserve a property you probably take for granted: a - b == 0 if and only if a == b. Without denormals, there would be a gap between zero and the smallest normal positive float. Two distinct values in that gap would subtract to zero — a violation that would break any numerical algorithm relying on that invariant. Denormal arithmetic is slower on most hardware because it requires special handling (and some CPUs historically flushed-to-zero instead, which is fast but mathematically wrong).

NaN and Infinity: 1.0 / 0.0 is positive infinity. 0.0 / 0.0 is NaN (Not a Number). NaN != NaN — always, by spec. This is the format's way of signalling that the computation has left the domain of representable numbers. These are not implementation accidents. They're defined in the standard because operations that produce undefined results need some representation, and propagating NaN through a computation is more useful than crashing.

If you've ever debugged a NaN that appeared three steps after the actual problem, this is why: NaN propagates silently through arithmetic, so the first invalid operation might be far from where you noticed.

The reduction hierarchy

Every arithmetic operation your code performs compiles down through a strict tower:

POWER(a, n)
    → O(log n) × MULTIPLY

MULTIPLY(a, b)
    → O(log b) × ADD  [shift-and-add]

DIVMOD(a, b)
    → O(log²(a/b)) × SUB

ADD/SUB
    → O(1) XOR, AND gates  [carry-lookahead adder]

XOR, AND
    → transistors switching voltages

The ** operator in Python is not a primitive. Neither is *. Neither is /. They're each a compiled reduction to the level below, and at the bottom of the chain are transistors.

This was literally the hardware situation in 1972. The Intel 8008 had no multiply instruction. To multiply, you ran a loop of shifts and adds in software — exactly the peasant algorithm above, in assembly. The MUL instruction came later, but it didn't change what the hardware was doing. It just moved the loop from your code into microcode, and eventually into dedicated silicon (the Wallace tree). The algorithm is the same. The transistors just run it in parallel now instead of sequentially.

What this means for your code

Understanding this chain doesn't change what you write day to day. You're not going to reimplement * as a loop of adds.

But it does change how you think about performance claims. When someone says "this operation is O(1)", they mean O(1) in the machine-word arithmetic model — where a 64-bit add and a 64-bit multiply both count as single operations. That model is accurate for fixed-width integers at hardware speed. It breaks down for big integers (Python int is arbitrary precision — a thousand-bit multiply is not O(1)) and for floating-point operations where alignment and normalisation add real latency.

And when you hit a floating-point bug — 0.1 + 0.2 != 0.3, a NaN propagating through your ML pipeline, a slow path caused by denormals — you now know where to look. The representation is binary, the encoding is IEEE 754, the exponent alignment is lossy, and the special cases are part of the spec.

The * operator returns a number. But there was nothing atomic about how it got there.

The next layer down: why does it work?

Everything in this post reduces to addition. The question I've glossed over is: why does that work?

Why is multiplication just iterated addition? Why does the shift-and-add algorithm give the right answer? The answer is algebraic — multiplication is defined as the unique structure-preserving map that sends 1 to the multiplicand, and addition is the primitive it's defined over. That definition, and the chain of constructions it sits inside — from two elements and a partial operation all the way to complex numbers — is the subject of the next post.

I'm writing a book about what makes developers irreplaceable in the age of AI. Join the early access list →

Naz Quadri once spent an afternoon convinced he'd found a bug in floating-point addition before remembering that 0.1 is a repeating binary fraction. He blogs at nazquadri.com. Rabbit holes all the way down 🐇🕳️.

Further Reading