How can I compute a base 2 logarithm without using the built-in math functions in C#?

Question

How can I compute a base 2 logarithm without using the built-in math functions in C#?

I use Math.Log and BigInteger.Log repeatedly in an application millions of times and it becomes painfully slow.

I am interested in alternatives that use binary manipulation to achieve the same. Please bear in mind that I can make do with Log approximations in case that helps speed up execution times.

Answer 1

Assuming you're only interested in the integral part of the logarithm, you can do something like that:

static int LogBase2(uint value)
{
    int log = 31;
    while (log >= 0)
    {
        uint mask = (1 << log);
        if ((mask & value) != 0)
            return (uint)log;
        log--;
    }
    return -1;
}

(note that the return value for 0 is wrong; it should be negative infinity, but there is no such value for integral datatypes so I return -1 instead)