Bitwiser

Prompted by an email with a developer who was concerned about the lack of knowledge about bit fields and bit shifting…

Before reading this you might want to revise your bits and bytes and two’s complement.

Bit fields use the individual bits in a byte or other integer type, and in C++ operators such as the bitwise OR, |, bitwise AND, &, and shift operators << and >> allow direct manipulation of the bits in a variable.

When initialising the GLUT display mode, the bitwise OR operator is used to combine the options chosen in a single variable:

glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE | GLUT_DEPTH);

This passes as input to the glutInitDisplayMode a single parameter – found by OR’ing the three variables together. If you check the GLUT headers you’ll be able to see that each has a power of two value… so if the three values are 8, 4 and 1 then the parameter passed into InitDisplayMode would be 13 (ie. 8 | 4 | 1 )

The display mode function will itself use bitwise comparisons to determine how to initialise glut. This might seem awkward, but allows a single byte or word to be used in place of multiple variables.

Bit shifting in C++ uses the << and >> operators (yes, another use for these!)

Shifting all the bits in an integer one place to the left effectively adds another 0 at the end – ie. it multiplies the value by two (this is in binary – in decimal if you add a 0 zero at the end of a number you get the same result as multiplying by ten)

Bitwise and bit shifting operations are sometimes used for their compactness and for possible optimizations. For example, a bit shift operation is, on most processors, quicker to computer than a multiplication or division. So when multiplying or dividing by a power of two, some developers might use a bit shift instead.

BUT this might not always be necessary or even have any effect. Optimising code without knowing where the bottlenecks actually are is of limited value – and can make code harder to understand or maintain. And modern compilers are pretty good at optimising code too…

I did a quick test in Visual Studio 2010 to see how shift operators compared to multiply and divide – comparing a single postion left and right shift with a *2 and /2 operations.

So, for example a shift left C++ instruction and the assembly produced:

c = (b<<1);
002715E7 mov eax,dword ptr [b]
002715EA shl eax,1
002715EC mov dword ptr ,eax

The middle line there shows the shl instruction – shift left.

What happens for c = (a*2)? The assembly is shown below:

0027153D mov eax,dword ptr [a]
00271540 shl eax,1
00271542 mov dword ptr ,eax

Look familiar? It should, because it is the exact same. The compiler recognises that *2 can be more efficiently computed using a shift left operation than by multiplication, so it does that.

What about shift right?

d = (b>>1);
002715EF mov eax,dword ptr [b]
002715F2 sar eax,1 // shift right
002715F4 mov dword ptr [d],eax

What happens when divide is used instead?

d = a/2;
00271532 mov eax,dword ptr [a]
00271535 cdq
00271536 sub eax,edx
00271538 sar eax,1
0027153A mov dword ptr [d],eax

The compiler has used a shift right instead of a divide but the code generated is not the same! This has two additional instructions. cdq extends the 32-bit value (which has been placed in register eax) to a 64 bit value across the pair of registers eax and edx. I have to admit I’m slightly lost as to the purpose of the subtraction… because it doesn’t achieve very much.

Ho well, the output from this is the same in either case – whether the number we are dividing or shifting is positive, negative or 0.

But 100 brownie points to anyone who can convincingly explain to me why the extra two statements are there…