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


  • 0
    H

    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.


Log in to reply
 

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