## Code Writing Code

When you strive for optimization in code, there come times when it is apparent that you can use a table lookup instead of a calculation.  Typing in a table of any significant size is both error-prone and time-consuming.  So don't.  And when I say that, I mean never for any table larger than about 16 entries.  Anything else is going to cause you grief, especially if you have to re-type it because of an error.

A fine example is to count the number of bits turned on in an int.  The classic code looks like this:

int BitCount(unsigned int n)
{
int count = 0;
while (n) {
count += n & 1; // if the low bit is set, add 1
n = n >> 1;
}
return count;
}

This is nice - it's a tight loop, not too many variables, some operations that map nicely onto your typical machine architecture.  Problem is, it's still doing a lot of work.  We could improve it by doing a table look up for the bit counting.  Unfortunately, this isn't such a good idea since the table would need to be 4 gigabytes long.  We can use divide and conquer for this:

static int __bitCountByteTable[256] = { ... }
static inline int BitCountByte(unsigned char n)
{
return __bitCountByteTable[n];
}

int BitCountRevised(unsigned int n)
{
int count = 0;
for (int i=0; n && i < sizeof(unsigned int); i++) {
count += BitCountByte((unsigned char)(n & 0xff));
n = n >> 8;
}
return count;
}

Now we're counting 8 bits at a time.  On a 32-bit processor, the loop will run a maximum of 4 times.  You could even rewrite this code to just do the 4 counts on each byte in the long, but you know, 64-bit processors are on the way and the code above should work no matter how many bytes are in your int.

You'll note that I left out __bitCountByteTable.  You make that table like this:

void PrintTable(char *name, int *data,
int length, int entriesPerLine)
{
printf("static int %s[%d] = {", name, length);
for (int i=0; i < length; i++) {
if (i > 0)
printf(",");
if ((i % entriesPerLine) == 0) {
printf("\n\t");
}
else {
printf(" ");
}
printf("%d", data[i]);
}
printf("\n};");
}
void MakeBitCountTable()
{
int table[256];
for (int i=0; i < 256; i++) {
table[i] = BitCount((unsigned int)i);
}
PrintTable("
__bitCountByteTable", table, 256, 8);
}

PrintTable will generate a nicely C-Formatted table declaration with each of the entries in it where you want it.  It's also probably a good idea to include the code that generated your table in comments in the final code and to verify the correctness of the table in a test that runs only in your debug configuration.  For extra credit, rewrite PrintTable to make tables that could be byte, short, int or long and can generate output in decimal or hex, with or without column justification.
Published Monday, April 03, 2006 12:30 PM by Steve Hawley