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

これは、浮動小数点数に 2 進指数のエンコードが含まれているという事実を利用しています。簡単なベンチマークでは、x64 ではオリジナルよりも 13 倍高速であり、x86 では約 21 倍高速であることが示されました。

Answer 2

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