尾随零的数量 [英] Number of trailing zeroes

问题描述

我编写了一个函数 trailing_zeroes(int n)，该函数以数字的二进制表示形式返回尾随零的数字.

I've written a function trailing_zeroes(int n) that returns the number of the trailing zeroes in the binary representation of a number.

示例:二进制格式的 4 是 100 ，因此该函数在此情况下返回 2 .

Example: 4 in binary is 100, so the function in this case returns 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，则会出现循环.

The reason of the if statement is because in case n equals to 0, there will be a loop.

我认为这样编写的代码非常难看；有更好的方法吗?

I think it's pretty ugly this code written like this; is there a better way?

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

I want to avoid the break statement inside the while, because a lot of people told me that using that statement inside while/for sometimes could be "informal". I thought to rewrite the function like this, but I don't think it's the best way to do it:

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

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

推荐答案

您的函数不正确:对于 0 ，它仍然具有无限循环.测试应该是:

Your function is incorrect: it still has an infinite loop for 0. The test should be:

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

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

Note that you cannot handle negative numbers with this approach, hence your function should probably take an unsigned number argument, or you could convert the argument to unsigned.

您的函数应为特殊情况 0 并使用更简单的循环:

Your function should special case 0 and use a simpler loop:

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

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

以上功能非常简单易懂.如果结果很小，那将是非常快的.与您的函数一样，为 0 返回的值是 0 ，这值得怀疑，因为 0 的尾随零实际上与 0中的值位一样多.code> unsigned 类型.

The above function is very simple and easy to understand. It is quite fast if the result is small. The value returned for 0 is 0 as in your function, which is questionnable as 0 really has as many trailing zeroes as value bits in the unsigned type.

有一种更有效的方法，其步骤数恒定:

There is a more efficient approach with a constant number of steps:

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

请注意，通过将第一步更改为

Note that we could handle any larger int size by changing the first step to

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

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

Some compilers have a built-in function __builtin_ctz() to count the number of trailing zeroes using very efficient assembly code. It is not a C Standard function but at the cost of reduced portability, you might want to use it if it is available. Check your compiler's documentation.

以下是 GCC文档中的摘要:

内置函数: int __builtin_ctz(无符号int x)

从最低有效位位置开始，返回 x 中尾随0位的数目.如果 x 为 0 ，则结果不确定.

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

这篇关于尾随零的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！