baumhaus.digital/Studium Generale/Short History of the Learning Machine/Logic, Gates, Machine/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 cici+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.