Chapter 3
How does it add?

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 adder; you just have not called it that yet.

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 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.3 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.

Figure 3.3 shows the construction: two half-adder blocks 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.4 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.

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.5 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-3. 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-4. A minimal ALU: four operations, one opcode, one mux per bit

def alu(op_hi: int, op_lo: int, a_bits: list[int], b_bits: list[int]) -> list[int]:
    """A tiny ALU. The opcode (op_hi, op_lo) selects 0=add, 1=and, 2=or, 3=xor;
    every candidate result is computed and a 4:1 mux picks one per bit. The add
    result is one bit wider (its carry-out), so the bitwise results are padded
    with a LOW to match."""
    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, 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 chapter gives the machine state.

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 selector chooses one of four operations. What is the most it could choose between, and what would a fifth operation cost?