奇数位的位奇偶校验码

Question

我正在尝试查找位串的奇偶校验，以便如果 x 有奇数个 0，则返回 1。
我只能使用基本的按位运算，到目前为止我已经通过了大多数测试，但我想知道两件事：

1. 为什么 x ^ (x + ~1) 有效？我偶然发现了这一点，但如果位数为奇数，它似乎给你 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

Answer 2

我会使用实际计数，而不是利用数字表示的位级黑客，这样既感觉更安全，也更干净且易于理解。当然，可能会慢一些，但这是一个相当不错的权衡，尤其是当人们对性能预期一无所知时。

为此，只需编写代码来计算 1 位的数量，最直接的解决方案通常归结为循环。

更新：鉴于（奇怪且烦人的）限制，我的回应可能是unwind "naive" 解决方案中给出的循环 <一个href="http://graphics.stanford.edu/~seander/bithacks.html" rel="nofollow">bithacks 页面。那不太好，但我可以去做一些有用的事情。 :)

Answer 3

位奇偶校验可以这样完成：

#include <stdio.h>

int parity(unsigned int x) {
    int parity=0;
    while (x > 0) {
       parity = (parity + (x & 1)) % 2;
       x >>= 1;
    }
}

int main(int argc, char *argv[]) {
    unsigned int i;
    for (i = 0; i < 256; i++) {
        printf("%d\t%s\n", i, parity(i)?"odd":"even");
    }
}