c++ - 尾随零

我编写了一个函数railing_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;
}

最佳答案

您的函数不正确: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的摘要:

关于c++ - 尾随零，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45221914/