如何使用C#计算整数二进制表示中的末尾零数量

Question

如何高效地计算整数二进制表示中末尾零的数量？

- abel406

---

Java的实现基于《Hacker's Delight》一书。请参见此处示例。 - Prince John Wesley

可能不是很快，但我认为你可以将int转换为BitArray，然后向后循环并计数。 - Hans Olsson

你的二进制表示是什么？是一个字符串吗？它能适应 int 或 long 吗？ - Robert Harvey

只需要一个x86机器码指令。BSFW、BSFL或BSFQ，名称为Bit scan forward，可惜在C#中不是单个指令。但我不想回到汇编语言。 - Casperah

Answer 1

这是一个不错的、快速简便的实现：

public static int NumberOfTrailingZeros(int i)
{
    return _lookup[(i & -i) % 37];
}

private static readonly int[] _lookup =
    {
        32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17,
        0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18
    };

（摘自http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightModLookup。）

- LukeH

---

@Downvoter：您能解释一下为什么您认为这个答案应该被点踩吗？ - LukeH

我没有点踩，但我可以想象为什么人们会点踩。取模部分是昂贵的。它会在最好的情况下转化为一个64位长的乘法，甚至在最坏的情况下需要数十个周期的除法。并且它需要37*4字节的内存。总之，如果不比下面的迭代版本更差的话，它几乎没有任何优势。考虑到大多数架构自几十年前就开始使用clz指令，你的建议并不是很有帮助的。 - Jake 'Alquimista' LEE

@Jake：我同意这可能不是最优解，但我提供了一个链接到bithacks页面，其中有一些替代方法。此外，我们在谈论C#，这是一种托管语言：如果您知道如何从C#和/或.NET强制执行CLZ / CTZ指令，请分享。 - LukeH

@Jake：如果OP愿意在.NET运行时的限制下工作，那么mod调用和147字节的存储很可能不是什么大问题（如果它们是问题，那么OP可以自由地对替代方案进行基准测试，直到找到符合其要求的方案为止）。 - LukeH

你对人们为何给你的帖子点踩感到好奇。我给了你答案。下面是另一个链接：http://www.codeproject.com/Articles/1392/Using-Unmanaged-code-and-assembler-in-C - Jake 'Alquimista' LEE

他们是如何计算/生成那个表格的？我还没有在任何地方找到生成该表格的算法。 - Lance

Answer 2

从第一个数字开始制作掩码，然后不断移动直到找到匹配项:

public static int numTrailingBinaryZeros(int n)
{
    int mask = 1;
    for (int i = 0; i < 32; i++, mask <<= 1)
        if ((n & mask) != 0)
            return i;

    return 32;
}

- Servy

Answer 3

从 .Net Core 3.0 开始，有BitOperations.TrailingZeroCount函数。虽然我不知道之前的版本是否也有该函数，但是如果我查看当前的 .NET 7 源代码，它已经内联到了Bmi1.TrailingZeroCount中，并在支持的 x86 环境中转换为tzcnt x86 汇编指令，因此具有硬件加速实现，对于ARM也有软件实现的备选方案。

- ömer hayyam

---

现在应该接受这个答案了。Intrinsics使得很多这些好的位操作变得非常非常低效，无论是在C#还是Java中。它们可能在问题提出时还不存在，但如今，每个人都试图在进行性能优化之前（或者检查生成的代码之前）创建一个优化版本，只会自己给自己找麻烦。 - Franz D.

Answer 4

在Java中，它的实现方式如下：

  public static int numberOfTrailingZeros(int i) {
        // HD, Figure 5-14
        int y;
        if (i == 0) return 32;
        int n = 31;
        y = i <<16; if (y != 0) { n = n -16; i = y; }
        y = i << 8; if (y != 0) { n = n - 8; i = y; }
        y = i << 4; if (y != 0) { n = n - 4; i = y; }
        y = i << 2; if (y != 0) { n = n - 2; i = y; }
        return n - ((i << 1) >>> 31);
    }

我认为这个想法来自于《黑客的乐趣》（Hacker's Delight）。

- Oleksandr Vitvitskyi

---

一个展开的二分查找循环——太棒了！因为找到了一种现有的、经过大量验证的方法，所以加1分。 - voxoid

在C#中，返回行无法编译，因为C#没有零填充右移运算符>>>。相反，我认为应该是return n - (int)((uint)(i << 1) >> 31);。 - voxoid

虽然有点冷门，但这是Java标准库的实现（Integer.numberOfTrailingZeros）。 - thecodewarrior

Answer 5

int trailingZeros(int n) {
    if(!n)
        return 32;

    for(int s = 0; !(n & 1); s++)
        n >>= 1;
    return s;
}

- artahian

Answer 6

这个 Java 版本的变体使用了更多的位操作来消除最后一个条件测试：

    public static uint Ctz(uint num)
    {
        if (num == 0) return 32;    // optional, otherwise returns 0

        uint tmp;
        uint res = 0;
        num &= (uint)-(int)num;  // Isolate bit
        tmp = num >> 16; if (tmp != 0) { num = tmp; res += 16; }
        tmp = num >> 8;  if (tmp != 0) { num = tmp; res += 8; }
        tmp = num >> 4;  if (tmp != 0) { num = tmp; res += 4; }
        return res + ((num >> 1) - (num >> 3));
    }

- DosMan