class Solution {
public:
int getSum(int a, int b) {
int sum = a;
while (b != 0)
{
sum = a ^ b;//calculate sum of a and b without thinking the carry
b = (a & b) << 1;//calculate the carry
a = sum;//add sum(without carry) and carry
}
return sum;
}
};
Share my C++ solutions,easy to understand

Calculate step by step:
class Solution { public: int getSum(int a, int b) { if (a == 0) return b; if (b == 0) return a; int sum = 0; int mask = 1; int c = 0; while (mask != 0) { int m1 = (a & mask) != 0 ? 1 : 0; int m2 = (b & mask) != 0 ? 1 : 0; if (m1 == 1 && m2 == 1) { if (c == 1) sum = mask; c = 1; } else if ((m1 ^ m2) == 1) { if (c == 1) c = 1; else sum = mask; } else { if (c == 1) { sum = mask; c = 0; } } mask <<= 1; } return sum; } };

Just a brief Proof why this loop will end within O(logn):
 We definte card(n) to be the count of 1s in n's binary representation.
 by the end of each loop, card(sum) <= min(card(a), card(b)), and the equal sign will only happens when a = b. (think about xor op)
 So if a != b, card((a & b) << 1) < min(card(a), card(b))
 If a == b, sum in next loop will be 0, and b will be 0 then, and While will end in 1 extra loop. i.e. this will only happen at the last loop.
So combining the previous, while loops at most O(logn) times.

@shenrf22 loop until carry part is 0, each loop sum of a, b is not change, his idea is excellent


@ziyangqi Hi, if a=111000, b=000111, so sum=a^b=111111, then b=(a&b)<<1=0, a=sum=111111, is card(sum)<=min(card(a), card(b)) in this loop true?

@xinyufeng16 Sorry, there was a typo, in the that line. It should be
 So if a != b, card((a & b) << 1)
Rather than  So if a != b, card(sum)
I've updated the proof.
 So if a != b, card((a & b) << 1)