Java Non Arithmetical Adder

Question

I found some code to add two numbers using XOR and AND without using any arithmetical operators.

I understand that x^y equates to the sum and that x&y equates to the carry. However I don't understand why the carry must be left shifted? My knowledge of the left bitwise shift is that is the same as multiplying by two. Why is the carry being multiplied by two?

public static int add(int x, int y) {

    // Iterate till there is no carry  
    while (y != 0)
    {
        // carry
        int carry = x & y;  

        // Sum 
        x = x ^ y; 


        y = carry << 1;
    }
    return x;

}

Any guidance appreciated.

Try with 1 and 3 and draw it on a sheet of paper. You'll see it more clearly. Basically if there are any bits that are set for both values, they will result in "bubbling" up one bit. by doing XOR and shifting the carry up, you just achive bitwise addition. — px1mp, Sep 26 '14 at 14:13
In decimal addition, if you added 66 + 55 you'd have a carry from the ones column that would be shifted onto the tens column; likewise when you add the tens column. — duffymo, Sep 26 '14 at 14:14

Tarek · Accepted Answer · 2014-09-26T15:02:15.597

Lets try with two small integer x=5 which binary equivalent is 101 and y=1, which binary equivalent is 001.

Now, why I am talking about binary or more specifically, want to deal with bits? Because XOR is a bit wise operation.

So, if you run XOR operation between x and y, the result is following:

x = x^y = 101 ^ 001 = 100 (decimal :4)

See, just XOR operation between two numbers don't give us the sum. (sum of 5 and 1 should be 6, not 4) We use the carry, to get the exact sum. Actually, the algorithm is designed in a way, so that it gives us the correct answer.

Now, lets see, how using carry in this algorithm, gives us the correct answer.

Since,

carry = x & y = 101 & 001 = 1 (decimal 1)

According to your program, y = carry << 1;

So, y will now become = 001 << 1 = 010 (decimal :2)

The loop will keep running, until y becomes zero.

If you run the loop again (since y=2 and not zero)

x = x ^ y = 100 ^ 010 = 110 (decimal :6)

carry = x & y= 100 & 010 = 0 (decimal 0)

Now, the XOR between the new value of x and y is 6 which is exactly the sum of 5 and 1. Look at carry, its value is now 0.

Our y will also become 0 now, because right shifting 0 will also give us 0. Since y is now zero, the loop will not run anymore and we got our sum by returning x!

Java Non Arithmetical Adder

1 Answers1