/*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) {
}
我不确定从哪里开始编写这个函数,我想我将值作为数组循环并对它们应用异或运算。 会像下面这样工作吗?如果没有,有什么方法可以解决这个问题?
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;
}
}
最佳答案
选项 #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 算法以 O(log(位数)) 计算 1:
http://aggregate.org/MAGIC/#Population%20Count%20%28Ones%20Count%29
关于c - 无符号整型的偶校验,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21589674/