Faster Log2Ceil

Question

I was wondering if somebody knows a faster way to implement the function below, a computation of logarithm of 2 ceiling on integers, in C#.

private int Log2Ceil(int x)
{
   return (int)Math.Ceiling(Math.Log((double)x, 2));
}

Answer 1

See the answer to this question. The code it references is in C, but most of it works in C# as well.

Alternatively, you can use

private int Log2Ceil(int n) {
    long bits = BitConverter.DoubleToInt64Bits((double)n);
    return ((int)(bits >> 52) & 0x7ff) - 1022;
}

which uses the fact that floating-point numbers contain an encoding of the binary exponent. A quick benchmark showed this to be 13x faster than your original on x64 and about 21x faster on x86.

Answer 2

I also found another way to do that, as described here.

private int Log2Ceil(int x)
{
    uint v = (uint)(x - 1); // 32-bit word to find the log base 2 of
    uint r = 0; // r will be lg(v)
    while (v > 0) // unroll for more speed...
    {
        v >>= 1;
        r++;
    }
    return (int)r;
}