c - 为什么这个 bitcount 代码没有通过测试？

Question

我现在在 bit.c 实验室工作。我制作了函数 bitCount。我认为它很完美，但它无法通过测试。我不知道为什么。

int bitCount(int x) {
    unsigned int a = 0x01010101;
    int b;
    int result = 0;
    result += a&x;
    result += a&(x>>1);
    result += a&(x>>2);
    result += a&(x>>3);
    result += a&(x>>4);
    result += a&(x>>5);
    result += a&(x>>6);
    result += a&(x>>7);
    b = result + result >> 8;
    b = b + result >> 16;
    b = b + result >> 24;
    return b&0xff;
}

Answer 1

您对错误的位求和，因为在这些行中 + 的优先级高于 >>:

b = result + result >> 8;
b = b + result >> 16;
b = b + result >> 24;

假设结果== 0x01020304:

• 表达式result + result >> 8将得到0x01020304 + 0x01020304 >> 8，然后是0x02040608 >> 8，并且最后0x020406。
• 表达式 b = b + result >> 16 将得到 0x020406 + 0x01020304 >> 16，然后是 0x0104070A >> 16 ，最后是0x010407。
• 表达式 b = b + result >> 24 将得到 0x010407 + 0x01020304 >> 24，然后是 0x0103070B >> 24 ，最后是0x010307。
• 最后表达式 b&0xff 结果为 0x07。这不是我们期望的结果 0x0A 或 10。

因此您必须:

1. 确保在添加之前完成移位。使用括号()。
2. 使用 & 0xFF 屏蔽不必要的位。请注意，这并不是绝对必要的，因为有 b&0xff，但在我看来，它使意图更加清晰。

示例:

b = (result & 0xFF) + (result >> 8 & 0xFF);
b = b + (result >> 16 & 0xFF);
b = b + (result >> 24 & 0xFF);