From Logic Gates to Arithmetic

A processor is built from one kind of switch repeated billions of times. Wire a few switches together and you get a gate that computes AND, OR or NOT. Wire gates together and you get a circuit that adds two numbers. Stack enough of those circuits and you have a machine that can run any program.

Nothing in it thinks. A CPU is very fast plumbing, and every capability it has is a circuit somebody designed. This topic shows the plumbing, from a single gate to a 64-bit adder, and prices each step: why an addition takes one tick, why a division takes many, and what physically limits how much work fits in a tick at all.

Switches and Gates

A transistor is a switch that one voltage opens or closes, letting current through or blocking it. A handful of them wired together make a gate, a circuit whose output is a fixed function of its inputs. NOT flips a bit: 0 becomes 1 and 1 becomes 0. AND outputs 1 only when both inputs are 1. OR outputs 1 when either input is 1. XOR, exclusive or, outputs 1 when exactly one input is 1.

One gate is enough to build all the others. NAND, an AND followed by a NOT, can be wired into NOT, AND, OR and XOR, and so into any logical function at all. This is why a chip can be made from one small pattern repeated billions of times, and why the same Boolean algebra that simplifies an if statement also simplifies a circuit.

Adding Two Bits

Adding two single bits has four cases. 0 plus 0 is 0, 0 plus 1 and 1 plus 0 are 1, and 1 plus 1 is 10 in binary: a sum bit of 0 and a carry of 1. Look at the columns in the figure and two gates appear. The sum bit is the XOR of the inputs, and the carry is their AND. Two gates make a half adder.

A full adder also takes a carry in from the column to its right, which takes two half adders and an OR gate. Chain 64 full adders so that each one's carry out feeds the next one's carry in, and the chain adds two 64-bit numbers. The figure below adds 109 and 39 in eight bits. Each adder takes one bit of each number and a carry from its right, and the sum bits read 10010100, which is 148.

Why Carries Cost Time

In a plain chain like that one, called a ripple-carry adder, each bit has to wait for the carry from the bit before it. The carry out of bit 0 settles, then bit 1 can settle, then bit 2, all the way along. The delay grows with the width: a 64-bit ripple adder waits for 64 carries in a row, and that is too slow to finish inside one clock tick.

Real adders compute the carries in parallel. Extra gates look at groups of bits at once and work out in advance whether a group will produce a carry or pass one through, so the answer arrives after a delay that grows with the logarithm of the width instead of the width itself. The price is chip area: more gates to buy less time. That is the time-space trade of Chapter 1, made in silicon.

Subtraction, Multiplication and Division

Two's complement, from Chapter 2, makes subtraction almost free. To compute a minus b, flip every bit of b, add 1, and add the result to a. Flipping bits is a row of NOT gates, and the plus 1 enters as the first carry in, so one adder circuit does both addition and subtraction.

Multiplication is shifts and adds, the same long multiplication taught in school but in binary, done by a large block of adders working in parallel. On current processors it takes about three clock ticks. Division is harder to parallelize, because each step of long division depends on the one before, and on typical processors a 64-bit integer division takes several times to an order of magnitude longer than a multiplication, according to published instruction timing tables. Compilers know this and replace division by a constant with a multiplication by a precomputed reciprocal and a shift, which gives the same answer faster.

Bitwise Operations in Your Code

The gates surface directly in every programming language as the bitwise operators: and, or, exclusive or, not, and the shifts that move bits left or right. They are the natural tool for flags packed into one integer, for masks that extract a field from a larger value, for exclusive or as a parity check, which Chapter 12 uses to detect corruption, and for hash functions that mix bits together.

In compiled code each of these operators is one instruction and takes one tick. In Python each still pays for the interpreter around it. Measured on CPython 3.15, halving an integer with floor division took about 20 nanoseconds and shifting it right by one bit took about 26: the shift was not faster, because the cost of either line is dispatch, type checks and object handling, not the arithmetic the gates perform.

The Clock and What It Costs

A clock ticks a few billion times a second, and each tick is the time allowed for signals to settle through the gates between one set of registers and the next. At 3 gigahertz a tick lasts about a third of a nanosecond. In that time light in a vacuum travels about 10 centimetres, and signals in on-chip wires travel less. A circuit that is physically too long, or too many gates deep, cannot finish within a tick.

So two physical facts set the ceiling on work per tick: distance, and the heat released every time billions of transistors switch. The last topic of this chapter shows how heat ended the era of ever-faster clocks. In the systems you run, the cost shows up as arithmetic that is not all the same price: in a tight compiled loop, one integer division can take as long as a dozen or more additions, and it is the instruction that shows up in the profile.