c位运算bug

Question

x 的来源已更新。这是一项任务，我被要求履行该职能。作业的要求是我不能更改参数类型或进行任何类型转换。所以我有这个问题。

我想使用c实现位计数。这是代码:

int bitCount(int x) {
    int mask1 = 0x55555555;
    int mask2 = 0x33333333;
    int mask3 = 0x0f0f0f0f;
    int mask4 = 0x00ff00ff;
    int mask5 = 0x0000ffff;
    //x = 0xffffffff;
    if (x != 0xffffffff) {
        exit(0);
    }
    printf("%x\n", x);
    x = (x & mask1) + ((x >> 1) & mask1);
    printf("%x\n", x);
    x = (x & mask2) + ((x >> 2) & mask2);
    printf("%x\n", x);
    x = (x & mask3) + ((x >> 4) & mask3);
    printf("%x\n", x);
    x = (x & mask4) + ((x >> 8) & mask4);
    printf("%x\n", x);
    x = (x & mask5) + ((x >> 16) & mask5);
    printf("%x\n", x);

    return x;
}

当x = -1(或十六进制的0xffffffff)时，答案应该是0x20。但实际上输出是:

ffffffff
aaaaaaaa
24444444
6080808
e0010
1e

如果我取消注释该行 代码中的“x = 0xffffffff”，输出变为:

ffffffff
aaaaaaaa
44444444
8080808
100010
20

操作系统是Mac OS X。gcc版本是:

gcc --version

配置为:

--prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 7.0.2 (clang-700.1.81)
Target: x86_64-apple-darwin14.5.0
Thread model: posix

为什么？

Answer 1

首先，负整数右移是实现定义的:

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

但是，假设我们使用的是 x86，并且负整数右移的工作方式与 2 的补码表示完全一样，并产生正确的 32 位值。如果 int x = 0xFFFFFFFF 则 x & mask1 为 0x55555555 并且 (x >> 1) & mask 也是0x55555555，两者都是正数；它们的总和是 0xAAAAAAAA 然后

x = (x & mask1) + ((x >> 1) & mask1);

如果 int 是 32 位宽，则会导致有符号整数溢出，因此您的代码具有未定义的行为。您应该必须使用unsigned int来进行这种位操作，而不是int。

我无法在我的计算机上重现您的错误，但我可以通过在溢出加法后屏蔽 x 中的符号位来获得相同的输出:

x = (x & mask1) + ((x >> 1) & mask1);
x = x & 0x7FFFFFFF;

只有通过此更改，我才能获得您所观察到的错误输出:

ffffffff
aaaaaaaa
24444444
6080808
e0010
1e

<小时/>

当 64 位处理器变得更加普遍时，32 位整数的这种未定义行为增加了很多 - 根据 C 标准，编译器可以使用 64 位寄存器来处理 32 位有符号 整数，因为它们永远不会溢出，如果你溢出它们，你的“32位”int变量甚至可能最终包含一个64位值。