Add two numbers using bit manipulation

Question

I'm working on the following practice problem from GeeksForGeeks:

Write a function Add() that returns sum of two integers. The function should not use any of the arithmetic operators (+, ++, –, -, .. etc).

The given solution in C# is:

public static int Add(int x, int y)
{
    // Iterate till there is no carry  
    while (y != 0)
    {
        // carry now contains common set bits of x and y
        int carry = x & y;

        // Sum of bits of x and y where at least one of the bits is not set
        x = x ^ y;

        // Carry is shifted by one so that adding it to x gives the required sum
        y = carry << 1;
    }
    return x;
}

Looking at this solution, I understand how it is happening; I can follow along with the debugger and anticipate the value changes before they come. But after walking through it several times, I still don't understand WHY it is happening. If this was to come up in an interview, I would have to rely on memory to solve it, not actual understanding of how the algorithm works.

Could someone help explain why we use certain operators at certain points and what those totals are suppose to represent? I know there are already comments in the code, but I'm obviously missing something...

Answer 1

At each iteration, you have these steps:

carry <- x & y   // mark every location where the addition has a carry
x <- x ^ y       // sum without carries
y <- carry << 1  // shift the carry left one column

On the next iteration, x holds the entire sum except for the carry bits, which are in y. These carries are properly bumped one column to the left, just as if you were doing the addition on paper. Continue doing this until there are no more carry bits to worry about.

Very briefly, this does the addition much as you or I would do it on paper, except that, instead of working right to left, it does all the bits in parallel.