My C++ code with proof
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 belo
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:\n>     int getSum(int a, int b) {\n>         int ans = a ^ b;\n>         int c = a & b;\n>         while(c != 0) {\n>             c <<= 1;\n>             int ans_prim = ans ^ c;\n>             c = ans & c;\n>             ans = ans_prim;\n>         }\n>         return ans;\n>      }\n\nHere, variable **c** is carry, and **ans** is return value. Denote ^ is xor operation.\n\n***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).* \n\n*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.*
[]