Adding column by column in hardware with a chain of full adders — the ripple-carry adder and why it is O(n).
Binary addition works exactly like the decimal addition you learned in school, except each column holds only 0 or 1 and a column overflows as soon as its total reaches 2. When that happens it writes a sum digit and passes a carry to the next column on the left.
Each column adds three bits: a bit from A, a bit from B, and the carry-in from the column to its right. A full adder produces two outputs: Sum = A XOR B XOR Cin (the digit written down) and Carry = (A AND B) OR (Cin AND (A XOR B)) (handed to the next column). The carry-out is 1 whenever at least two of the three inputs are 1.
A ripple-carry adder wires n full adders in a row, feeding each column's carry-out into the next column's carry-in, starting from the rightmost (least-significant) bit with carry-in 0. It is the simplest possible adder to build.
Add 0110 (6) + 0101 (5), right to left:
carry: 0 1 0 0
A : 0 1 1 0
B : 0 1 0 1
----------------
sum : 1 0 1 1 = 11
col0: 0+1+0 = 1, carry 0
col1: 1+0+0 = 1, carry 0
col2: 1+1+0 = 0, carry 1 <- spills over
col3: 0+0+1 = 1, carry 0A AND B) and "propagate" (A XOR B) signals, instead of waiting for the ripple. It costs far more gates but cuts the delay from O(n) toward O(log n) — the standard speedup in real CPUs.