我写了一个函数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;
}
4条答案
按热度按时间ilmyapht1#
您的函数不正确:对于
0
,它仍然有一个无限循环。测试应该是:注意,这种方法不能处理负数,因此函数可能需要一个
unsigned
数字参数,或者可以将参数转换为unsigned
。您的函数应该将
0
特殊化,并使用更简单的循环:上面的函数非常简单易懂,如果结果很小,它会非常快,
0
返回的值是0
,就像你的函数一样,这是值得怀疑的,因为0
的尾随零和unsigned
类型中的值位一样多。有一种更有效的方法,其步骤数恒定:
请注意,我们可以通过将第一步更改为来处理任何更大的
int
大小一些编译器有一个内置函数
__builtin_ctz()
,它使用非常有效的汇编代码来计算尾随零的数量。它不是一个C标准函数,但以降低可移植性为代价,如果它可用,您可能希望使用它。请检查您的编译器文档。以下是GCC docuemntation的摘要:
内置功能:
int __builtin_ctz (unsigned int x)
返回
x
中从最低有效位位置开始的尾随0位数。如果x
为0
,则结果未定义。oipij1gg2#
如前所述,有一个内置函数可以做到这一点,而且由于它可能使用硬件,所以速度可能非常快。然而,doc for GCC确实表示如果输入为0,则结果是未定义的。由于这是一个扩展,因此您的编译器可能无法使用它。
否则,每当有人说"但是操纵"或"位计数"时,你就需要拿出你的"Hacker's Delight"。这本书太好了,我买了两个版本。大约有4页(第一版)致力于此,"ntz"(尾随零的数目)。如果已经有"nlz"(前导零的数量)或者一个"popcnt"函数,那么你就可以直接得到ntz。否则书中给出了several implementations,有些使用popcnt,一个有循环,其他的使用二分查找。
例如,
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位的实现,就像在国际象棋引擎中处理“位棋盘”一样。
bkhjykvo4#
C++20引入了
<bit>
头文件,它提供了countr_zero
。链接的cppreference页面提供了示例:输出:
如果需要0输入的值为0,可以执行以下操作: