c# - 如何用 C# 计算整数的二进制表示中的尾随零

Question

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

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。）

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

Answer 3

在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”

Answer 4

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

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

Answer 5

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