c - 奇数位的位奇偶校验码

Question

我试图找到一个位串的奇偶校验，如果 x 有奇数个 0，它会返回 1。
我只能使用基本的按位运算，到目前为止我已经通过了大部分测试，但我想知道两件事:

1. 为什么 x ^ (x + ~1) 有效？我偶然发现了这一点，但如果有奇数位，它似乎给你 1，如果有偶数，它似乎给你其他东西。喜欢 7^6 = 1 因为 7 = 0b0111

2. 这是解决问题的正确方向吗？我假设我的问题源于第一个操作，特别是 (x + ~1) 因为它会溢出某些 2 的补码。谢谢

代码:

int bitParity(int x) {
    int first = x ^ (x + ~1);
    int second = first ^ 1; // if first XOR gave 1 you'll return 0 here
    int result = !!second;
return result;
}

Answer 1

据我所知，你的奇偶校验函数实际上并没有起作用——它似乎在大约一半的时间内得到了正确的答案，这与返回一个随机结果(或者甚至只返回 0 或 1 所有时间)。

有几个位级黑客确实实际工作于:http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive - 你可能想看看最后一个:http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel