Friday, October 9, 2009

Bit Counting (The end, I hope)

So the original question was, "How do you write a function to count the number of bits set in an arbitrary byte?" I figured that if you're going to do this repeatedly, it might be worth just building a lookup table. The question then becomes "How do you populate a table of set bit counts for each possible byte?" This can be solved with a simple iteration:

int exp = 1;
table[0] = 0;
for (int i = 1; i < 256; i++)
if (i == exp*2) exp *= 2;
table[i] = table[i-exp] + 1;

Now if I had thought of that during the interview ...

No comments: