Adding Two Numbers With Bitwise and Shift Operators

Here it is:

int add(int x, int y) {

int a, b;

do {

a = x & y; b = x ^ y; x = a << 1; y = b;

}while(b);

return b;

}

While I was thinking about this as to why this makes sense, I found that it indeed makes sense.

When we get both 1’s and shift them left – it means that during addition, there will be a carry to the left and the current position becomes zerop (since both are 1s.)

When we xor the numbers, we have the places as 1’s that just show 1 without any carry. If we again do an and of the anded value and the xor‘ed value, then what we are essentially doing is adding the carried bits in the current positions. Doing a xor again will add up those places that dont generate a carry. Places that generate a carry will be taken care of during the and operation. So, what we now have is the recently generated carries which will be dealt again in the next run of the loop. This goes on until there are no carries generated – i.e the and operation results in zero.

In short, the algorithm deals with two components – the positions that generate a carry and the positions that don’t generate a carry. In each run, the newly generated carrys will be added to the corresponding positions.

Once the addition is done, multiplication is just repeated addition. This is a nice example of a divide and conquer strategy – multiplication is repeated addition.

As far a multiplication is concerned, the key is to go through the bits of one number and it is 1, then we add the other number to the sum. As we proceed to the left, we keep multiplying the other number by 2 so that when we encounter a 1 in the first number the candidate to be added to the sum is equal to the other number shifted so many times as the position of the 1 in the first number. The following function will make it clear.

int multiply(int x, int y) {
int m=1, z =0;

while(x>=m && y) {

if (x &m) z=add(y,z);

y <<= 1; m<<= 1;
}
}

return z;

Advertisements

4 thoughts on “Adding Two Numbers With Bitwise and Shift Operators

  1. how can u say all the codes above are correct?
    if u executed those .i hope those may not work.so check once and post again.

    thank you

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s