无符号整数的偶校验 [英] Even parity of a unsigned int

问题描述

/*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操作. 可以进行以下工作吗?如果没有，那么解决该问题的方法是什么?

I'm not sure where to begin writing this function, I'm thinking that I loop through the value as an array and apply xor operations on them. Would something like the following work? If not, what is the way to approach this?

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(数量为1s)处进行迭代):

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

这篇关于无符号整数的偶校验的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！