THE HALF ADDER two bits in, a sum and a carry out — addition's smallest atom
The smallest piece of arithmetic there is: add two single bits. The sum is their XOR (1 when they differ), and the carry is their AND (1 only when both are 1). That is a half adder — “half” because it cannot accept a carry in, only produce one out. Two gates, and the whole of addition is built by chaining them. It is where the carry is born: 1+1 overflows a single bit, and that overflow — the carry — is the one signal that must travel to make bigger numbers add.
THE TECHNIQUE sum = a ⊕ b ; carry = a & b
The demo adds two bits: XOR gives the sum, AND gives the carry — and 1+1 is where the carry first appears: live demo
HISTORY & CREDIT the half adder · two gates
“Addition is a primitive.” — it is built from two logic gates on single bits; the carry is the AND, and everything larger is those two gates, chained. cited
the atom · sum = XOR, carry = AND — the two-gate cell. “half” · no carry-in; the full adder (dart 375) adds that third input. lineage · the Boolean logic of Shannon (1937) realised in relays, tubes, then transistors.
XOR for the sum, AND for the carry — the smallest arithmetic, and the birthplace of the signal that has to travel. the half adder
RECOMMEND FOR I-13 the two-gate cell, on the compiler
On the canonical compiler, 1+1 gives sum 0 and carry 1 — the carry born from a single-bit overflow:
$ i13 run c_halfadder.i13 # sum=a^b, carry=a&b
RUN OK · 12 step(s) · peak stack 2 · call depth 0
sum = 0
carry = 1 -- 1+1 overflows one bit: the carry is born
Recommend as the batch's atom: the half adder is where the carry begins — XOR sums, AND carries — and i13 shows 1+1 producing the carry. Not a keeper (two gates computing a correct sum is correctness itself, not a supplement). The cell the whole batch chains: every larger adder is half adders wired to pass the one signal that overflow creates.