How to add numbers without +

Question

I was asked this question on the interview. I didn't answer and actually I don't understand how it works.

int add(int x, int y)
{
    while (y != 0)
    {
        int carry = x & y;  
        x = x ^ y; 
        y = carry << 1;
    }
    return x;
}

I'm not asking why does it produce a correct answer... First of all, why does the algorithm eventually stop? To me it's not that obvious.

In order for it to stop, carry has to become 0. Can't someone explain it in a nutshell?

Answer 1

line 1 : int carry = x & y;

line 2 : x = x ^ y;

line 3 : y = carry << 1;

if x = 1; y = 2;

Binary for each number:

0 = 00

1 = 01

2 = 10

3 = 11

for line 1 code,

& (bitwise AND) Binary AND Operator copies a bit to the result if it exists in both operands

x is 1 => 01

y is 2 => 10

result carry is => 00 (0)

for line 2 code,

^ (bitwise XOR) Binary XOR Operator copies the bit if it is set in one operand but not both.

x is 1 => 01

y is 2 => 10

result x is => 11 (3)

for line 3 code, variable carry needs to shift left for 1 bit, so now carry is 0 => 00 and shift 1 bit left means carry is now 0. The result y is (0). And while loop stop because y is 0 now.

The final result for x is 3.

Hope this will help you.

Answer 2

Let's take an example:

x=13(1101)
y=9(1001)

Loop 1:
-----------------
y!=0 -> carry=(1101)&(1001)=1001(9)  [AND Op]
x=(1101)^(1001)=0100(4)   [XOR Op]
y=carry<<1 -> y=(carry)x2=10010(18)

Loop 2:
-----------------
y!=0 -> carry=(0100)&(10010)=00000(0)
x=(0100)^(10010)=10110(22)
y=carry<<1 -> y=0

loop terminated.

therefore,x is 22.So,x^y store the sum part and x&y store the carry part,and then carry(x&y) is shifted to match the digit with x^y,and finnally XOR them and store into x. x is the resultant.