Notebooks · posts/building-a-four-bit-adder-out-of-nand-gates

Building a four-bit adder out of NAND gates

Adam Zettel · September 22, 2026 · written with an agent

A NAND gate wires into NOT, AND, OR and XOR. Those make a half adder, two half adders make a full adder, and four full adders in a row give 11 + 7 = 18. The program is built in five steps (rungs), each tested against the full truth table of the circuit it adds; the last checks all 256 sums of two four-bit numbers.

s = a \oplus b \oplus c_{in}, c_{out} = ab + c_{in} (a \oplus b)

Bits here are the numbers 0 and 1, a gate is a function of its inputs, and a wire is a variable holding a bit. That models a circuit at the level of logic gates, above transistors and below an instruction set.

The last rung draws three pictures: the wiring of one column (one full adder), a timing diagram of that column as its three inputs count from 000 to 111, and the sum 11 + 7, where the carry has to pass through all four columns, one full-adder carry delay (two gate levels) each. That delay is what makes this design slow, and it is what a carry-lookahead adder removes.

Look inside this program

Atlas
The program’s map: every function and which calls which.
There’s no recorded run of this program yet.

Shift+Enter in a cell runs it and moves to the next. Running a cell runs every cell above it too, as one program.

[1]lines 23–559

from gates import (
    and_x, and_y, net2_x, net2_y, or_x, or_y, parked, wire_x, wire_y, xor_arc_x, xor_arc_y,
)

WIDTH = 4

rung "NAND, and the three gates wired from it" {
    #| NAND is an AND with its output inverted: $\overline{ab}$. Tie its two inputs
    #| together and it inverts. Invert its output and it ANDs. Invert both inputs and
    #| De Morgan's law, $a + b = \overline{\bar a \bar b}$, makes it an OR.
    #|
    #| `nand(0,0)` is 1 because $0 \cdot 0 = 0$ and the bar flips it; the other three
    #| rows follow the same way. A two-input gate has only four possible inputs, so a
    #| test of all four rows checks it completely.

    #| $\overline{ab}$.
    def nand(a, b) {
        return bxor(band(a, b), 1.0)
    }
    #| $\bar a$: a NAND with both inputs tied together.
    def gate_not(a) {
        return nand(a, a)
    }
    #| $ab$: a NAND with the bar taken off again.
    def gate_and(a, b) {
        return gate_not(nand(a, b))
    }
    #| $a + b = \overline{\bar a \bar b}$: a NAND of the two inverses.
    def gate_or(a, b) {
        return nand(gate_not(a), gate_not(b))
    }

    show nand(0.0, 0.0)
    show nand(1.0, 1.0)

    test "NAND is the AND of its inputs, inverted, in all four rows" {
        assert_near(nand(0.0, 0.0), 1.0, 0.0)
        assert_near(nand(0.0, 1.0), 1.0, 0.0)
        assert_near(nand(1.0, 0.0), 1.0, 0.0)
        assert_near(nand(1.0, 1.0), 0.0, 0.0)
    }
    test "NOT, AND and OR built from NAND agree with the operations they name" {
        assert_near(gate_not(0.0), 1.0, 0.0)
        assert_near(gate_not(1.0), 0.0, 0.0)
        for a to 2 {
            for b to 2 {
                assert_near(gate_and(a, b), band(a, b), 0.0)
                assert_near(gate_or(a, b), bor(a, b), 0.0)
            }
        }
    }
}

rung "XOR: on when the two inputs differ" {
    #| $a \oplus b = (a + b)\,\overline{ab}$: at least one input is on, and not both.
    #| Three of the gates above, in series.
    #|
    #| Adding two bits gives a sum that is their XOR and a carry that is their AND,
    #| so XOR is the last gate an adder needs.

from gates import (
    and_x, and_y, net2_x, net2_y, or_x, or_y, parked, wire_x, wire_y, xor_arc_x, xor_arc_y,
)

WIDTH = 4

rung "NAND, and the three gates wired from it" {
    #| NAND is an AND with its output inverted: $\overline{ab}$. Tie its two inputs
    #| together and it inverts. Invert its output and it ANDs. Invert both inputs and
    #| De Morgan's law, $a + b = \overline{\bar a \bar b}$, makes it an OR.
    #|
    #| `nand(0,0)` is 1 because $0 \cdot 0 = 0$ and the bar flips it; the other three
    #| rows follow the same way. A two-input gate has only four possible inputs, so a
    #| test of all four rows checks it completely.

    #| $\overline{ab}$.
    def nand(a, b) {
        return bxor(band(a, b), 1.0)
    }
    #| $\bar a$: a NAND with both inputs tied together.
    def gate_not(a) {
        return nand(a, a)
    }
    #| $ab$: a NAND with the bar taken off again.
    def gate_and(a, b) {
        return gate_not(nand(a, b))
    }
    #| $a + b = \overline{\bar a \bar b}$: a NAND of the two inverses.
    def gate_or(a, b) {
        return nand(gate_not(a), gate_not(b))
    }

    show nand(0.0, 0.0)
    show nand(1.0, 1.0)

    test "NAND is the AND of its inputs, inverted, in all four rows" {
        assert_near(nand(0.0, 0.0), 1.0, 0.0)
        assert_near(nand(0.0, 1.0), 1.0, 0.0)
        assert_near(nand(1.0, 0.0), 1.0, 0.0)
        assert_near(nand(1.0, 1.0), 0.0, 0.0)
    }
    test "NOT, AND and OR built from NAND agree with the operations they name" {
        assert_near(gate_not(0.0), 1.0, 0.0)
        assert_near(gate_not(1.0), 0.0, 0.0)
        for a to 2 {
            for b to 2 {
                assert_near(gate_and(a, b), band(a, b), 0.0)
                assert_near(gate_or(a, b), bor(a, b), 0.0)
            }
        }
    }
}

rung "XOR: on when the two inputs differ" {
    #| $a \oplus b = (a + b)\,\overline{ab}$: at least one input is on, and not both.
    #| Three of the gates above, in series.
    #|
    #| Adding two bits gives a sum that is their XOR and a carry that is their AND,
    #| so XOR is the last gate an adder needs.