了解如何使用 C 中的按位运算符计算数字的尾随零

Question

注意- 这不是这个问题的重复 -并行计算右侧的连续零位（尾随）：解释？。signed()链接的问题有不同的上下文，它只询问使用的目的。不要将此问题标记为重复。

我一直在寻找一种方法来获取数字中尾随零的数量。我发现斯坦福大学在这里写了一篇有点无聊的文章，给出了以下解释。

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;

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

Answer 1

代码已损坏（存在未定义的行为）。这是一个固定版本，也更容易理解（并且可能更快）：

uint32_t v;  // 32-bit word input to count zero bits on right
unsigned c;  // c will be the number of zero bits on the right
if (v) {
    v &= -v; // keep rightmost set bit (the one that determines the answer) clear all others
    c = 0;
    if (v & 0xAAAAAAAAu) c |= 1; // binary 10..1010
    if (v & 0xCCCCCCCCu) c |= 2; // binary 1100..11001100
    if (v & 0xF0F0F0F0u) c |= 4;
    if (v & 0xFF00FF00u) c |= 8;
    if (v & 0xFFFF0000u) c |= 16;
}
else c = 32;

一旦我们知道只设置了一位，我们就一次确定结果的一位，方法是同时测试结果为奇数的所有位，然后测试结果设置为 2 的所有位，等等。

原始代码相反，从结果集的所有位开始（在 后面if (c) c--;），然后确定哪些位需要为零并清除它们。

由于我们一次学习一位输出，我认为使用位运算而不是算术来构建输出会更清楚。