在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位英特尔CPU。

有一个有用的参考页面是Bit Hacks页面，另一个是fxtbook.pdf。然而，虽然它们提供了解决问题的有用方向，但它们并没有给出一个现成的答案。

我需要一个可重复使用的函数，类似于C#中的_BitScanForward64和_BitScanReverse64。

- Andrew Savinykh

---

这不是与https://dev59.com/nGkv5IYBdhLWcg3wqiiS基本相同吗？ 显然，您必须将其调整为64位，并且它会给出您要查找的数字的相反数，但它传达了相同的信息。 - Taekahn

@Taekahn 调整到64位并不是一件简单的事情。你可以试试看。正如我在问题中承认的那样，SO上存在32位的答案。 - Andrew Savinykh

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 = x == 0 ? 0 : BitOperations.Log2(x) + 1

- phuclv

---

很好！谢谢你分享这个！ - Andrew Savinykh

在您的答案中添加了一个链接。+1 - Taekahn

x=2 "BitOperations.Log2(x - 1) + 1" 得到的结果是2，但是x=3得到的结果是1（但它们应该有相同的最高有效位）。也许可以使用"BitOperations.Log2(x) +1"。此外，Log2(0)+1和Log2(1)+1都得到1，因此可能需要添加一个保护条件"(x==0) ? 0 : BitOperations.Log2(x) + 1"。 - SunsetQuest

Answer 2

在编程中有一种方法，可以利用德布鲁因序列，这个方法在与问题相关的Bit Hacks页面中有描述。不幸的是，该页面没有提供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];
    }
}

我还在github上发布了C#版本的序列生成器。

另一篇与De Bruijn序列相关的文章，没有在问题中提到，可以在这里找到。

- Andrew Savinykh

Answer 3

根据我的评论，这是一个用于计算64位整数的前导零位的C#函数。

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

更新：
如果您使用的是较新版本的 C#，请检查下面答案中是否内置了此功能。 https://dev59.com/b10Z5IYBdhLWcg3wfgi-#61141435

- Taekahn

---

根据我的性能测试，这比我的更快，在我的输入上。干得好，谢谢！ - Andrew Savinykh

如果可以的话，我想知道你会用这个做什么？尽管我很努力，但我无法想到任何实际应用。 - Taekahn

我正在运行某些数学建模模拟。在处理每个批次中的数十亿个样本时，稍微削减一些毫秒可以使它们更快地完成。 - Andrew Savinykh

目前整个程序运行速度比我开始时快了约6倍（每次模拟需要40分钟，而我最初需要4小时），分析器中的热点是“Array.Clone”和“Dictionary.TryGetValue”。这表明我可以进一步优化的唯一事情是想出更好的数据修剪方法来使样本更小。 - Andrew Savinykh

有趣。你的工作听起来比我的更有趣.....但我跑题了。 谢谢分享 :) - Taekahn

找到最高有效位远非不切实际。这是一个非常常见和有用的操作，就像找到一个数字的log2，或者找到一个数字适合多少字节/位，这在许多编码中都被使用。这就是为什么在大多数现代架构中都有硬件指令来执行此操作。然而，在C#中执行这样的计算密集型任务并不是高效的方法。编写利用SIMD的本机代码会更好。 - phuclv

Answer 4

获取IL代码中最高位的最快方法应该是将其转换为float并访问指数位。

保存代码：

int myint = 7;
int msb = (BitConverter.SingleToInt32Bits(myint) >> 23) - 0x7f;

更快的方法是使用msb和lsb CPU指令。正如phuclv所提到的，它在.Net Core 3.0中可用，因此我添加了一个测试，但速度并没有快多少。

按照要求，这里是对10000个uint和ulong进行转换的BenchmarkDotNet结果。加速比为2倍，因此BitScanner解决方案很快，但无法击败本地浮点转换。

           Method |     Mean |    Error |   StdDev | Ratio
BitScannerForward | 34.37 us | 0.420 us | 0.372 us |  1.00
BitConverterULong | 18.59 us | 0.238 us | 0.223 us |  0.54
 BitConverterUInt | 18.58 us | 0.129 us | 0.121 us |  0.54
     NtdllMsbCall | 31.34 us | 0.204 us | 0.170 us |  0.91       
 LeadingZeroCount | 15.85 us | 0.169 us | 0.150 us |  0.48

- Hessi9

---

