# Here is the explanation of the most voted solution with proof.

• 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:

1. stay the same
2. 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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.