Starbucks-fueled Developer

Monday, February 12, 2007

Bit Shifting: What is it and Why

OK, so maybe I'm way behind the times, but I finally figured out why in the world one would ever want to shift bits. I came by this discovery after reading one of Ron Jefferies' recent posts. Pay particular attention to the color method:


private int color(int count) {
// int gray = (255 - count*4 + count/2) & 0xFF;
int gray = (255 - count*6) & 0xFF;
int rgb = (gray << 16) | (gray << 8) | (gray << 0);
return rgb;
}

The return value is then fed into a Color object (in .NET, you would use this value in the Color.FromArgb method), which expects the value of the parameter to have the individual color values (e.g., alpha/opacity value, red, green, and blue values, respectively) in specific parts of the 32-bit value. So...let's digress a bit to CSC242 - Assembly...

1 byte = 8 bits, which, in memory would be:
00: 00 00 00 00 // 00: represents a memory address, each pair representing 2 bits

2 bytes = 16 bits, in memory
00: 00 00 00 00 00 00 00 00

3 bytes = 24 bits, in memory
00: 00 00 00 00 00 00 00 00 00 00 00 00

4 bytes = 32 bits, in memory
00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Now, an integer, on a 32-bit machine, occupies (appropriately so), 4 bytes of memory. So, when you assign an integer a value of, say, 135, it looks like this in memory (values in binary):

int val = 135; //c# assignment
00: 00 00 00 00 00 00 00 00 00 00 00 10 00 01 11 // 10000111 in binary is 135

This is exactly how the computer stores the value in memory. However, this won't "work" for the Color.FromArgb(int argb) method because as the documentation states:

"The byte-ordering of the 32-bit ARGB value is AARRGGBB. The most significant byte (MSB), represented by AA, is the alpha component value. The second, third, and fourth bytes, represented by RR, GG, and BB, respectively, are the color components red, green, and blue, respectively."


Most significant bit translates to the first pair of zeros you'd read in the value of (in bold below):

00: 00 00 00 00 00 00 00 00 00 00 00 10 00 01 11 // 1000111 in binary is 135

So, if we wanted 135 to be the red value, we need move - or shift - the bits that represent 135 up to the proper position. This is where the left-shift (<< in C/C++/C#/Java) operation comes in. When you apply the left-shift operator, you must specify the number of bits you want to move. In order to move the values of 135 into the proper position for the Color.FromArgb(int) method to interpret the value as the value we want for red, we must shift the value 16 bits.

int red = (135 << 16);
00: 00 00 00 10 00 01 11 00 00 00 00 00 00 00 00

Shifting the bits left 16 positions, is effectively multiplying 135 by 2^16, or 65536. To get the green value of the color, we need to shift the bits left 8 positions:

int green = (135 << 8);
00: 00 00 00 00 00 00 00 10 00 01 11 00 00 00 00

We apply the same to the value for blue, but shifting the bits really has no effect as the blue component stays in the last byte:

int blue = (135 << 0);
00: 00 00 00 00 00 00 00 00 00 00 00 10 00 01 11 // 10000111 in binary is 135

Now, to make the composite value - that is, combining the red, green and blue values into 1 value - we add the values together, bitwise. This is accomplished using the bitwise OR operator:

int rgb = (red | green | blue);
00: 00 00 00 00 10 00 01 11 10 00 01 11 10 00 01 11

The rgb variable now has all three color components in the proper positions. Having zeros in the most significant bits translates to a value of 0 for the alpha/transparency component that the FromArgb(int) method is expecting - giving us a completely opaque color.

This may not be the most clear description; I found out that I by showing the disassembly while running a program shows the effect (however, in hex) that shifting has on values. Hopefully, I'll be able to post some shots to help explain.