The bitshift operators take two arguments, and looks like:
x << n
x >> n
where x can be any kind of int variable or char variable,
and n can be any kind of int variable.
Think of x as a bitstring (since it is), and n as the number of bits to shift left or write. You should be familiar with shifting, because it's a fundamental operation in, say, insertion sort.
There are sneaky ways to shift bits even if you use other types (say, float). This involves tricks with casting. We'll see this at the end of these notes.
Let's look at an example. Suppose x is a char and contains the following 8 bits.
If we shift left by 2 bits, the result is:
When you shift left by k bits then, bi + k = bi. If i + k > N, then bit bi fell off the left edge. If i < K, then bi = 0. In other words the low K bits are all 0's.
That means that as you shift left, the bits on the high end (to the left) fall off, and 0 is shifted in from the right end.
This bit contributes 2i to the overall value.
If you shift left by K bits, then this 1 will now appear as bi + K. Thus, that bit contributes 2i + K, which is, of course, equal to 2i * 2K (using law of exponents), i.e., it's multiplying by 2K.
Of course, this multiplication can only go so far. For unsigned int, when the first "1" falls off the left edge, the operation has overflowed. That is, you've multiplied by 2K such that the result is larger than the largest possible unsigned int.
Shifting left on signed values also works, but overflow occurs when the most significant bit changes values (from 0 to 1, or 1 to 0).
It's not nearly as obvious that shifting left in 2C would actually multiply by 2. The easiest way to view this is to think about 1C. The difference between 1C and 2C is 1. That means, if you're looking at a negative number, and focus on the bits with 0, they shift when they move to the left. Now, the correponding positive value is computed by flipping the bits (thus, those 0 bits are now 1), and effectively, you're watching 1 bits move left.
Another way to view this is to recall that 2C is equivalent to flipping the bits left of the rightmost 1. Again, if you look at the 0's left of that rightmost 1, they will eventually become 1's and they are shifting to the left.
Right shifting causes a few more problems. When shifting to the right for unsigned int, bits fall off the least significant end, and 0's are shifted in from the most significant end. This is also known as logical right shift (logical shifts shift in 0's).
However, with signed int, the story is different. What right shifting does depends on the compiler. One possibility is to shift in 0's, just as unsigned int's do. If this occurs, then you divide by 2K (if you're shifting K bits), but only for non-negative values of x. For negative values, you've made it positive, and it no longer makes sense that this operation is equivalent to dividing by 2K.
Compilers may also shift in the sign bit. Thus, if x is negative, the sign bit is 1, so 1's are shifted from the most significant end. If x is non-negative, 0's are shifted from the most significant end. This is called an arithmetic right shift since the sign bit is shifted in. Thus, if you shift right by K bits, then K 1's or K 0's are shifted in.
Let's look at an example of this. Suppose x looks like before:
Let's shift right by 3 bits. If the sign bit is shifted in, the result is:
If 0's are shifted in, the result is:
int x = 3 ; int n = 2 ; x << n ; cout << x << endl ;What does it print? The answer is 3. The answer is NOT 12.
Why is that? Suppose you were asked to sum x + y. What will happen to x or y? Of course, you know that nothing happens to them. But then where does the sum go? A temporary value is created internally, and that value is typically used to assign to some result or printed.
The same thing happens when you do x << n. It creates a temporary value with a bitshifted version of x, but does not change the value of x.
So, how do you save the change? Simple, just assign it.
x = x << n ;
cout << x << endl ;
This prints out 12 (if x is 3 and n is 2).
There's an equivalent way to do this. Use the <<=; operator.
Nearly every C binary operator has a version with ='s after it.
x <<= n ;
cout << x << endl ;
Trick the compiler.
How do you do that?
Make it think the float is an int.
Here's the wrong way to do it. You can try to cast the float to an int. But if you do this, you have two problems. First, casting creates a temporary value. Even if you save this, the bits will actually change. A float that's cast to an int causes the fractional part to be truncated, and what's more, it changes the representation from IEEE 754 to 2C.
Nevertheless, casting is the right idea. Here's how to do it.
float x ;
int * ptr = (int *) (& x) ;
*ptr <<= n ; // left shift by n bits
You make a pointer that points to the float with same number
of bytes, then you shift based on the dereferenced pointer. At
this point, when we manipulate *ptr, we're actually manipulating