Decompose a and b as:
a = a1 + a2, b = b1+ b2
such that a1 & a2 is 0 and b1 & b2 is 0
that is, a1 and a2 have mutually exclusive 1 bits
the same for b1 and b2.
then a+b = (a1+b1) + (b2 + b2)
we also want to make sure that a1 and b1 have mutually exclusive 1 bits
and that a2 and b2 have exactly the same 1 bits.
the rule for a1 and b1 are: if a certain bit for a and b are the same, set it as 0
if this bit for a and b are not the same, a1 have this bit the same as a's and
b1 have this bit the same as b's.
the rule for a2 and b2 are: if a certain bit for a and b are the same, set it
the same as a or b, if this bit for a and b are not the same, set it as 0.
in summary, a1 pick the bits of a which are different than b
b1 pick the bits of b which are different than a
a2 and b2 pick the bits of a which are the same as b
a = 11010, b = 10111
then a1 = 01000, b1 = 00101
a2 = 10010, b2 = 10010
as we can see, a1 and b1 have mutually exclusive 1 bits, so
a1 + b1 = a^b
a2+b2 = (a&b) << 1
as a result a+b = a^b + ((a&b) << 1)
in this example:
a + b = 001101 + 100100
a + b = 101001 + 001000
a + b = 100001 + 010000
a + b = 110001 + 000000
the iteration can end when b reaches 0
now we need to prove that this iteration will always end
first, we notice that the number of 1 bits in b in the next iteration
has only two possibilities:
- stay the same
- become smaller
In case 1), b in the next iteration will be come 2*b
when b = b & a, in this case all the 1 bits in b are also 1 in a
then ((a&b) << 1) = 2 * b
Proving that b will finally reach 0, amounts to prove that
we will only have finitely many case 1), because each case 2) will reduce
the number of 1 bits of b by one, and b can only have finitely many 1 bits.
In case 1), b becomes 2*b, and a will become smaller since their sum is a constant.
b can only keep double itself until b has its leading 1 bit in a higher position
than a's leading 1 bit. In this case, the leading 1 bit in b will correspond with
0 bit in a, and in this case b is no longer b&a and we have a case 2).
This completes the prove that in this iteration b will always reach 0.