The Machine · Chapter 3
How does it add?

Watch the opener · 1:31

Transcript

How does it add? In binary, one plus one is one, zero. But our gates each give a single bit.

So I bet adding needs a special circuit, something smarter than a gate. But adding two bits only has four cases. That's a table, like any gate's.

Zero plus zero is zero. One plus zero is one, and so is zero plus one. And one plus one is one, zero. Write every answer as two bits: a sum on the right, a carry on the left. The sum is one when the bits differ. That's an XOR gate. The carry is one only when both are one. That's an AND gate. Give both gates the same two inputs. Try one plus one: carry one, sum zero. Two gates, two bits: one, zero.

So that's how it adds, no special part! An XOR gate for the sum and an AND gate for the carry make a half adder.

But the next column over adds three bits: its own two, plus the carry. Set two numbers in the adder below, and watch the carry ripple left.

Chapter 2 built XOR: a gate whose output is 1 exactly when its two inputs differ. That phrasing sounds abstract, but “they differ” is another way of saying “one is 0 and one is 1,” which is the same as saying the sum of the two bits is 1 without a carry. You already have the sum half of the simplest adder; this chapter adds the carry and then scales the pattern.

3.1 Combinational logic

Every circuit in this chapter is combinational: its output is a pure function of its present inputs, with no memory of any earlier input. Feed it the same inputs twice and it gives the same output twice. This is in contrast to the memory circuits that Chapter 4 will build from these same gates, which can remember an earlier input. Here the output is always and only a function of right-now inputs. That constraint makes the circuits much easier to reason about: trace the signal forward, and you know everything.

3.2 Writing numbers with bits

A bit holds only 0 or 1; several bits together can hold a larger number. Decimal places have weights 1,10,100,… from right to left. Binary places double instead: 1,2,4,8,… , the powers of two. For example, 1101₂ = 1× 8 + 1× 4 + 0× 2 + 1× 1 = 13. The subscript 2 marks a binary numeral. Its rightmost bit is bit 0, the least significant bit, worth one; the leftmost occupied place is the most significant bit. Thus 10₂ means one two and zero ones, or 2.

The Python circuits use lists in the opposite order, starting with bit 0 so addition can follow the carry from low places to high ones. to_bits(13, 4) produces [1, 0, 1, 1]: the entries have weights 1,2,4,8. The helper from_bits converts that list back to 13. These helpers translate notation; the gates do the arithmetic.

3.3 The half adder

The half adder is the simplest binary adder. It takes two single bits and returns two bits: a sum and a carry. Work through the four possible inputs and the outputs fall into place. When both inputs are 0 the sum is 0 and there is no carry. When exactly one input is 1 the sum is 1 and there is still no carry. When both inputs are 1 the sum wraps around to 0 but there is a carry of 1, encoding the fact that 1 + 1 = 2 = 10₂.

The sum column is exactly the XOR truth table, and the carry column is exactly the AND truth table. The half adder needs no new gate. XOR from Chapter 2 pays off immediately.

Figure 3.2 shows the gate-level circuit: XOR feeds the sum output and AND feeds the carry output, both driven by the same two inputs.

Example 3-1. Half adder: sum is XOR, carry is AND

def half_adder(a: int, b: int) -> tuple[int, int]:
    """Sum and carry of two bits: the sum is XOR, the carry is AND."""
    return xor_(a, b), and_(a, b)1

• xor_ gives the sum, and_ gives the carry; both computations share the same two inputs, exactly as the figure shows.

3.4 The full adder

The half adder has one weakness: it cannot accept a carry coming in from a less-significant bit position. Chaining two half adders together fixes this. The first half adder adds a and b, producing an intermediate sum and an intermediate carry. The second half adder adds that intermediate sum to the carry-in c_in, producing the final sum and a second carry. Because at most one of the two intermediate carries can be 1 at a time, a simple OR of the two carries gives the correct carry-out. If a+b already produced a carry, its intermediate sum is 0, so adding c_in cannot produce the second carry; if it did not, the carry-in may be the one that creates a carry.

The code follows that construction directly: two half-adder calls feeding one OR gate.

Example 3-2. Full adder: two half adders and an OR

def full_adder(a: int, b: int, cin: int) -> tuple[int, int]:
    """Add three bits (a, b, and a carry-in) from two half adders and an OR."""
    sum1, carry1 = half_adder(a, b)1
    sum2, carry2 = half_adder(sum1, cin)1
    return sum2, or_(carry1, carry2)2

