2 
/*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;
    }
}
4

2 に答える 2

3

オプション #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 - O(1 の数) で、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 - O(log(ビット数)) で 1 をカウントするために SWAR アルゴリズムを使用します。

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

于 2014-02-05T22:21:12.523 に答える