# Share my C++ solutions,easy to understand

• ``````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;
}
};``````

• 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;
}
};``````

• talented !!!

• Is this also working with negative cases? Why?

• Yes. Because it simulates the process of addition in computer.

• why the carry always be zero at last?

• 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.

• Easy to understand? Please give a proof!

• Not easy to understand...

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

• ``````int addition(int a,int b)
{
if(b == 0)
return a;
return addition(a^b,(a&b)<<1);
}
``````

This is a good idea, but it cannot pass the complie.(

• @vdvvdd I have the same question as shenrf22 , why is b zero at last?

• awesome,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?

• +1 for Calculate step by step

• @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.

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