Bitshift Operators

Introduction

Did you think that << or >> was invented in C++? That these operators did not exist in C? If so, you're wrong. These operators did exist in C. Of course, they were not the stream insertion and extraction operators. These were bitshift operators.

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.

Restrictions

Like bitwise operators, you can only perform bitshift operations on x (the left argument) on certain types: in particular, any kind of int and any kind of char.

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.

Operator <<

The operation x << n shifts the value of x left by n bits.

Let's look at an example. Suppose x is a char and contains the following 8 bits.

b7 b6 b5 b4 b3 b2 b1 b0
1 1 0 0 0 1 1 1

If we shift left by 3 bits, the result is:

b7 b6 b5 b4 b3 b2 b1 b0
0 0 0 1 1 1 0 0

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.

Left shifting is multiplying by 2K

If you shift left on an unsigned int by K bits, this is equivalent to multiplying by 2K. Why is that? Fix your attention to a bit that has a value of 1. Suppose bi = 1 prior to shifting.

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.

Operator >>

Left shifting generally creates few problems regardless of type. 0's are shifted from the least significant end, and bits fall off the most significant end.

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:

b7 b6 b5 b4 b3 b2 b1 b0
1 1 0 0 0 1 1 1

Let's shift right by 3 bits. If the sign bit is shifted in, the result is:

b7 b6 b5 b4 b3 b2 b1 b0
1 1 1 1 1 0 0 0

If 0's are shifted in, the result is:

b7 b6 b5 b4 b3 b2 b1 b0
0 0 0 1 1 0 0 0

Shifting Doesn't Change Values

Here's one of those rather annoying facts about C, that is perfectly consistent with the way C does things. Suppose x = 3 and n = 2. What does the following code do?
  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 ; 

Shifting Bits for other types

Suppose you wish to shift left on float variables. The compiler will complain that you can't do this. Bitwise/bitshift operations aren't defined on float variables. So, what can you do?

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 x.

Summary

Some facts: