Bitwise carry applications

Question

Call me naive but in this area I always struggled. So I was just browsing through the code for adding two numbers without + operator and bumped into this code:

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

Now I understand, how he is calculating the carry but why y!=0 and how this code is achieving the result for adding two numbers?

Answer 1

Basics first. Exclusive or'ing two bits is the same as the bottom digit of their sum. And'ing two bits is the same as the top bit of their sum.

A | B | A&B | A^B | A+B
-----------------------
0 | 0 |  0  |  0  |  00
0 | 1 |  0  |  1  |  01
1 | 0 |  0  |  1  |  01
1 | 1 |  1  |  0  |  10

As you can see the exclusive-or result is the same as the last digit of the sum. You can also see that the first digit of the sum is only 1 when A is 1 and B is 1.

[If you have a circuit with two inputs and two outputs, one of which is the exclusive or of the inputs and the other is the and of the inputs, it is called a half adder - because there is no facility to also input a carry (from a previous digit).]

So, to sum two bits, you calculate the XOR to get the lowest digit of the result and the AND to get the highest digit of the result.

For each individual pair of bits in a pair of numbers, I can calculate the sum of those two bits by doing both an XOR and an AND. Using four bit numbers, for example 3 and 5

3 0011
5 0101
------
  0110 3^5 = 6 (low bit)
  0001 3&5 = 1 (high bit)

In order to treat the 3 and 5 as single numbers rather than collections of four bits, each of those high bits needs to be treated as a carry and added to the next low bit to the left. We can do this by shifting the 3&5 left 1 bit and adding to the 3^5 which we do by repeating the two operations

6    0110
1<<1 0010
     ----
     0100 6^(1<<1) = 4
     0010 6&(1<<1) = 2

Unfortunately, one of the additions resulted in another carry being generated. So we can just repeat the operation.

4    0100
2<<1 0100
     ----
     0000 4^(2<<1) = 0
     0100 4&(2<<1) = 4

We still have a carry, so round we go again.

0    0000
4<<1 1000
     ----
     1000 4^(4<<1) = 8
     0000 4&(4<<1) = 0

This time, all the carries are 0 so more iterations are not going to change anything. We've finished.