• the two half_adder calls, one for a+b, one for the intermediate sum plus c_in
• or_ merges the two partial carries into the final carry-out; because both cannot be 1 simultaneously, OR is sufficient

3.5 The ripple-carry adder

A single full adder handles one bit position. To add two n-bit numbers, chain n full adders in series: feed the carry-out of each stage into the carry-in of the next. The lowest stage receives a carry-in of 0; the highest stage’s carry-out becomes the extra top bit of the result. That is the complete ripple-carry adder. Figure 3.4 shows a four-stage chain drawn so that the carry path is impossible to miss.

The interactive version needs the in-browser runtime.

Example 3-3. A ripple adder: follow the carry from bit zero

def ripple_add(a_bits: list[int], b_bits: list[int]) -> list[int]:
    """Add two equal-length bit lists (least significant bit first). The result
    is one bit wider than the inputs: the final carry becomes the top bit."""
    carry = LOW
    out = []
    for a, b in zip(a_bits, b_bits):
        bit, carry = full_adder(a, b, carry)
        out.append(bit)
    out.append(carry)
    return out

For a sum that needs the extra carry, call:

ripple_add(to_bits(11, 4), to_bits(6, 4))

It returns [1, 0, 0, 0, 1], still least-significant first. Read in written-number order, that is 1011₂ + 0110₂ = 10001₂; from_bits gives 17. The fifth bit preserves the carry that would otherwise be lost from a four-bit result.

The cost of the ripple-carry design is its latency. Before bit position k can produce a valid carry, every stage to its right must have settled. For wide adders, the critical path runs the full width of the carry chain, one full adder deep per bit. Real processors replace this design with carry-lookahead or prefix adders that compute carries in parallel, but the ripple-carry adder is the right starting point because the logic is transparent: you can trace the carry with your finger.

3.6 Choosing an operation: the multiplexer and the ALU

An arithmetic-logic unit does not just add. It computes several candidate results, one per operation, and then selects one based on a control signal called the opcode. The device that does the selecting is a multiplexer.

A 2-to-1 multiplexer takes two data inputs and one select line. When the select is LOW it passes the first input; when HIGH it passes the second. Built from NOT, AND, and OR, it is a two-way switch made of gates.

Example 3-4. 2-to-1 multiplexer: select one of two inputs

def mux(sel: int, a: int, b: int) -> int:
    """Two-to-one multiplexer: a when sel is LOW, b when sel is HIGH."""
    return or_(and_(not_(sel), a), and_(sel, b))1

• when sel is LOW, not_(sel) is HIGH, so the first AND passes a and the second is blocked; when sel is HIGH the situation reverses and b comes through.

Three 2-to-1 muxes compose into a 4-to-1 mux. With a 2-bit opcode the 4-to-1 mux selects one of four inputs, which is exactly what a minimal ALU needs: one output per supported operation.

The ALU below supports four operations: add (opcode 00), bitwise AND (01), bitwise OR (10), and bitwise XOR (11). It computes all four results for every bit position and uses a 4-to-1 mux per bit to pick the winner.

Example 3-5. A minimal ALU: four operations, one two-bit opcode

def alu(op_hi: int, op_lo: int, a_bits: list[int], b_bits: list[int]) -> list[int]:
    """Tiny ALU: 00 add, 01 and, 10 or, 11 xor; pad bitwise results to add width."""
    add = ripple_add(a_bits, b_bits)1
    a = a_bits + [LOW]
    b = b_bits + [LOW]
    return [mux4(op_hi, op_lo, add[i], and_(a[i], b[i]), or_(a[i], b[i]),2
                 xor_(a[i], b[i])) for i in range(len(add))]

• ripple_add produces the addition result, which is one bit wider than the inputs because of the final carry-out
• for each bit position, one mux4 picks among the add result, the AND result, the OR result, and the XOR result according to the two opcode bits

Arithmetic can compute, but it cannot remember; the next main chapter gives the machine state. An optional division read comes first for readers who want to build another operation from the adder.

Exercises

• Make the ripple adder subtract: negate the second number in two’s complement (invert every bit, then add one) and add as before.
• The ALU’s two-bit selector chooses one of four operations. What would a fifth operation cost?