The Adder

Addition in columns

Think how we add two large numbers on a sheet of paper: we set them neatly one under the other, aligned to the right, and add digit by digit, starting from the units and moving left. When the sum of a column runs past a single digit — 7 + 5 = 12, say — we write the units below (2) and “keep in mind” the tens digit (1), which we pass on as a carry to the neighbouring column. We are so used to this dance of the pencil on paper that we forget its deeper nature: it is an infallible mechanical algorithm, probably the first we ever learned as children.

In the binary world the rules are the same but considerably simpler, since we have only two digits at our disposal: 0 and 1. The possible situations can be counted on one hand. 0 plus 0 gives 0. 0 plus 1 gives 1. And 1 plus 1 gives 2. But since two cannot be written with a single binary digit, it becomes 10: we write 0 in the current column and send 1 as a carry into the column on the left. If three 1s meet (two added plus a carry from before), we get 3, that is binary 11: we write 1 and pass 1 on. The whole arithmetic of addition fits into these few clear rules, and that simplicity is exactly what makes it possible to build it out of electric circuits.

The half adder

Let us look first at the simplest possible column: the first on the right, the units column, which receives no carry from behind. It needs two inputs (the two bits to be added) and offers two outputs: the digit that stays in place (the sum) and the digit that leaves towards the left (the carry). The circuit able to do this is called a half adder — “half” because it is equipped to solve only half the problem, lacking a third input for a possible incoming carry.

If we examine the outputs we recognise the logic gates at once: the carry must be 1 only when both inputs are 1 (that is, 1 + 1 = 10), which matches the AND gate perfectly. The sum digit is 1 when exactly one of the inputs is 1 (0+1 or 1+0), but becomes 0 when both are 1 (in which case the sum is 10, so the units digit is 0). This behaviour is called EXCLUSIVE-OR (often shortened to XOR): that is, “either one or the other, but never both at once”.

The EXCLUSIVE-OR gate is not an exotic part standing on its own: it can easily be assembled from the AND, OR and NOT gates we already know: (a OR b) AND NOT (a AND b). Being everywhere in arithmetic and cryptography, however, engineers give it a graphic symbol of its own.

The full adder

All the other columns of a number, lying to the left of the first position, are more demanding: they must add not only their own two bits (a and b) but also the carry arriving from the neighbouring column on the right. So we have three inputs to add. The circuit that solves this whole task is called a full adder.

Seen logically, the answer is harmonious: the sum digit must be 1 when we have an odd number of inputs equal to 1 (a single 1, or all three). The carry that leaves must be 1 if at least two of the three inputs are active. These are exactly the “parity” and “majority” functions we met in the exercises of the previous lesson. We need invent nothing out of nothing: pure logic moulds itself onto arithmetic.

In practice a full adder is elegantly built by chaining two half adders: the first adds a to b, and the second adds the carry coming from the right to the partial result. If either of those two additions produces a carry (it cannot happen in both at once), a simple OR sends that carry on to the next column.

Chaining them together

A full adder deals with a single column. If we set eight such blocks side by side and connect the carry leaving each one to the input of its left-hand neighbour, we obtain a device able to add two numbers of eight bits each (that is, two bytes). This arrangement is called a ripple carry — it is the embodiment, in silicon and copper, of school addition on paper.

Notice, though, the hidden constraint that appears here: the second column cannot know its final result until the first has finished computing its carry; the third must wait for the second, and so on, like a row of dominoes falling one after another. For large numbers, of 64 bits, that wave of waiting would be far too slow. In real processors, engineers use ingenious “carry look-ahead” schemes that guess the carries of all the columns in parallel, sacrificing room on the chip (more transistors) to gain speed. It is the first instance of an eternal trade-off in computers: the exchange between time and space.

Subtraction, with the same circuit

We might think that subtracting numbers needs a completely different circuit. Fortunately, mathematics offers us a brilliant escape: subtraction can be turned into addition. Think of a clock face with 12 hours: if it is nine o’clock and you want to know what time it was three hours ago, you can turn the hand back by 3, arriving at six. But you can just as well turn the hand forward by 9 (since 12 − 3 = 9) and you will land at exactly the same point, six o’clock. In a circular system, subtracting a value is identical with adding the difference up to the end of the cycle.

On eight bits we can represent 256 different values (from 0 to 255). Subtracting a number is therefore equivalent to adding what it lacks to reach 256. That complementary number is astonishingly easy to obtain in binary: we simply invert all the bits (0 becomes 1 and 1 becomes 0) and add 1 at the end. The technique is called two's complement. With that simple convention, numbers beginning with 1 are read as negative, letting us cover the range from −128 to +127 without needing any physical minus sign in the wires.

Our adder can now subtract with no new parts at all: when we want subtraction we invert the bits of the second term with plain NOT gates and inject a 1 into the initial carry of the first column. Press the “subtraction” button in the figure above: the circuit stays the same, yet it computes perfect subtractions.

Overflow

Eight bits offer exactly 256 possible combinations and not one more. When we add two large numbers and the result passes 255, the ninth bit — the carry leaving the last column on the left — simply has no room left in the byte and falls into the void, like a car’s odometer resetting to 00000 after 99999. This situation is called overflow . It is not a manufacturing defect but an inevitable consequence of working with a fixed width of bits. At the edge of any finite system, arithmetic curves round into a circle.

Processors do not ignore the event, though: they catch the fallen bit in a special indicator (a “flag”) that the programmer can inspect. Depending on intent, overflow may signal a serious error or be used deliberately, exactly like the turning of a clock.

The adder we have built reckons at the speed of light, but it suffers from one major weakness: it is completely without memory. If we cut off its inputs, the result at the output evaporates in an instant. The circuits so far live purely in the immediate present, with no recollection of the past. To build a real computer we absolutely need circuits able to keep a result in mind even after the cause that produced it has gone. In the next lesson we shall give memory life through a surprising idea: a loop in which the output of a circuit returns to its own input.