奇数位的比特奇偶校验码

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;
}

- tippenein

---

你从哪里找到那个算法的？ - rnunes

不要使用 int，因为会发生溢出，这将导致未定义的行为。相反，请使用 unsigned 和 1u，这样可以定义好环绕行为。 - Jens Gustedt

这个算法不起作用。它对于0到255之间的所有值都返回1。 - undur_gongor

我取了奇数位二进制数，并对它们进行异或、与和或运算，其中异或是唯一给出有用结果的运算（至少我是这么认为的）。 - tippenein

可能是bitParity - 查找整数中奇数位的数量的重复问题。 - Troyseph

Answer 1

据我所知，您的奇偶校验函数实际上并不起作用 - 它似乎只有一半的时间能够得出正确的答案，这与返回随机结果（甚至只是始终返回0或1）的效果差不多。

有几种位级技巧实际上可以解决这个问题：http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive - 您可能想看看其中的最后一个： http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel。

- Paul R

---

我意识到我的完整代码不起作用，但是对于我尝试的值，x ^ (x-1) 似乎给出了有意义的答案。如果你是正确的，那么我应该放弃它并重新开始。 - tippenein

只需尝试输入值0、1、2和3，您就会发现它无法正常工作。 - Paul R

Answer 2

我会使用实际计数而不是利用数字表示的位级黑客技巧，这样既更安全，也更清晰易懂。当然，可能会更慢，但这是一个相当不错的折衷方案，特别是当人们对性能期望一无所知时。

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

更新：考虑到（奇怪而烦人的）限制，我的回应可能是在bithacks页面上给出的“naive”解决方案中取消循环。那不会很漂亮，但我可以去做一些有用的事情。 :)

- unwind

---

我肯定会使用循环来轻松计算每个位或者只是将所有位异或在一起，但是对于这个任务，我不允许使用控制结构。只能使用 | ^ & >> << ~ + ! 这些操作符。所以，你的回答是我的第一反应，但是行不通。 - tippenein

我已经拿到了一个之前写好的位计数代码，并且将结果与0x1进行了AND运算，以判断是否有奇数个位。然而，我通过暴力算法实现了bitCount(int x)算法；使用以下方式检查每个位： !!(x & (1<<bit#)) 目前这对我来说还不够好，但是这种方法已经解决了位奇偶性问题。 - tippenein

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");
    }
}

- sastanin