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.

Answer 2

I will try to explain it on a simple 3 bits example (you can skip this example to the actual explanation which marked in bold font and starts at Now to the way we achieve the same flow from the posted code).

Lets say we want to add x=0b011 with y=0b101. First we add the least significant bits 1+1 = 0b10

carry: x10
x:     011
      +
y:     101
      -----
       xx0

Then we add the second bits (and by the book we need to add also the carry from the previous stage but we can also skip it for later stage): 1+0 = 0b1

carry: 010
x:     011
      +
y:     101
      -----
       x10

Do the same for the third bit: 0+1 = 0b1

carry: 010
x:     011
      +
y:     101
      -----
       110

So now we have carry = 0b010 and some partial result 0b110. Remember my comment earlier that we take care of carry at some later stage? So now is this "later stage". Now we add the carry to the partial result we got (note that it is the same if we added the carry for each bit separately at the earlier stages). LSB bits addition:

NEW carry:    x00
carry:        010
             +
part. res.:   110
             -----
              xx0

Second bits addition:

NEW carry:    100
carry:        010
             +
part. res.:   110
             -----
              x00

Third bit addition:

NEW carry:      100
carry:          010
               +
part. res.:     110
               -----
new part. res.  100

Now carry = NEW carry, part. res. = new part. res. and we do the same iteration once again.

For LSB

NEW carry:    x00
carry:        100
             +
part. res.:   100
             -----
              xx0

For the second bits:

NEW carry:    000
carry:        100
             +
part. res.:   100
             -----
              x00

Third bits:

NEW carry:   1000 --> 000 since we are working with 3 bits only
carry:        100
             +
part. res.:   100
             -----
              000

Now NEW carry is 0 so we have finished the calculation.The final result is 0b000 (overflow).

I am sure I haven't discovered anything to here. Now to the way we achieve the same flow from the posted code:

The partial result is the result without the carry, which means when x and y have different bits at the same position, the sum of these bits will be 1. If the same bits are identical, the result will be 0 (1+1 => 0, carry 1 and 0+0 => 0, carry 0).

Thus partial result is x ^ y (see the properties of the XOR operation). In the posted code it is x = x ^ y;.

Now let's look at the carry. We will get carry from a single bit addition only if both bits are 1. So the bits which will set the carry bits to 1 are marked as 1 in the following expression: x & y (only the set bits at the same position will remain 1). But the carry should be added to the next (more significant) bit! Thus

carry = (x & y) << 1; // in the posted code it is y = carry << 1

And the iterations are performed unless carry is 0 (like in our example).