Absolute Beginner's Guide to Bit Shifting?

Question

I've been attempting to learn C in my spare time, and other languages (C#, Java, etc.) have the same concept (and often the same operators) ...

What I'm wondering is, at a core level, what does bit-shifting (<<, >>, >>>) do, what problems can it help solve, and what gotchas lurk around the bend? In other words, an absolute beginner's guide to bit shifting in all its goodness.

EDITS:

1. I removed the nonexistent (sorry, brain fart) <<< operator.
2. Thank you to everyone for the help and explanations; I hope they help the next guy with this question as much as they helped me. (And please keep 'em coming and add on to this!)

Answer 1

Wikipedia does a great job of explaining it: http://en.wikipedia.org/wiki/Bitwise_operation

Answer 2

Two very good posts on Wikipedia should explain all..

• Bitwise Operation
• Logical Shift

Answer 3

Lets say we have a single byte:

0110110

Applying a single left Bitshift gets us:

1101100

The leftmost zero was shifted out of the byte, and a new zero was appended to the right end of the byte.

The bits don't rollover, they are discarded, that means if you left shift 1101100 and then right shift it, you won't get the same result back.

Shifting left by N is equivalent to multiplying by 2^N.

Shifting right by N is (if you are using ones compliment) is the equivalent of dividing by 2^N and rounding to zero.

Bitshifting can be used for insanely fast multiplication and division, provided you are working with a power of 2, almost all low level graphics routines use bitshifting.

For example, way back in the olden days, we used mode 13h (320x200 256 colors) for games. In Mode 13h, the video memory was laid out sequentially per pixel. That meant to calculate the location for a pixel, you would use the following math:

memoryOffset = (row * 320) + column

Now, back in this day and age, speed was critical, so we would use bitshifts to do this operation.

However, 320 is not a power of two, so to get around this we have to find out what is a power of two that added together makes 320:

(row * 320) = (row * 256) + (row * 64)

Now we can convert that into left shifts:

(row * 320) = (row << 8) + (row << 6)

For a final result of:

memoryOffset = ((row << 8) + (row << 6)) + column

Now we get the same offset as before, except instead of an expensive multiplication operation, we use the two bitshifts...in x86 it would be something like this (note, its been forever since I've done assembly):

mov al, 320; 2 cycles
mul [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles

Total: 28 cycles

Vrs

mov al, [row]; 2
mov di,[row]; 2
shl al, 6;  2 
shl di, 8;  2 
add al, di; 2
add [column], ax; 2

12 cycles.

Yes, we would work this hard to shave off 16 cpu cycles.

Ok, back in the modern days... something more useful now would be to use bitshifting to store two 8-bit values in a 16-bit integer, for example, in c#:

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

Answer 4

First, learn how "ordinary" binary arithmetic works. Learn how to convert between decimal, hexadecimal, octal and binary. Learn how to add and subtract numbers in binary. Then learn at least about 2nd complement (the most common way to represent signed numbers in binary; other ways that C supports are signed-magnitude and 1st complement, but you can skip them in first iteration). Then learn how to negate a number in 2nd complement. Then learn about bit-wise operators (and, or, not, xor; in C & | ~ ^). Once you have learned all of that, the definition and purpose of bit-shifting operators will become self-illuminating.

Sorry, there's no easy way to learn a new concept.

What they're good for: quickly computing a bunch of nontrivial functions. For example: this link or the FXT book.

Pitfalls: as usual, C has a lot of undefined behavior. For example, shifting 16-bit quantity by 17 bits is technically UB. Shifting signed numbers is tricky and may give unexpected results and/or UB. And whatever you do, don't "optimize" expressions such as x*4 into x<<2. Today's compilers are smart.

EDIT: "C supports" might be misleading. The C standard allows the given C implementation to arbitrarily implement one of: 2nd complement, 1st complement or signed-magnitude. The implementation will commonly choose the native format of the underlying platform which is 2nd complement on x86 and AMD64 (and many others), the CPU architecture which you're most probably using :) [In fact, I don't know of any CPU that uses 1st complement or signed-magnitude -- probable some DSPs.]

Answer 5

One gotcha is that the following is implementation dependent (according to the ANSI standard):

char x = -1;
x >> 1;

x can now be 127 (01111111) or still -1 (11111111).

In practice, it's usually the latter.

Answer 6

The bit shifting operators do exactly what their name implies. They shift bits. Here's a brief (or not-so-brief) introduction to the different shift operators.

The Operators

• >> is the arithmetic (or signed) right shift operator.
• >>> is the logical (or unsigned) right shift operator.
• << is the left shift operator, and meets the needs of both logical and arithmetic shifts.

All of these operators can be applied to integer values (int, long, possibly short and byte or char). In some languages, applying the shift operators to any datatype smaller than int automatically resizes the operand to be an int.

Note that <<< is not an operator, because it would be redundant. Also note that C and C++ do not distingiush between the right shift operators. They provide only the >> operator, and the shifting behavior is implementation defined.

---

Left shift (<<)

Integers are stored, in memory, as a series of bits. For example, the number 6 stored as a 32-bit int would be:

00000000 00000000 00000000 00000110

Shifting this bit pattern to the left one position (6 << 1) would result in the number 12:

00000000 00000000 00000000 00001100

As you can see, the digits have shifted to the left by one position, and the last digit on the right is filled with a zero. You might also note that shifting left is equivalent to multiplication by powers of 2. So 6 << 1 is equivalent to 6 * 2, and 6 << 3 is equivalent to 6 * 8. A good optimizing compiler will substitute shifts for multiplications when possible.

Non-circular shifting

Please note that these are not circular shifts. Shifting this value to the left by one position (3,758,096,384 << 1):

11100000 00000000 00000000 00000000

results in 3,221,225,472:

11000000 00000000 00000000 00000000

The digit that gets shifted "off the end" is lost. It does not wrap around.

---

Logical right shift (>>>)

A logical right shift is the converse to the left shift. Rather than moving bits to the left, they simply move to the right. For example, shifting the number 12:

00000000 00000000 00000000 00001100

to the right by one position (12 >>> 1) will get back our original 6:

00000000 00000000 00000000 00000110

So we see that shifting to the right is equivalent to division by powers of 2.

Lost bits are gone

However, a shift cannot reclaim "lost" bits. For example, if we shift this pattern:

00111000 00000000 00000000 00000110

to the left 4 positions (939,524,102 << 4), we get 2,147,483,744:

10000000 00000000 00000000 01100000

and then shifting back ((939,524,102 << 4) >>> 4) we get 134,217,734:

00001000 00000000 00000000 00000110

We cannot get back our original value once we have lost bits.

---

Arithmetic right shift (>>)

The arithmetic right shift is exactly like the logical right shift, except instead of padding with zero, it pads with the most significant bit. This is because the most significant bit is the sign bit, or the bit that distingishes positive and negative numbers. By padding with the most significant bit, the logical right shift is sign-preserving.

For example, if we interpret this bit pattern as a negative number:

10000000 00000000 00000000 01100000

we have the number -2,147,483,552. Shifting this to the right 4 positions with the arithmetic shift (-2,147,483,552 >> 4) would give us:

11111000 00000000 00000000 00000110

or the number -134,217,722.

So we see that we have preserved the sign of our negative numbers by using the arithmetic right shift, rather than the logical right shift. And once again, we see that we are performing division by powers of 2.

Answer 7

Bitwise operations, including bit shift, are fundamental to low-level hw or embedded programming. If you read a spec for a device or even some binary file formats, you will see bytes, words, and dwords, broken up into non-byte aligned bitfields, which contain various values of interest. Accessing these bit-fields for reading/writing is the most common usage.

A simple real example in graphics programming is that a 16-bit pixel is represented as follows:

  bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1  | 0 |
      |       Blue        |         Green         |       Red          |

To get at the green value you would do this:

 #define GREEN_MASK  0x7e0
 #define GREEN_OFFSET  5
 // read grean
 uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Also common is using bit shifts for fast multiplication and division by powers of 2.

 i <<= x;  // i *= 2^x; 
 i >>= y;  // i /= 2^y;