A Bit on Bits

Long time no post, try to do better...so on and so forth. With that out of the way.

A problem came up recently that I found interesting. The problem is an old one that of counting the number of bits set in a given integer. So I went looking for the correct algorithm to use. The one that I found was elegant and short but took a minute of inspection to understand how it worked.

The algorithm used a strategy called Dynamic Programming. First off Dynamic Programming is about the worst name for this algorithmic strategy because it conveys nothing about how it works. For that algorithmic strategy to be applicable the problem at hand must meet a few conditions. First you must be able to divide the problem into sub problems. Second you must be able to find answer to your problem by solving and putting together the sub problems.

Now you might say "But that sounds like Divide and Conquer" and you would be right. The difference is that in dynamic programming the identical sub-problem comes up multiple times. If you blindly divide and conquer such a problem you end up recomputing the sub-problems multiple times which often leads to exponential time algorithms. So in dynamic programming we keep a table of the answers computed and the problem becomes putting together the sub-answers to find the solution.

So here is the algorithm in pseudo-code ('&' is the bitwise operation a'la C).

onesCount[0] = 0

for i = 1 to 255
    onesCount[i] = onesCount[i / 2] + (i & 0x1)

See, short. This follows the basic structure of any Dynamic Programming algorithm. Basically this builds a look-up table for a single byte (i.e. onesCount[x] is the number of bits set in the integer x). The first line sets up the trivial answer to the problem's base case. Being that the integer zero contains no set bits. Then the for-loop precedes to fill in the rest of the table with the correct values. How does that work?

Now since we start at 0 and work our way upward we know for sure that the value for i / 2 has already been computed. So we know the number of bits set in that number. Well i / 2 basically chops the right most bit off the number (its a one position right bit shift). So that tells us how many bits have been set in all but the one's position and all that remains is to check out if that last bit is set or not. If it is the number of bits set in i is one more then in i / 2. So i & 0x1 is one in exactly that situation.

So thats the dynamic programming algorithm for constructing that look-up table. Do you see how it fits into the dynamic programming strategy. Be on the lookout for other algorithms from the dynamic programming family. They are always interesting.