c# - 更快的 Log2Ceil

Question

我想知道是否有人知道一种更快的方法来实现下面的函数，在 C# 中计算整数的 2 上限的对数。

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

Answer 1

请参阅此问题的答案。它引用的代码是用 C 编写的，但其中大部分也可以在 C# 中运行。

或者，您可以使用

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

它使用了浮点数包含二进制指数编码的事实。一个快速的基准测试表明，这比您在 x64 上的原始速度快 13 倍，在 x86 上快约 21 倍。

Answer 2

我还找到了另一种方法来做到这一点，如此处所述。

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