c位操作错误

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

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

结果E1 >> E2是 E1右移位E2位置.如果E1具有无符号类型或者E1具有有符号类型和非负值,则结果的值是商的整数部分E1 / 2^E2.如果E1具有带符号类型和负值,则结果值是实现定义的.

但是,让我们假设我们使用的是x86,负整数的右移实际上就像是2的补码表示,并产生一个正确的32位值.如果int x = 0xFFFFFFFF那时x & mask1是0x55555555,(x >> 1) & mask也是0x55555555,两者都是积极的; 而他们的总和0xAAAAAAAA,然后

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

如果是32位宽,则导致有符号整数溢出int,因此您的代码具有未定义的行为.你应该使用unsigned int这样的比特而不是int.

我不能在我的计算机上重现你的错误,但是我可以通过x在溢出添加之后屏蔽符号位来获得相同的输出:

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

只有通过此更改,我才能获得您正在观察的错误输出:

ffffffff
aaaaaaaa
24444444
6080808
e0010
1e

这与32位整数未定义行为有所增加,当64位处理器已经变得越来越普遍了很多-根据C标准的编译器允许使用32位的64位寄存器签署的整数,因为他们从来没有溢出和如果你溢出它们,你的"32位" int变量甚至可能最终包含64位值.