# 0ms AC java solution

• test cases all pass

0 ms

``````   public int getSum(int a, int b) {
if(b == 0){//没有进为的时候完成运算
return a;
}
int sum,carry;
sum = a^b;//完成第一步加发的运算
carry = (a&b)<<1;//完成第二步进位并且左移运算
return getSum(sum,carry);//
}``````

• why python get maximum recursion depth exceeded error for the input -1 1

• Sorry I don't know python

• I have thought about xor method (bit by bit), but your solution is cleaner!

• thank you!!!!!!!!

• I have same error with input (-1,1) and i guess that matter of the 0 binary digit using in python.

• The code is c++ style.

• it's better to explain a little bit about why it terminates. My opinion is: since <<1 will make at least one more 0 in the low part, so the function will at most be called for 32 times.

• Hah, my c++ solution has the same idea. The base case uses | operator, which may be easier to think of. But @lid004's code is more concise.

``````class Solution {
public:
int getSum(int a, int b) {
int base = a ^ b;
int carrier = (a & b) << 1;

//merge
//base case
if ((base & carrier) == 0)    return base | carrier;
//recursive case
return getSum(base, carrier);
}
};``````

• awesome, you are great!

• @yidongwang Thanks

• can you explain this principle?

• @TF "^" means XOR operation for two operator

"a & b << 1" recall the carry

• @johnjavabean I think python uses "unlimited" bits (not sure how many bits myself) to represent integer vs Java / Cpp uses fixed bit length for primitive types. So if you code Python in a Java / Cpp way, you won't hit the base case as expected.

• not as cleaner as this one. but just for reference.

``````  public int getSum3(int a, int b) {
//return (a|b)+(a&b);
int carry=a&b;
a=a|b;//get current bit value
if(carry==0) return a;
a=a&(~carry); // if carry is 1, then it current value need to be set to 0;
return getSum(a,carry<<1);
}
``````

• Thank you so much!

• Can be written in 1 line, but a little bit confusing.

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

• Very elegant solution! Thank you for saving me from the loop... haha

• Python can't implement tail call optimization, so change it to while loop in Python.

• I think it's actually let us to do how computer operate sum. It's about analogous circuit.

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