Your browser does not seem to support JavaScript. As a result, your viewing experience will be diminished, and you have been placed in read-only mode.

Please download a browser that supports JavaScript, or enable it if it's disabled (i.e. NoScript).

xor is sum without carry over & with left shift is the carry over

class Solution { public: int getSum(int a, int b) { return b == 0 ? a : getSum(a^b, (a&b)<<1); } };

''' if( b == 0 ) return a; ''' This statement is not necessary.

@steven5

it is necessary.

if we do not check b, it would be in a dead loop for getSum(1,0)

or we can put it in one line, it does not improve the performance though.

return a == 0 ? b : b == 0 ? a : getSum(a^b, (a&b)<<1);

Brilliant. Can you prove that it will always terminate?

@johnathan79717

yes. the left shift would trim 0/1 in the left and add 0 in the right, so b would become 0 in 32 left shifts. In addition, a&b would not flip 0 in b to 1.

"' if ( a == 0 ) return b; ''' Does this statement necessary?

@Vinceven

not necessary, if a=0, a^b would be b and (a&b)<<1 would be 0, so it just swaps a and b

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