Do You Speak Binary?

How well do you know the fundamental unit of information, communication, computation?

When interviewing coders, I often like to ask them to explain how they would implement a function which counts the number of bits set in an integer. This is often called the “population counting” problem. In Beautiful Code: Leading Programmers Explain How They Think, Henry S. Warren, Jr. gives a wonderful treatment of the population count problem. This C code implements a clever algorithm to compute number of set bits in one 32-bit word:

/* Counts 1-bits in a word. */
int pop(unsigned x) {
  x = x - ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  x = x + (x >> 8);
  x = x + (x >> 16);
  return x & 0x0000003F;
}

Can you figure out how it works?

For a really hard-core puzzle, try to figure out this piece of code from the Quake code. It computes the inverse square root of a floating point number:

float InvSqrt(float x){
   float xhalf = 0.5f * x;
   int i = *(int*)&x;
   i = 0x5f3759d5 - (i >> 1);
   x = *(float*)&i;
   x = x*(1.5f - xhalf*x*x);
   return x;
}

Wow. If you need to cheat (I did), the web is full of explanations. The one that really helped me understand was by Kalid Azad at BetterExplained.

I firmly believe that every programmer should try to build a good working understanding of the bit world. It’s not that you have to know that stuff to be able to write (most) programs. But look at it this way. That computer on your desk has a CPU in it. That CPU is executing billions of instructions per second to execute your code. Are you really not interested at all on what’s going on in there? Don’t you want to know why computers suck at math?

If the next coder you interview has trouble answering more than a couple of the following, that should be a no hire:
The next time you are interviewing a coder, here are some questions you could ask to probe their understanding of the binary system:

• What are the first ten powers of two?
• What is 0×7F in binary? In decimal?
• What does two’s complement mean?
• How would you extract the 8 low-order bits from a word?
• How would you count the number of bits in a word?
• What arithmetic operation does shifting right by one bit correspond to?

To me, total lack of understanding in this area is a big red flag and should cause a no hire. It means that you either haven’t been programming long enough to encounter these bit-level problems, or worse, you did encounter them but gave up for one reason or another.  It’s a real confidence booster to know that you can, if need be, go all the way down to the bit level to solve a problem or understand a bug.

It’s all ones and zeroes, right? The bits are your friends. How well do you know them?

If you liked this, click here to receive new posts in a reader.
You should also follow me on Twitter here.