如何有效地计算数字中的尾随零位？

问题描述 投票：0回答：4

我编写了一个函数 

trailing_zeroes(int n)
，它返回数字的二进制表示形式中尾随零的数量。

示例：二进制中的

4
是
100
，因此本例中的函数返回
2
。

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，就会出现循环。

我认为这样写的代码非常丑陋；有更好的办法吗？

我想避免在 

break
中使用 
while
语句，因为很多人告诉我，在 
while/for
中使用该语句有时可能是“非正式的”。我想像这样重写函数，但我认为这不是最好的方法：

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

bits = 0;
while (!(n & 01)) {
    ++bits;
    n >>= 1;
}
c++ c while-loop bit-manipulation bitwise-operators
4个回答
4
投票

你的函数不正确：它仍然有一个无限循环

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 文档的摘要：

内置功能：

int __builtin_ctz (unsigned int x)

返回 

x
中尾随 0 位的数量，从最低有效位位置开始。如果 
x
是 
0
，则结果未定义。

4
投票

正如已经提到的，有一个内置函数可以做到这一点，并且由于它可能使用硬件，因此速度可能非常快。但是，GCC 的 doc 确实表示，如果输入为 0，结果是未定义的。由于这是一个扩展，它可能不适用于您的编译器。

否则，每当有人说“但是操纵”或“位计数”时，您就需要拿起您的“黑客之乐”。书太好了，两个版本都买了。大约有 4 页（第一版）专门讨论“ntz”（尾随零的数量）。如果您已经有“nlz”（前导零的数量）或“popcnt”函数，那么您可以直接获取 ntz。另外，这本书给出了几种实现，一些使用 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);
}
2
投票

亨利·沃伦 (Henry Warren) 的《黑客之乐》中报道了 

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];
}
2
投票

C++20 引入了 

<bit>
标头，它提供了 
countr_zero
。链接的 cppreference 页面提供了示例：

#include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>
 
int main()
{
    for (const std::uint8_t i : { 0, 0b11111111, 0b00011100, 0b00011101 }) {
        std::cout << "countr_zero( " << std::bitset<8>(i) << " ) = "
                  << std::countr_zero(i) << '\n';
    }
}

输出：

countr_zero( 00000000 ) = 8
countr_zero( 11111111 ) = 0
countr_zero( 00011100 ) = 2
countr_zero( 00011101 ) = 0

如果您需要 0 输入的值为 0，您可以执行以下操作：

(n ? countr_zero(n) : 0)
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.