注意-这不是此问题的重复-Count the consecutive zero bits (trailing) on the right in parallel: an explanation?。链接的问题具有不同的上下文,它仅询问使用signed()的目的。请勿将此问题标记为重复。

我一直在寻找一种方法来获取数字中的尾随零。我在这里发现了一些“ Stanford University Write up HERE”,这给出了以下解释。

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;


为什么这最终会起作用?我对十六进制数字如何表示为二进制和按位运算符有所了解,但是我无法弄清楚此工作背后的直觉?工作机制是什么?

最佳答案

这段代码(从网络上)大部分是C,尽管v &= -signed(v);不是正确的C。目的是使其表现为v &= ~v + 1;

首先,如果v为零,则在&操作之后它仍为零,并且所有if语句都被跳过,因此得到32。

否则,&操作(在更正后)将清除最右边1左侧的所有位,因此在该点v包含单个1位。然后c递减为31,即可能结果范围内的所有1位。

然后,if语句一次确定其数字位置(位置编号的一位,而不是v的一位),清除应为0的位。

10-07 19:11
查看更多