既然已经有一个不同于你的答案被接受了，那么你应该进行一些速度测试，并在回答中发布结果，以证明它更快。如果你这样做了，请@我，我会点赞你的答案。...你需要考虑到问题指定它涉及64位整数，同时明确排除32位整数。...因此，你可能只需要删除这个答案。总的来说，在速度问答中，始终要发布速度测试和结果，并最好附带相关数据集。 - Rodger

我怀疑你的结果是否正确。BitOperations.LeadingZeroCount应该比转换为浮点数然后进行一些操作要快得多。 - phuclv

我为BitOperations.LeadingZeroCount添加了一个更快但令人失望的测试。因此，如果您有幸拥有.Net Core 3.0兼容的目标平台，则应使用它，否则浮点转换是最快的方法。 - Hessi9

Answer 5

@Taekahn 给出了一个很好的回答，我只是稍微改进一下:

[System.Runtime.CompilerServices.MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int CountLeadingZeros(this ulong input)
{
    const int bits = 64;
    // if (input == 0L) return bits; // Not needed. Use only if 0 is very common.
    int n = 1;
    if ((input >> (bits - 32)) == 0) { n += 32; input <<= 32; }
    if ((input >> (bits - 16)) == 0) { n += 16; input <<= 16; }
    if ((input >> (bits - 8)) == 0) { n += 8; input <<= 8; }
    if ((input >> (bits - 4)) == 0) { n += 4; input <<= 4; }
    if ((input >> (bits - 2)) == 0) { n += 2; input <<= 2; }
    return n - (int)(input >> (bits - 1));
}

• 避免使用稍微有点神奇的数字，而是使用(bits - x)来使它们的意图更加明显。
• 适应不同的字长现在应该很明显和琐碎了。
• 将(input == 0)视为特殊情况是不必要的，并且去除这种情况将加速所有其他输入。
• 使用int作为计数器比使用UInt64更合理。(甚至可以将其设置为byte，但是int是默认的整数类型，据说在每个平台上都是最快的。)
• 添加了用于积极内联的属性，以确保获得最佳性能。

没有必要在运行时计算任何“(bits - x)”中的值，因此编译器应该预先计算它们。因此，提高可读性并不需要任何代价。

编辑：正如@Peter Cordes指出的那样，如果您有BitOperations类，则应该只使用System.Numerics.BitOperations.LeadingZeroCount 。我自己常常没有。

- Jan Heldal

---

2020年还有必要吗？如果JIT编译效率高的话，BitOperations.LeadingZeroCount应该会更快。或者在编译针对没有硬件位扫描的目标架构时，它们是相等的。如果C#不能通过位运算版本进行常量传播，我可以想象这对于编译时常量输入会更快，但希望它能够做到。 - Peter Cordes

@Peter Cordes：.NET平台有很多变体，并非所有变体都可以访问BitOperations类。在我们公司，我们仍然使用一些产品的传统“Portable”项目，而System.Numerics.BitOperations根本不存在。 - Jan Heldal

你的答案对于零不给出正确的结果。你最终会得到1+32+16+8+4+2-0=63而不是64。 - Arnaud

Answer 6

既然我们在谈论.NET，通常最好不要使用外部本机调用。但是如果您可以容忍每个操作的托管/非托管往返开销，则以下两个调用提供了对本机CPU指令相当直接和未经过滤的访问。

分别来自ntdll.dll的各自函数的（极简主义）反汇编也显示在下面。该库将存在于任何Windows计算机上，并且如果按照所示引用，则始终会找到它。

最低有效位（LSB）：

[DllImport("ntdll"), SuppressUnmanagedCodeSecurity]
public static extern int RtlFindLeastSignificantBit(ulong ul);

// X64:
//      bsf rdx, rcx
//      mov eax, 0FFFFFFFFh
//      movzx ecx, dl
//      cmovne eax,ecx
//      ret

最高有效位（MSB）：

[DllImport("ntdll"), SuppressUnmanagedCodeSecurity]
public static extern int RtlFindMostSignificantBit(ulong ul);

// X64:
//      bsr rdx, rcx
//      mov eax, 0FFFFFFFFh
//      movzx ecx, dl
//      cmovne eax,ecx
//      ret

使用方法：
这里有一个使用示例，需要访问上述声明。非常简单。

int ix;

ix = RtlFindLeastSignificantBit(0x00103F0A042C1D80UL);  // ix --> 7

ix = RtlFindMostSignificantBit(0x00103F0A042C1D80UL);   // ix --> 52

- Glenn Slayden