A few months ago I wrote about a very nifty square root function in Jack Crenshaw’s book “Math Toolkit for Real-time Programming”. As elegant as the square root function is, it pails in comparison to what Crenshaw calls his ‘bitlog’ function. This is some code that computes the log (to base 2 of course) of an integer – and does it in amazingly few cycles and with amazing accuracy. The code in the book is for a 32 bit integer; the code I present here is for a 16 bit integer. Although you are of course free to use this code as is, I strongly suggest you buy Crenshaw’s book and read about this function. You’ll see it truly is a work of art. BTW, one of the things I really like about Crenshaw is that he takes great pains to note that he didn’t invent this algorithm. Rather he credits Tom Lehman. Kudos to Lehman.
/** FUNCTION: bitlog DESCRIPTION: Computes 8 * (log(base 2)(x) -1). PARAMETERS: - The uint16_t value whose log we desire RETURNS: - An approximation to log(x) NOTES: - **/ uint16_t bitlog(uint16_t x) { uint8_t b; uint16_t res; if (x <= 8 ) /* Shorten computation for small numbers */ { res = 2 * x; } else { b = 15; /* Find the highest non zero bit in the input argument */ while ((b > 2) && ((int16_t)x > 0)) { --b; x <<= 1; } x &= 0x7000; x >>= 12; res = x + 8 * (b - 1); } return res; }
Tags: Log
This code is really messed up by WordPress.
I also suspect it is not very good.
I’d expect two table lookups in a 256 entry table to be better.
Or some bit twiddling hack: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
I have changed the formatting of the code so as to make WordPress render it a little better.