Bitwise Operators Pt. II: Use Cases

Luckily with today’s computing power, the necessity of bit manipulation isn’t as prevalent as it once was as programmers no longer need to account for every literal bit. Still, these are good things to have in your tool belt, especially in low memory environments like in PLCs.

A common example case is determining if a number is a power of two. Visually, this is very easy to inspect. If the bit has a single 1, it is a power of two. With bitwise operators, it takes a bit more work:

isPowerOfTwo(x) 
{ 
 return x && (!(x & (x - 1))); 
}

The x before the double ampersand is for the use case where x is 0. The second half of the function just compares x and its lowest neighbor. A common property of all power of two integers is that x and x-1 have perfectly switched bits.

Another famous example comes from the developers at Id Software, most famous for their work on Wolfenstein, Quake, and Doom. This function accurately approximates the inverse square of a float. The inverse square is a necessary function when dealing with 3D vectors. As this function is going to be fired many times a second during rendering, the function needed to be fast.

float Q_rsqrt( float number )
{
   long i;
   float x2, y;
   const float threehalfs = 1.5F;

   x2 = number * 0.5F;
   y  = number;
   i  = * ( long * ) &y   // evil floating point bit level hacking
   i  = 0x5f3759df - ( i >> 1 );   // what the fuck? 
   y  = * ( float * ) &i;
   y  = y * ( threehalfs - ( x2 * y * y )…