algorithm - 计算二进制数的楼层对数

Question

如果存在二进制数，在位系统中，则该数的楼层对数定义为该数的 MSB 的索引。现在，如果我有一个二进制数，通过逐位扫描所有位，我可以确定 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];
}

对于无符号的 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];
}

这个网站是玩小把戏的好去处

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

它具有这些以及许多其他技术，可用于实现您在问题中所要求的内容。

Answer 2

正如@hatchet 所说，有许多利用小型查找表的通用技巧。

然而，还有一个值得注意的替代方案。如果您想要最快的实现并使用低级语言，那么该指令也内置在几乎所有 ISA 中，并且几乎所有编译器都支持。请参阅https://en.wikipedia.org/wiki/Find_first_set并酌情使用编译器内在函数或内联汇编。