尾随零的数量

Question

我写了一个函数 trailing_zeroes(int n) returns 一个数字的二进制表示中尾随零的数量。

示例：二进制中的4是100，所以本例中的函数returns2.

unsigned trailing_zeroes(int n) {
    unsigned bits;

    bits = 0;
    while (n >= 0 && !(n & 01)) {
        ++bits;
        if (n != 0)
            n >>= 1;
        else
            break;
    }
    return bits;
}

if语句的原因是因为如果n等于0，就会出现循环。

我觉得这样写的代码很丑；有没有更好的方法？

我想避免在 while 中使用 break 语句，因为很多人告诉我在 while/for 中使用该语句有时可能是 "informal"。我想像这样重写函数，但我认为这不是最好的方法:

unsigned bits;
if (n == 0)
    return bits = 1;

bits = 0;
while (!(n & 01)) {
    ++bits;
    n >>= 1;
}

Answer 1

如前所述，有一个内置函数可以执行此操作，并且由于它可能使用硬件，因此速度可能非常快。但是，doc for GCC 确实表示如果输入为 0，则结果未定义。由于这是一个扩展，它可能不适用于您的编译器。

否则，无论何时有人说 'but manipulation' 或 'bit counting'，您都需要找到 "Hacker's Delight". A book so good that I bought both editions. There are about 4 pages (1st ed.) dedicated to this, 'ntz' (number of trailing zeroes). If you already have a 'nlz' (number of leading zeroes) or a 'popcnt' function, then you can get the ntz directly. Otherwise the book gives several implementations 的副本，一些使用 popcnt，一个使用循环，其他使用二进制搜索.

例如，

int ntz3(unsigned x) {
   int n;

   if (x == 0) return(32);
   n = 1;
   if ((x & 0x0000FFFF) == 0) {n = n +16; x = x >>16;}
   if ((x & 0x000000FF) == 0) {n = n + 8; x = x >> 8;}
   if ((x & 0x0000000F) == 0) {n = n + 4; x = x >> 4;}
   if ((x & 0x00000003) == 0) {n = n + 2; x = x >> 2;}
   return n - (x & 1);
}

Answer 2

你的函数不正确：它仍然有一个 0 的无限循环。测试应该是：

while (n > 0 && !(n & 1))

请注意，您不能使用这种方法处理负数，因此您的函数可能应该采用 unsigned 数字参数，或者您可以将参数转换为 unsigned.

你的函数应该是特例 0 并使用更简单的循环：

unsigned trailing_zeroes(int n) {
    unsigned bits = 0, x = n;

    if (x) {
        while ((x & 1) == 0) {
            ++bits;
            x >>= 1;
        }
    }
    return bits;
}

以上功能非常简单易懂。如果结果很小，它会很快。为 0 返回的值是 0 就像在你的函数中一样，这是有问题的，因为 0 确实有与 unsigned 类型中的值位一样多的尾随零。

有一种步骤数恒定的更有效的方法：

unsigned trailing_zeroes(int n) {
    unsigned bits = 0, x = n;

    if (x) {
        /* assuming `x` has 32 bits: lets count the low order 0 bits in batches */
        /* mask the 16 low order bits, add 16 and shift them out if they are all 0 */
        if (!(x & 0x0000FFFF)) { bits += 16; x >>= 16; }
        /* mask the 8 low order bits, add 8 and shift them out if they are all 0 */
        if (!(x & 0x000000FF)) { bits +=  8; x >>=  8; }
        /* mask the 4 low order bits, add 4 and shift them out if they are all 0 */
        if (!(x & 0x0000000F)) { bits +=  4; x >>=  4; }
        /* mask the 2 low order bits, add 2 and shift them out if they are all 0 */
        if (!(x & 0x00000003)) { bits +=  2; x >>=  2; }
        /* mask the low order bit and add 1 if it is 0 */
        bits += (x & 1) ^ 1;
    }
    return bits;
}

请注意，我们可以通过将第一步更改为

来处理任何更大的 int 大小

while (!(x & 0x0000FFFF)) { bits += 16; x >>= 16; }

一些编译器有一个内置函数 __builtin_ctz() 可以使用非常高效的汇编代码来计算尾随零的数量。它不是 C 标准函数，但以降低可移植性为代价，如果它可用，您可能希望使用它。检查编译器的文档。

这是来自GCC docuemntation的摘要：

Built-in Function: int __builtin_ctz (unsigned int x)

Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

Answer 3

Henry Warren 在“Hacker's Delight”中报道了 ntz 的各种方法。

我认为 De Bruijn 序列解决方案非常疯狂。参见 https://en.wikipedia.org/wiki/De_Bruijn_sequence#Finding_least-_or_most-significant_set_bit_in_a_word。

这是一个 64 位实现，就像在国际象棋引擎中用来处理“位板”一样。

int ntz(uint64_t x) {
    // We return the number of trailing zeros in
    // the binary representation of x.
    //
    // We have that 0 <= x < 2^64.
    //
    // We begin by applying a function sensitive only
    // to the least significant bit (lsb) of x:
    //
    //   x -> x^(x-1)  e.g. 0b11001000 -> 0b00001111
    //
    // Observe that x^(x-1) == 2^(ntz(x)+1) - 1.

    uint64_t y = x^(x-1);

    // Next, we multiply by 0x03f79d71b4cb0a89,
    // and then roll off the first 58 bits.

    constexpr uint64_t debruijn = 0x03f79d71b4cb0a89;

    uint8_t z = (debruijn*y) >> 58;

    // What? Don't look at me like that.
    //
    // With 58 bits rolled off, only 6 bits remain,
    // so we must have one of 0, 1, 2, ..., 63.
    //
    // It turns out this number was judiciously
    // chosen to make it so each of the possible
    // values for y were mapped into distinct slots.
    //
    // So we just use a look-up table of all 64
    // possible answers, which have been precomputed in 
    // advance by the the sort of people who write
    // chess engines in their spare time:

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

    return lookup[z];
}

尾随零的数量

Number of trailing zeroes

c

c++

bitwise-operators

while-loop