Adding two bits
Adding bits works like adding on paper, but a column holds only 0 or 1. 0 + 1 = 1 fits. But 1 + 1 = 2, written 10 in binary: a 0 stays here and a carry of 1 moves left.
Look at the sum bit S. It is 1 when exactly one input is 1, and 0 when the two inputs match. That is the XOR rule, so one XOR gate makes the sum: S = A XOR B.
The carry bit C is 1 only for 1 + 1, when both inputs are 1. That is the AND rule. So an AND gate, fed by the same two inputs, makes the carry: C = A AND B.
Together the XOR and the AND make a half adder: two bits in, a sum and a carry out. Read C S as a two-bit number and it always equals A + B. It is only half: it cannot take a carry in.
Adding three bits
To add longer numbers, each column must also add the carry from the column to its right. A full adder takes three bits: A, B and carry in (Cin). Three inputs give 2 × 2 × 2 = 8 rows.
Start with a half adder on A and B. Its XOR gives P = A XOR B, the sum of the first two bits. Its AND gives 1 when A and B are both 1: the first way to make a carry.
A second half adder adds Cin to P. Its XOR gives the final sum, S = A XOR B XOR Cin. Its AND gives 1 when Cin and P are both 1: the second way to make a carry.
Carry out (Cout) is 1 if either half adder made a carry. They never both do: when A and B are both 1, P is 0. So an OR gate joins them: Cout = (A AND B) OR (Cin AND (A XOR B)).
The whole table
Step through all 8 rows. S is 1 when an odd number of inputs are 1, and Cout when two or more are. Read Cout S as a two-bit number: it always counts the 1s going in.
The sums, row by row
;; step 1/9 · add-bits ;; about: Inputs A, B, Sum S, Carry C, Truth table Column addition with bits: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10 (two) S (sum) is the bit that stays in the column. C (carry) is the bit that moves one column left. A B → C S 0 0 → 0 0 0 1 → 0 1 1 0 → 0 1 1 1 → 1 0
In binary each column is worth twice the one to its right, so 10 means one two and no ones: 2. A sum that does not fit in one column sends a carry left, just like 9 + 1 = 10 in decimal. In Python, ^, & and | on the numbers 0 and 1 work as XOR, AND and OR, so s = a ^ b ^ cin and cout = (a & b) | (cin & (a ^ b)) give the same 8 rows as the circuit.