1

最近我遇到了这个问题，它要求您返回二进制字符串中连续数字的数量，从左到右（so 11101001 = 3, 011111 = 0, 111101 = 4, 等）。关键是只使用二进制操作数，并且没有任何类型的循环。

在网上浏览了一下（感谢谷歌）后，我发现了其他人提出的这个解决方案，并希望更好地帮助理解它。

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正在被转移和否定，但我不知道这如何帮助解决任何问题。

4

2 回答 2

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

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

  1. v >> 16将 的值v（此时是 的值x）向右移动 16 位。这个表达式的低 16 位是v的高 16 位，有趣的是，这个表达式的高 16 位是实现定义的。我使用过的 C 编译器已将有符号值的右移作为算术移位执行，您发布的代码似乎依赖于这一事实，但情况并非如此。有关详细信息，请参阅此问题的答案。

  2. 运算符对~步骤 1 中生成的值执行按位补码。这里的重要观察是，当且仅当 (a) 的前 16 位v全为 1，并且 (b) 使用的 C 编译器执行算术移位时，那么步骤 1 中表达式的所有位都将为 1，这意味着~(v>>16)它将为零。

  3. 运算符对第!2 步中产生的值执行逻辑否定，这意味着!(~(v>>16))当且仅当第 2 步中的值为零（意味着前 16 位v全为 1）时，它才会为 1。否则，该值将为零。

  4. Finally, the << 4 is just a multiplication by 16. So r is assigned the value 16 if the top 16 bits of x were set to 1, or the value zero if any of the top 16 bits were 0s (or if the C compiler being used performs a logical right shift).

Next, this line:

v <<= r;

If the top 16 bits of v are all 1s—meaning that the value of r is 16—then we don't need to examine those bits any further, so this line shifts v to the left by 16 bits, which essentially discards those top 16 bits that we've already examined, and places the eight next-most-significant bits in the topmost positions, so we can examine those next.

另一方面，如果 的前 16 位v并非全为 1（即 的值为r0），那么 的后16位就v变得无关紧要了，因为无论前导 1 的位数v是多少，我们都知道它必须小于 16。因此，在这种情况下，v <<= r保持 的值v不变，我们通过检查 中的 8 个原始最高位继续下一步v。

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

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

这里唯一不同的是，它r是用逻辑 OR 扩充的，而不是像在 16 位步骤中那样直接分配。在这种情况下，这在功能上等同于加法，因为我们知道 的值r以前是 0 或 16，而 的值shift同样是 0 或 8，并且这些值的 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，这显然比原始值的总位数少 1，因此在所有 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当且仅当其中的所有位x都是 1 时才为零，因此!(~x)在这种情况下为 1，在任何其他情况下为零。

于 2015-04-30T02:57:54.583 回答
1

好的，

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

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

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

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

    v   <<= r;

我们刚刚计算的位数（16 或零）向左移动。我们现在考虑要么原始顶部位的较小块，要么其他位的较小块，现在移动到顶部位置。

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

和以前一样的游戏，但现在我们只考虑一个 8 位块。

    r    |= shift;

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

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

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

如果设置了最高位，它只会翻转结果的最低位v；由于到目前为止代码尚未设置该位，因此^=可以很容易地使用+=or |=。然后我们有：

    return r + full;

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

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

于 2015-04-30T02:58:14.297 回答