Half-adder

Gate-Level CPU Simulator

Start with the easiest possible question: how do you add two single bits?

Take the obvious first guess. XOR is the only gate that returns 1 exactly when its inputs differ — which feels close to addition. Try it on the four cases:

$a$	$b$	XOR (proposed sum)	actual $a + b$
0	0	0	0
0	1	1	1
1	0	1	1
1	1	0	2

Three rows match. The fourth doesn't, and it can't: $1 + 1 = 2$ , but a single output bit holds 0 or 1, not 2. The fix isn't to swap XOR for some other gate — it's to give the adder a second output bit, so it can represent values from 0 to 3.

Call the two outputs sum (the units bit) and carry (the next column over). With two outputs the table fills in:

$a$	$b$	sum	carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Look at the sum column: it's 0110 — that's XOR. Look at the carry column: it's 0001 — that's AND. So one XOR and one AND, fed the same two inputs, give us a one-bit adder. Our first instinct (XOR) wasn't wrong — it was incomplete. Adding AND for the carry closes the gap.

def half_adder(a, b):
    """Add two single bits. Returns (sum_bit, carry_out)."""
    s = XOR(a, b)
    c = AND(a, b)
    return s, c

Half-addersum = a ⊕ b · carry = a · b

demo:

set inputs with a / b, then send a pulse to watch the signal travel

Why two gates?

A single XOR works for three of the four input cases — but on 1 + 1 it returns 0, not 2. The reason: in binary 1 + 1 = 10, and a one-bit output has nowhere to put that second digit. The AND gate catches it. It fires only when both inputs are 1, which is exactly when the sum overflows. So XOR carries the units bit, AND carries the carry bit, and they run side by side — one gate-delay, both bits at once. Try the 1 + 1 = 10 (carry!) demo above and watch the two gates light up together.

Why "half"?

Half because there's nowhere for a carry from the previous column to come in. Two inputs in, two bits out — but no incoming carry, which is fine for the rightmost column of an addition and broken everywhere else. Every other column needs three inputs. The full-adder is what gives you the third one.

Why XOR specifically? Couldn't a different gate work for the sum?

No — XOR is the only 2-input gate whose truth table is 0110, which is exactly the sum column. The other named gates have different tables: OR is 0111 (so it'd wrongly say 1+1=1); NAND is 1110 (wrongly says 0+0=1); and so on. There are 16 possible 2-input gates total — exactly one of them matches 0110. The XOR/AND choice isn't a design preference. It's the only pair of gates whose truth tables match the half-adder's truth table.

Could you build the half-adder out of NAND gates only?

Yes — and chips often do. NAND is universal: every other gate can be built from NANDs alone. NOT(a) = NAND(a, a); AND is two NANDs (one to compute, one to invert); XOR takes about four. With sharing, the whole half-adder lands at around five NAND gates total. That's more gates than the XOR + AND version, but every gate is the same primitive cell — and NAND is the cheapest gate to fabricate in CMOS (four transistors). Same function, different vocabulary at the silicon level.

What's the half-adder for? Why bother?

It's the atomic unit of arithmetic at the gate level. Two of them stacked plus an OR gives you a full-adder (next page), which handles a single column of multi-bit addition. Chain $n$ full-adders end-to-end and you have an $n$ -bit adder. Every arithmetic operation in the CPU eventually decomposes to chains of these. Understand the half-adder and you've understood the smallest layer of the entire arithmetic stack.

Many phrasings, many angles

Five aspects of the half-adder, five phrasings each. Scan down a cluster until something clicks; once any one phrasing lands, the others retroactively make sense. Same idea as the why-block above, pulled apart into smaller pieces so your eye can pick the one that fits.

Each heading is a different facet of the half-adder. Each line under it is a different way to say the same thing about that facet. Scan down a cluster until something clicks; once any one phrasing lands, the others retroactively make sense.

Why two output bits

A single output bit holds 0 or 1, but 1+1=2 needs two digits to write down.
The half-adder's answer can be 0, 1, or 2 — three distinct values — and three distinct values can't be encoded in a single bit.
Adding two bits can produce a result that overflows a single bit; you need a second wire to carry the rest.
1+1 evaluates to 2, which in binary is 10 — two digits, and two digits need two output wires.
A 2-input gate produces 1 bit of output, but the half-adder's image has more values than 1 bit can hold; two parallel gates are required.

XOR's role (the sum bit)

XOR's truth table is 0110, which exactly matches the sum column of the half-adder.
XOR fires when its two inputs differ — producing 1 for (0,1) and (1,0), and 0 otherwise — which is exactly the sum-bit pattern.
Of all 16 possible 2-input gates, XOR is the unique one whose truth table is 0110 — only XOR fits the sum.
The sum bit of a + b is a ⊕ b because XOR's behavior ("exactly one input is 1") matches what "the units digit of a binary sum" means.
XOR alone gets three of four input cases correct (0+0, 0+1, 1+0); only 1+1 falls through, and that's exactly the case AND picks up.

AND's role (the carry bit)

AND's truth table is 0001, which exactly matches the half-adder's carry column.
AND fires only when both inputs are 1 — the precise case where a carry is generated.
Of all 16 possible 2-input gates, AND is the unique one whose truth table is 0001 — the only gate fit for the carry bit.
The carry bit of a + b is a · b because AND is high exactly when 1+1=10 happens, the only case requiring a carry.
AND captures what XOR alone can't: the case where the sum overflows a single bit.

Parallel construction (one gate-delay)

XOR and AND fire simultaneously on the same input pair — neither waits for the other.
The half-adder's two output bits settle in one gate-delay, not two — the two gates are computationally independent.
The gates share their inputs but produce independent outputs, so there is no serial dependency between them.
"Parallel" here is literal silicon parallelism: both gates exist on the chip and propagate at the same time.
One operand pair in, two output bits out, one delay — the parallel structure is what makes the half-adder fast.

What the half-adder is for

The half-adder is the smallest non-trivial circuit in arithmetic; every multi-bit adder is built from it.
Two half-adders plus an OR gives a full-adder, which accepts an incoming carry and is the building block of multi-bit addition.
Chain n full-adders end-to-end and you have an n-bit adder; chain 32 of them and you have what the CPU uses for 32-bit arithmetic.
Every arithmetic operation in the CPU eventually decomposes to chains of full-adders, which decompose to half-adders — the half-adder is the atomic unit.
The same decomposition pattern (split the operation into bitwise functions of independently-determinable output bits, compute in parallel) generalizes to every other ALU primitive.