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

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

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

Answer 3

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