embedded software boot camp

Integer Log functions

Sunday, May 11th, 2008 by Nigel Jones

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;
}

Home

Tags:

2 Responses to “Integer Log functions”

  1. Juergen says:

    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

  2. Nigel Jones says:

    I have changed the formatting of the code so as to make WordPress render it a little better.

Leave a Reply to Juergen

You must be logged in to post a comment.