algorithm - 2 進数のフロア ログの計算

Question

ビット システムの 2 進数の数値がある場合、数値のフロア ログは数値の MSB のインデックスとして定義されます。ここで、数値が 2 進数である場合、すべてのビットを 1 つずつスキャンすることで、MSB のインデックスを特定できますが、注文するのに n 回かかります。私がそれを行うことができるより速い方法はありますか？

Answer 1

例として c# を使用すると、バイトの場合、テーブルを事前に計算してからルックアップを実行できます

internal static readonly byte[] msbPos256 = new byte[256];
static ByteExtensions() {
    msbPos256[0] = 8; // special value for when there are no set bits
    msbPos256[1] = 0;
    for (int i = 2; i < 256; i++) msbPos256[i] = (byte)(1 + msbPos256[i / 2]);
}

/// <summary>
/// Returns the integer logarithm base 2 (Floor(Log2(number))) of the specified number.
/// </summary>
/// <remarks>Example: Log2(10) returns 3.</remarks>
/// <param name="number">The number whose base 2 log is desired.</param>
/// <returns>The base 2 log of the number greater than 0, or 0 when the number
/// equals 0.</returns>
public static byte Log2(this byte value) {
    return msbPos256[value | 1];
}

unsigned 32 ビット int の場合、次のように動作します。

private static byte[] DeBruijnLSBsSet = new byte[] {
    0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
    8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
public static uint Log2(this uint value) {
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    return DeBruijnLSBsSet[unchecked((value | value >> 16) * 0x07c4acddu) >> 27];
}

この Web サイトは、ちょっとしたトリックを行うための場所です。

http://graphics.stanford.edu/~seander/bithacks.html

これらと、質問で求めていることを達成するための他の多くの手法があります。