7

x の 0 の数が奇数の場合に 1 を返すように、ビット文字列のパリティを見つけようとしています。
私は基本的なビット単位の操作しか使用できず、これまでのところほとんどのテストに合格していますが、次の2つのことを疑問に思っています:

  1. x ^ (x + ~1) が機能するのはなぜですか? 私はこれに出くわしましたが、ビット数が奇数の場合は1、偶数の場合は何かを与えるようです。7 = 0b0111 であるため、7^6 = 1 と同様

  2. これは、これに対する問題解決の正しい方向ですか? 私の問題は、特定の 2 の補数をオーバーフローするため、最初の操作、具体的には (x + ~1) に起因すると想定しています。ありがとう

コード：

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

3 に答える 3

4

あなたのパリティ関数は、私が知る限り実際には機能しません-約半分の時間で答えが得られるようです。これは、ランダムな結果を返すのと同じくらい良いです(または常に0または1を返すだけです) .

実際に動作するビット レベルのハックがいくつかあります: http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive -おそらくこれらの最後の 1 つを見たいと思うでしょう: http://graphics.stanford .edu/~seander/bithacks.html#ParityParallel

于 2011-09-23T15:02:02.013 に答える
3

数値の表現を利用するビットレベルのハックではなく、実際のカウントを使用します。これにより、安全性が向上し、クリーンで理解しやすくなります。もちろん、おそらく遅くなりますが、特に期待されるパフォーマンスについて何も知らない場合は、これは非常に良いトレードオフです。

これを行うには、1 ビットの数をカウントするコードを記述するだけです。最も単純なソリューションは、通常、ループに要約されます。

更新: (奇妙で迷惑な) 制限を考えると、私の応答はおそらく、 bithacksページの「単純な」ソリューションで指定されたループを巻き戻すことです。それはきれいではありませんが、私は何か役に立つことをすることができます. :)

于 2011-09-23T14:45:25.200 に答える
1

ビット パリティは、次のように行うことができます。

#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");
    }
}
于 2011-09-23T15:05:18.460 に答える