了解使用二进制操作数计算二进制数中 1 的个数的函数

Question

最近我运行遇到了这个问题，它要求您 return 二进制字符串中从左到右的连续数（所以 11101001 = 3，011111 = 0、111101 = 4、等等）。关键是只使用二进制操作数，没有任何循环。

在网上看了一会（感谢Google），我发现这个解决方案是别人想出来的，希望能更好地帮助理解它。

int leftBitCount(int x) {
    int v = x;
    int r;  // store our result here
    int shift;
    int full = !(~x); // we must add one if we have 0xffffffff

    // Check the top 16 bits and add them to our result if they exist
    r     = !(~(v>>16)) << 4;
    v   <<= r;
    // check the remaining 8 bits
    shift = !(~(v >> 24)) << 3;
    v   <<= shift;
    r    |= shift;
    // remaining 4 bits
    shift = !(~(v>>28)) << 2;
    v   <<= shift;
    r    |= shift;
    // remaining 2 bits
    shift = !(~(v >> 30)) << 1;
    v   <<= shift;
    r    |= shift;
    // remaining 1 bits
    r    ^= 1&((v>>31));

    // remember to add one if we have 32 on bits
    return r + full;
}

据我所知，该函数显然检查了 32 位整数的前 16 位，然后根据它们是否全为 1 转到下 8 位，然后根据它们是否全为 1 转到下 4 位，然后2，然后是 1，等等

不幸的是，我有点不知道代码究竟是如何实现这一点的，希望得到一些帮助来理解。

例如，这里：

r     = !(~(v>>16)) << 4;
v   <<= r;

我可以看到 v 正在被移动和否定，但我不知道这如何帮助解决任何问题。

Answer 1

r = !(~(v>>16)) << 4;

这是这条线上发生的事情：

v >> 16将v的值（此时是x的值）右移16位。这个表达式的低 16 位是 v 的高 16 位，有趣的是，这个表达式的高 16 位是实现定义的。我使用过的 C 编译器将带符号的值右移作为算术移位，您发布的代码似乎依赖于这一事实，但事实并非如此。有关详细信息，请参阅 this question 的答案。
~ 运算符对步骤 1 中产生的值执行按位补码。这里的重要观察是当且仅当 (a) [=19 的前 16 位=] 都是 1，并且 (b) 正在使用的 C 编译器执行算术移位，然后所有步骤 1 中的表达式的位将为 1，这意味着 ~(v>>16) 将为零。
! 运算符对步骤 2 中产生的值执行逻辑非，这意味着当且仅当步骤 2 中的值为零（意味着 v 的前 16 位都是 1）。否则，该值为零。
最后，<< 4 只是乘以 16。因此，如果 x 的前 16 位设置为，r 的值为 16 1，或者如果前 16 位中的任何一位为 0（或者如果使用的 C 编译器执行逻辑右移）则值为零。

接下来，这一行：

v <<= r;

如果v的前16位全为1——也就是说r的值为16——那么我们就不需要再检查这些位了，所以这一行移位v 向左 16 位，这实际上丢弃了我们已经检查过的前 16 位，并将下一个最重要的八位放在最上面的位置，因此我们可以检查下一个。

另一方面，如果v的前16位不是全1——也就是说r的值为0——那么v的bottom16位就变得无关紧要了，因为无论v中前导1的位数是多少，我们都知道它一定小于16。所以在这种情况下，v <<= r 保持 v 的值不变，我们继续下一步，检查 v.

中最初的八个最高位

算法的其余部分基本上重复这些步骤，除了被检查的位数在每一步中下降一半。所以这段代码检查前 8 位：

shift = !(~(v >> 24)) << 3;
v <<= shift;
r |= shift;

这里唯一不同的是 r 使用逻辑或进行扩充，而不是像在 16 位步骤中那样直接赋值。在这种情况下，这在功能上等同于加法，因为我们知道 r 的值之前是 0 或 16，并且 shift 的值同样是 0 或 8，而 none这些值的 1 位出现在相应的位置。然后这段代码对前 4 位做同样的事情：

shift = !(~(v>>28)) << 2;
v <<= shift;
r |= shift;

然后前2名：

shift = !(~(v >> 30)) << 1;
v <<= shift;
r |= shift;

最后，前 1 名：

r ^= 1&((v>>31));

这样测试出来的位数是16 + 8 + 4 + 2 + 1 = 31，明显比原值的总位数差了一位，所以在全部32的情况下是不够的位为 1。假设所有 32 位都是 1，下面是 x 的原始值在每一步中将如何移位：

16-bit step: 123456789ABCDEFGHIJKLMNOPQRSTUVW
 8-bit step: HIJKLMNOPQRSTUVW----------------
 4-bit step: PQRSTUVW------------------------
 2-bit step: TUVW----------------------------
 1-bit step: VW------------------------------

到目前为止看到的代码从未考虑过的是 W 位，原始值的最低有效位。当且仅当它左边的所有位都为 1 时，该位才会成为结果的一部分，这意味着值中的所有位都为 1，这就是检查的目的在代码的顶部执行：

 int full = !(~x);

这与我们之前看到的按位补码和逻辑非的组合相同；当且仅当 x 中的所有位均为 1 时，~x 将为零，因此 !(~x) 在这种情况下将为 1，在任何其他情况下为零。

Answer 2

好的，

    int full = !(~x); // we must add one if we have 0xffffffff

按位求反运算符 (~) 翻转其操作数中的所有坑。如果操作数中的所有位都已设置，则结果为零，逻辑否定运算符 (!) 将其转换为值 1（真）。否则，逻辑否定将其操作数转换为 0（假）。

    // Check the top 16 bits and add them to our result if they exist
    r     = !(~(v>>16)) << 4;

操作数 v，假定为 32 位宽，右移以便其上半部分位最终位于结果的后 16 位中。代码似乎（不安全地）假设如果设置了符号位（即算术移位），空出的位将被填满，因此如果原始数字的前 16 位全部设置，则按位取反会产生零，逻辑否定将其转换为 1。将 1 (== 2^0) 左移四位得到 16 (== 2^4)，这是所讨论的位数。如果不是所有的前 16 位都是 1（或者一些但不是所有这些位都已设置，并且右移移入零而不是一个）那么你最终会得到 0 << 4，当然， 0.

    v   <<= r;

我们刚刚计算的位数（16 位或零位）向左移动。我们现在考虑将原始最高位的一小块，或者其他位的一小块，现在移到最高位置。

    shift = !(~(v >> 24)) << 3;
    v   <<= shift;

与以前相同的游戏，但现在我们只考虑 8 位块。

    r    |= shift;

将刚刚测量的位数（8 或零）添加到结果中。

其余的继续相同的模式，到这里：

    r    ^= 1&((v>>31));

如果设置了 v 的最高位，则简单地翻转结果的最低位；由于此时代码未设置该位，因此 ^= 可以很容易地成为 += 或 |=。那么我们有：

    return r + full;

请记住，如果参数的所有位都已设置，则 full 取值 1，否则为零。前面的代码已经用尽了一次设置 r 一位的所有技巧，因为它刚刚完成了最低有效位。如果输入值中确实多了一位，那么您需要使用 + 运算符将结果加 1 或模拟 6 位加法器。

请注意：此代码似乎依赖于某些实现定义的行为来完成其工作。您可以通过使用无符号整数而不是有符号整数来避免实现定义。您仍然需要稍微修正一下表达式，但我将其留给您解决。

了解使用二进制操作数计算二进制数中 1 的个数的函数

Understanding a function that uses binary operands to count the number of 1s in a binary number

c

binary-operators