Faster Log2Ceil

本文关键字：Log2Ceil Faster | 更新日期: 2023-09-27 18:00:38

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

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

Faster Log2Ceil

查看此问题的答案。它引用的代码是用C编写的，但大部分代码也可以用C#编写。

或者，您可以使用

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

其使用浮点数包含二进制指数的编码的事实。一个快速基准测试显示，它在x64上比原来快13倍，在x86上快21倍。

我还找到了另一种方法来实现这一点，如下所述。

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;
}
相关文章：