i
Adding One Is Adding a Carry daniel-hromada ()


Adding One Is Adding a Carry

Our algorithm increment is not a special case: to add 1, put a carry of 1 into the lowest position, then let every position run a half-adder.

c0 = 1 (that is the “+1”)

for every bit bi, from right to left:
outi = bi XOR ci
ci+1 = bi AND ci

The lowest bit has it easiest: b XOR 1 = NOT b — it always flips. Every higher bit flips only if the carry reached it — and the carry survives only through a chain of 1s.