Monday, September 14, 2009

Bit Counting (Continued)

So here's the pattern. You're trying to populate a table so that each entry in the table contains the number of bits set in a one byte binary representation of that entry's index:

0 = 00000000 → 0 bits set
1 = 00000001 → 1 bit set
2 = 00000010 → 1 bit set
3 = 00000011 → 2 bits set
4 = 00000100 → 1 bit set
5 = 00000101 → 2 bits set
6 = 00000110 → 2 bits set
7 = 00000111 → 3 bits set
8 = 00001000 → 1 bit set
and so on.

So the first two are obviously 0 and 1. The next two are the same, but with the 00000010 bit set. Then the next four follow the same pattern but with the 00000100 bit set. The next eight follow the pattern of the previous eight, but with 00001000 set.

So to populate the table, you basically put 0 in the first entry, and then repeatedly copy all the previous entries, incrementing by 1.

Actually, there's a more concise way to write this I'll post later.

If I had thought of that more quickly, I might have gotten that job in a start-up that was later bought by a large software company. Who knows?

Is it any wonder I'm such a curmudgeon?