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

for example:

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

next iteration:

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.