Binary addition

Admin 1
Viewed 461

I am trying to understand how Bitwise operators work in C, but I have an misunderstanding about the << operator.

I have the following code:

#include <stdio.h>

int Add(int x, int y);
int Add(int x, int y)
{
    while ( y != 0 )        /// Iterate till there is no carry
    {
        int carry = x & y;  /// carry now contains common set bits of x and y
        x = x ^ y;          /// Sum of bits of x and y where at least one of the bits is not set
        y = carry << 1;     /// Carry is shifted by one so that adding it to x gives the required sum
    }
    return x;
}

int main( void )
{
    printf( "%d", Add( 13, 17 ) );
    return 0;
}

If I understand correctly works like this:

First Iteration:
|=======================================|
|                                       |
|   while ( y       !=      0     )     |
|   while ( 17      !=      0     )     |
|   while ( 10001   !=      00000 )     |
|                                       |
|   c       =   x       &   y;          |
|   1       =   13      &   17          |
|   00001   =   01101   &   10001       |
|                                       |
|   x       =   x       ^   y           |
|   28      =   13      ^   17          |
|   11100   =   01101   ^   10001       |
|                                       |
|   y       =   c      <<   1           |
|   17      =   1      <<   1           |
|   10001   =   00001  <<   00001       |
|   00010   =   00001  <<   00001       |
|                                       |
|=======================================|

Second Iteration:
|=======================================|
|                                       |
|   while ( y       !=      0     )     |
|   while ( 2       !=      0     )     |
|   while ( 00010   !=      00000 )     |
|                                       |
|   c       =   x       &   y;          |
|   0       =   28      &   2           |
|   00000   =   11100   &   00010       |
|                                       |
|   x       =   x       ^   y           |
|   30      =   28      ^   2           |
|   11110   =   11100   ^   00010       |
|                                       |
|   y       =   c      <<   1           |
|   2       =   0      <<   1           |
|   00010   =   00000  <<   00001       |
|   00000   =   00000  <<   00001       |
|                                       |
|=======================================|

Then Y becomes 0 and X returns 30.

Now in the following code I have an issue:

#include <stdio.h>

int main( void )
{
    int x = 13;
    int y = x << 1; /// 11010 = 01101 << 00001
    x = 0 << 1;     /// 00000 = 00000 << 00001

    printf("y = %d\n", y ); /// 26  | 11010
    printf("x = %d\n", x ); /// 26  | 11010
    return 0;
}

Here if I understand right we shift all bits one to the left:

int y = x << 1; /// 11010 = 01101 << 00001

But what exactly happens here:

x = 0 << 1;     /// 00000 = 00000 << 00001

Does x get cleared and filled with the rezult of 0 << 1 ?

bit-shift c
2 Answers

Does x get cleared and filled with the rezult of 0 << 1 ?

x is just assigned the value of the expression 0 << 1. Zero left or right shifted by any amount remains 0.

So this means that the representation of the First and Second Iteration is correct?

It is correct, except that substitution of the old values of variables (on the lhs) is a bit confusing as in the following cases.

17      =   1      <<   1 
10001   =   00001  <<   00001

and 

2       =   0      <<   1
00010   =   00000  <<   00001

Instead depict it as: 

y      =   1      <<   1 
y      =   00001  <<   00001

and 

y       =   0      <<   1
y       =   00000  <<   00001
user_101902370

n << k is actually n * (2^k) as long as you have enough bits available to keep all of the resulting bits. So 0 << k is 0 * (2^k) = 0 whatever the (positive integer) value of k is.

Note that for usual 32 bit integers, a number on p = 17 bits or more, like 65537 (0x0001_0001), will stop behaving like the multiplication once k is greater or equal to (32+1)-p = (32+1)-17 = 16, as for example 65537 << 16 is 0x1_0001_0000 which is using 33 bits and is truncated to 0x0001_0000 = 65536.
With 65536 << 15 you may also start having strange results as the result, 0x1000_0000, is changing the left most bit, which is the sign bit if you're not using unsigned values...

user_104967100
Related