注意-这不是此问题的重复-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的位。