快速查找64位整数中设置最高和最低有效位的方法

Question

StackOverflow上有很多关于此的问题.很多.但是我找不到答案:

• 在C#中工作
• 适用于64位整数(与32位相反)

比...快:

private static int Obvious(ulong v)
{
    int r = 0;
    while ((v >>= 1) != 0) 
    {
        r++;
    }
    return r;
}

甚至

int r = (int)(Math.Log(v,2));

我在这里假设一个64位Intel CPU.

一个有用的参考是Bit Hacks页面,另一个是fxtbook.pdf. 然而,虽然这些提供了解决问题的有用方向,但它们没有给出准备好的答案.

我正在使用一个可重用的函数,它只能为C#执行与_BitScanForward64和_BitScanReverse64类似的操作.

Answer 1

.NET Core 3.0 添加了BitOperations.LeadingZeroCount和BitOperations.TrailingZeroCount，因此您可以直接使用它们。它们将被映射到 x86 的 LZCNT/BSR 和 TZCNT/BSF 指令，因此非常高效

int mostSignificantPosition = 63 - BitOperations.LeadingZeroCount(0x1234L);
int leastSignificantPosition = BitOperations.TrailingZeroCount(0x1234L);

或者，最高有效位的位置可以这样计算

int mostSignificantPosition = BitOperations.Log2(x - 1) + 1

Answer 2

在问题中链接的Bit Hacks页面上描述的其中一种方法是利用De Bruijn序列.不幸的是,这个页面没有给出所述序列的64位版本.这个有用的页面解释了如何构造De Bruijn序列,并且这个序列给出了用C++编写的序列生成器的示例.如果我们调整给定的代码,我们可以生成多个序列,其中一个序列在下面的C#代码中给出:

public static class BitScanner
{
    private const ulong Magic = 0x37E84A99DAE458F;

    private static readonly int[] MagicTable =
    {
        0, 1, 17, 2, 18, 50, 3, 57,
        47, 19, 22, 51, 29, 4, 33, 58,
        15, 48, 20, 27, 25, 23, 52, 41,
        54, 30, 38, 5, 43, 34, 59, 8,
        63, 16, 49, 56, 46, 21, 28, 32,
        14, 26, 24, 40, 53, 37, 42, 7,
        62, 55, 45, 31, 13, 39, 36, 6,
        61, 44, 12, 35, 60, 11, 10, 9,
    };

    public static int BitScanForward(ulong b)
    {
        return MagicTable[((ulong) ((long) b & -(long) b)*Magic) >> 58];
    }

    public static int BitScanReverse(ulong b)
    {
        b |= b >> 1;
        b |= b >> 2;
        b |= b >> 4;
        b |= b >> 8;
        b |= b >> 16;
        b |= b >> 32;
        b = b & ~(b >> 1);
        return MagicTable[b*Magic >> 58];
    }
}

我还将序列生成器的C#端口发布到github

在这里可以找到与De Bruijn序列的正确封面的问题中未提及的另一篇相关文章.

Answer 3

根据我的评论,这是C#中的一个函数,用于计算为64位整数修改的前导零位.

public static UInt64 CountLeadingZeros(UInt64 input)
{
    if (input == 0) return 64;

    UInt64 n = 1;

    if ((input >> 32) == 0) { n = n + 32; input = input << 32; }
    if ((input >> 48) == 0) { n = n + 16; input = input << 16; }
    if ((input >> 56) == 0) { n = n + 8; input = input << 8; }
    if ((input >> 60) == 0) { n = n + 4; input = input << 4; }
    if ((input >> 62) == 0) { n = n + 2; input = input << 2; }
    n = n - (input >> 63);

    return n;
}