Bit Counting

A few years ago, I was on a job interview, and the interviewer asked me how to write a function to count the number of '1' bits in a byte. I replied that this sounded like an obvious table lookup problem. Just create the table with 256 entries, and use the byte value itself to index to the correct bit count.

That seemed to take him a little off guard, but he quickly asked how to populate the table. He was still trying to get me to answer his original question with the explanation of how to test each bit by shifting the byte successively and ANDing with 1. If the shifted byte ANDed with 1 was 1, then the low bit was on, and the bit count for that byte should be incremented.

That might be ok for counting bits in one or two bytes, but it's a pretty lame way to populate a table. I knew there had to be a better way. The lame approach would require 2048 tests and 1792 shifts. Obviously there's a pattern to the number of bits set in values ranging from 0 to 255, and I wanted to take advantage of that. (Yes, you could skip the shift and just AND each byte 8 times, once with each of 8 different masks. That's still 2048 ANDs and tests.)

Unfortunately, I was so distracted by this that I didn't answer the question right away, and I didn't get the job. Actually, I don't know if this was the deciding factor or not, but it bugged me. I always get my best answers on the way home from the interview, and this was a prime example of that.

Got it?