# Share my solution using "XOR" and "AND"

• The Problem is a simple carry-adder question in digital circuit;

``````    class Solution {
public:
int getSum(int a, int b) {
int carry=a&b;
int result=a^b;
while(carry!=0){
int carry_t=carry<<1;
carry=carry_t&result;
result=result^carry_t;
}
return result;
}
};
``````

• Your solution is awesome, but I am kind of confused, could you please kindly explain it in details? Thanks very much.

• @ycl11761
The system of leecode discuss has changed and I miss the notification... Sorry! qAq

so,for every bit in an integer:
(1)we can calculate the carry-bit by doing &(AND) operation.because only 1+1=10 is carried;
(2) we calculate the left-bit by doing ^(XOR) operation. because 1+1=0 (ignored the carry-bit) 0+0=0, 1+0=1 0+1=1;
all the carry-bits in (1) together form an new integer: int carry,
all the left-bits in (2) together form an new integer: int result
we see this two integer as two new integer and repeat the (1) and (2)step to get their sum until carry is 0.
Hope this is not too late.

• I find it easy to understand while two numbers are both non-negative.
Your solution also works for negative situation, but I have no clue how.
Do you have an easy way to think about?

• @clydexu
This can work in negative situation since that carry-adder also works in Two's complement.
If you think:
-2=1000 0000 0000 0000 0000 0000 0000 0010
then:
-2+-2=0000 0000 0000 0000 0000 0000 0000 0100=4 (WTF?)
The solution is wrong.
However, negative numbers are stored in Two's complement to ensure that -0=0.
Such that:
-2=1111 1111 1111 1111 1111 1111 1111 1110
Then
-2+-2=
1111 1111 1111 1111 1111 1111 1111 1100=-4
(or in detailed:
in 1st round,
result=0000 0000 0000 0000 0000 0000 0000 0000
carry=1111 1111 1111 1111 1111 1111 1111 1110(because -2 & -2=-2)
carry_t=1111 1111 1111 1111 1111 1111 1111 1100(the most left bit has been dropped)
in the 2nd round,
result=1111 1111 1111 1111 1111 1111 1111 1100=-4
carry=0
)
Hope you can get it right, and give me and up-vote~~ : )

• ``````    def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
while b != 0:
carry = (a & b) << 1
a ^= b
b = carry
return a

``````

I submit this problem with python, but get TLE with test case: a = -1 and b = 1,

• @JCKoala_py
I am not familiar with python...
But I think this is caused by python's int is not 32 bit length.
in c++, a or b will just left shift to sth. like 1000 0000 0000 0000 0000 0000 0000 0000 and then go to zero.
I guess in python we dont have the time waiting it turns to zero.
I think you can fix it by just adding

``````if a==-b:
return 0
``````

at the begining.
You can say that this is a kind of bug of my code...>_<
Again, I am not familiar with python, nice try for writing it into python.
Hope you can get it right, and give me a thumbs-up~~ : )

• How to explain the corner case carry==0?

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