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

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 的位数，最直接的解决方案通常归结为一个循环。

更新：鉴于（奇怪和烦人的）限制，我的回应可能是解开在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");
    }
}