C语言 尾随零的数目

rjzwgtxy  于 2023-01-04  发布在  其他
关注(0)|答案(4)|浏览(113)

我写了一个函数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,则会出现循环。
我觉得这样写的代码很难看有没有更好的办法?
我想避免在while中使用break语句,因为很多人告诉我,在while/for中使用该语句有时可能是"非正式的"。我想这样重写函数,但我不认为这是最好的方法:

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

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

ilmyapht1#

您的函数不正确:对于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的摘要:
内置功能:int __builtin_ctz (unsigned int x)
返回x中从最低有效位位置开始的尾随0位数。如果x0,则结果未定义。

oipij1gg

oipij1gg2#

如前所述,有一个内置函数可以做到这一点,而且由于它可能使用硬件,所以速度可能非常快。然而,doc for GCC确实表示如果输入为0,则结果是未定义的。由于这是一个扩展,因此您的编译器可能无法使用它。
否则,每当有人说"但是操纵"或"位计数"时,你就需要拿出你的"Hacker's Delight"。这本书太好了,我买了两个版本。大约有4页(第一版)致力于此,"ntz"(尾随零的数目)。如果已经有"nlz"(前导零的数量)或者一个"popcnt"函数,那么你就可以直接得到ntz。否则书中给出了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);
}
hi3rlvi2

hi3rlvi23#

在亨利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];
}
bkhjykvo

bkhjykvo4#

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)

相关问题