Home · part 1 of 9

From gates to an ALU

One full adder from five gates, four of them chained into a 4-bit adder, and why the carry ripples.

One full adder, five gates

Inside a CPU, the circuit that adds is called the arithmetic logic unit, or ALU, and its heart is one small cell repeated once per bit: the full adder. It adds two bits and a carry coming in from the right, and produces a sum bit and a carry going out to the left. Written as gates: sum = A ⊕ B ⊕ cin and carry-out = A·B + cin·(A ⊕ B). That is two XOR gates, two AND gates and one OR gate. Tap the inputs below to watch them work.

Notation: A ⊕ B is XOR (1 exactly when the inputs differ), A·B is AND, + inside a gate equation is OR, and ¬A is NOT. Everywhere else, + is ordinary addition.

The highlighted row is the current input; ⊕ is XOR. The first XOR and AND form a half adder; the rest fold in the carry.

Four of them add 4-bit numbers

One full adder adds a single pair of bits. To add two 4-bit numbers you use four of them, one per bit, and they work the way you add on paper: write the two numbers one above the other, add each pair of digits starting from the right, and carry a 1 into the next place whenever a pair adds up to 2 or more. Each place, called a column, gets its own full adder. Its A and B inputs are that column's two bits, its carry-in is whatever the column on its right carried out, and its carry-out feeds the column on its left. That carry wire is the only connection between the adders. The carry-in of the rightmost column is tied to 0, and the carry-out of the leftmost column becomes the C flag. Below, the four adders are drawn as boxes marked FA (short for full adder), with the same sum written out as long addition beside them. Tap one of the FA boxes to open it and see its five gates working on that column; press ripple to watch the carries settle one column at a time, which is why the top bit is always the last to be ready.

tap A or B bits to change the sum, tap an FA box to open it

The same sum written as long addition. The red row is the carry into each column. The carry out of bit 3 lands in the C column on the left, as the fifth digit of the answer would on paper; in the machine it becomes the C flag.

Bitwise operations are simpler still: AND, OR and XOR need one gate per bit position and no carry at all, so no column ever waits for another. An ALU is these circuits side by side, with a few control wires choosing which one's output reaches the result.

Where this leads