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 ?
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