甚至无符号整数的奇偶校验

/*A value has even parity if it has an even number of 1 bits. *A value has an odd parity if it has an odd number of 1 bits. *For example, 0110 has even parity, and 1110 has odd parity. *Return 1 iff x has even parity. */ int has_even_parity(unsigned int x) { } 

我不知道从哪里开始编写这个函数，我认为我将值作为数组循环并对它们应用xor操作。 会有类似下面的工作吗？ 如果没有，接近这个的方法是什么？

 int has_even_parity(unsigned int x) { int i, result = x[0]; for (i = 0; i < 3; i++){ result = result ^ x[i + 1]; } if (result == 0){ return 1; } else{ return 0; } } 

Answer 1

选项＃1 – 以“明显”的方式迭代位，在O（位数）：

 int has_even_parity(unsigned int x) { int p = 1; while (x) { p ^= x&1; x >>= 1; // at each iteration, we shift the input one bit to the right } return p; 

选项＃2 – 仅迭代设置为1的位，在O（1的数量）：

 int has_even_parity(unsigned int x) { int p = 1; while (x) { p ^= 1; x &= x-1; // at each iteration, we set the least significant 1 to 0 } return p; } 

选项＃3 – 使用SWAR算法计算1，在O（log（位数））：

http://aggregate.org/MAGIC/#Population%20Count%20%28Ones%20Count%29

Answer 2

您不能将整数作为数组访问，

 unsigned x = ...; // x[0]; doesn't work 

但您可以使用按位运算。

 unsigned x = ...; int n = ...; int bit = (x >> n) & 1u; // Extract bit n, where bit 0 is the LSB 

假设有32位整数，有一种聪明的方法可以做到这一点：

 unsigned parity(unsigned x) { x ^= x >> 16; x ^= x >> 8; x ^= x >> 4; x ^= x >> 2; x ^= x >> 1; return x & 1; }