My C++ code with proof


  • 11
    F

    I saw a lot of the solution just give code, while no proof is given or even discussed. So I tried to give my informal math proof of my algorithm (see proof below code) in order to show why this algorithm is correct:

    int getSum(int a, int b) {
        int ans = a ^ b;
        int c = a & b;
        while(c != 0) {
            c <<= 1;
            int ans_prim = ans ^ c;
            c = ans & c;
            ans = ans_prim;
        }
        return ans;
     }
    

    Here, variable c is carry, and ans is return value. Denote ^ is xor operation.

    Proof: the loop invariant of the while loop above code is: if there is no carry in any ith bit of a + b exists, a ^ b must equal to a + b: let's consider a example: 2 in 2 base is 10, and 1 in 2 base is 01, there is no carry in any bit of (2 + 1), that's the time (2+1) = (2^1) exists. Otherwise, if we know a ^ b and carry for each bit of a + b, let's say c, then (a ^ b) + (c<<1) must equal to a + b; Here is an example: 3 in 2 base is 11, while 1 in 2 base is 01, obviously, carry is 01 corresponding to each bit, therefore, 3+1 = 3^1+(1<<1) holds (3^1 = 2, 1<<1 = 2).

    in the beginning, "c = a & b" and "c != 0" used to check if there is any carry for a + b exists: if not, then we got result directly (case 2 + 1), if there is any carry bit (case 3+1), then "c <<= 1" used to shift and "ans ^ c" used to calculate new "bit adding result", after new adding result is calculate, we have two situation: if the result is final result, then new carry must be zero, otherwise not (according to loop invariant); so carry is updated for each bit "c = ans & c". After above step, the ans keeps the xor result of ans and carry c, carry c holds the result of new carry for each bit of (previous ans + previous c<<1), till carry is gone, then ans holds final result.


  • 0
    L

    Good explain, thank you!


  • 0
    T

    Your proof is clear, but how will it going if a or b is negative? I have tested the program and found it is right, but I am confused about the reason.


  • 0
    F

    @tranfer the number in computer is represent as complemental code, so, in computer, you can use add to implement minus operation, so even it is minus operation, you still can regard it as add and do it in the same way.


  • 0
    A

    the code and proof is very good, i experience same issue about how minus work by add, then i found this post which is very helpful, i also want to share some detail information what i found how this logic work, following are defail,
    for the minus number, the low bits is the absolute value of the number, and the all other high bits is 1, for the calculation -2 + 4, that can get transfer into
    11111111111111111111111111111110 (-1)
    +
    00000000000000000000000000000100 (4)
    =
    00000000000000000000000000000010


  • 0
    Y

    @allenj

    2's complement.

    11111111111111111111111111111111 (-1)
    +
    00000000000000000000000000000100 (4)
    =
    00000000000000000000000000000011 (3)


  • 0
    1

    @allenj non-integer


Log in to reply
 

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