5

ある数に s がいくつあるかを数える問題はすでにありますが1、この問題は 1 が偶数か奇数かを判断する問題です。

ループまたは条件 (switch を含む) ステートメントは使用できません。また、除算、乗算、モジュラス演算子は避ける必要があります。より具体的には、32 ビットの符号なし整数であると想定できます。

実際、私はすでに実装を持っていますが、それが機能する理由を理解できません。その正しさの証拠や新しいアイデアは非常に役に立ちます。

int even_ones(unsigned x)
{
    x ^= x>>16;
    x ^= x>>8;
    x ^= x>>4;
    x ^= x>>2;
    x ^= x>>1;

    return !(x & 1);
}
4

4 に答える 4

11

排他的または操作が何をするか知っていると思います-2^つのビットが同じ値に設定されている場合、結果は0-そうでない場合は1. したがって、2 つの 1 ビット数 A と Bがある場合、A と B のいずれかが both 、または bothA^Bの場合、ゼロになります。つまり、との 1 の合計は偶数です...01AB

では、一度に 2 ビットずつ実行してみましょう。C と D は 2 ビットの数値です。可能な組み合わせは次のとおりです。

C    D    C^D
00   00   00   even
01   00   01    odd
10   00   10    odd
11   00   11   even
00   01   01    odd
01   01   00   even
10   01   11   even
11   01   10    odd
00   10   10    odd
01   10   11   even
10   10   00   even
11   10   01    odd
00   11   11   even
01   11   10    odd
10   11   01    odd
11   11   00   even

ご覧のとおり、各インスタンスでの演算はビット数を半分に減らし、1奇数で開始した場合、結果のビット数は奇数になります (ペアの1s は相殺されますが、他のすべては変更されないため)。 .

これで、より大きな数値 (4 ビット、8 ビット、16 ビット) で開始したときに同じことが引き続き当てはまる理由が明らかになったはずです。本質的に、アルゴリズムは 32 ビットの数値で始まり、それを 2 つの 16 ビットの数値に分割します。「2 つの 1」を取り除くことで、ビット数を半分に減らします。次に、残りの半分で動作し、残りのビットが 1 つだけになるまで繰り返します。そのビットが 1 (奇数) か 0 (偶数) かをテストすることで、答えが得られます。

明確でない場合は、x ^= x>>16実際に上位 16 ビットを下位 16 ビットにシフトし、そこで排他的論理和を生成するような操作を行います。実際には上位ビットをクリアしないため、「混乱が取り残されます」。しかし、アルゴリズムは次の混乱を無視します。以下を参照してください (簡単にするために 8 ビットから始めます)。

x =      abcdefgh 
x >> 4 = 0000abcd
new x  = abcdijkl
x >> 2 = 00abcdij
new x  = abmnopqr
x >> 1 = 0abmnopq
new x  = astuvwxy

この場合、最後の桁yは と の XOR でrあり、さらにとqの XOR です。これらは、それぞれ、、 、の XOR です。ご覧のとおり、すべてのビットの XOR が得られました。上で説明したように、これは、最下位ビットが現在 aまたは aであるかどうかに応じて、「すべて偶数」または「すべて奇数」のいずれかを意味します。l,jk,ih,df,bg,ce,a10

これが役に立ったことを願っています。

于 2013-10-15T04:25:45.977 に答える
5

バイトまたはワードのパリティをすばやく計算するためのいくつかのバリアントを次に示します。正確にどの方法が最速になるかは、CPU と、さまざまな基本操作が互いに相対的にどれだけ速いかによって異なります。したがって、これがなんらかの理由でアプリケーションのボトルネックになっている場合は、それぞれをプロファイルして、ターゲット マシンで最適に動作するものを見つける必要があります。

あなたのソリューションは、 「並列でパリティを計算する」実装と非常に似ていますが、最後に巧妙な最適化が行われていません。ここで何が起こっているかというと、各ステップで、残りのビットが 1 ビットになるまで、半分のビットと残りの半分のビットを XOR しています。ワードのパリティは、1 が偶数個ある場合は 0、1 が奇数個ある場合は 1 です。または同等に、ワードのパリティは、ワード内のすべてのビットの XOR です。

XOR 演算子は交換可能かつ結合的であるため、単語内のすべてのビットがどのように XOR されるかを並べ替えることができます。そのため、各ビットを個別に結果に XOR してすべてのビットの XOR を計算する代わりに、上位半分のビットと下位半分のビットを XOR し、対象となるビット数を半分に減らします。残り 1 ビットになったら完了です。

于 2013-10-15T04:07:58.790 に答える
2

この XOR は最上位 16 ビットと最下位 16 ビットであることに注意してください。

x ^= x>>16;

次に、シリーズは 2 番目の最下位 8 ビットと最下位 4 ビットの XOR を続けます。最上位 16 ビットは単純にジャンクであり、そこで何が起こっても無視できることに注意してください。

x ^= x>>8;

というように、1 ビットになるまで、2 番目の最下位 4 ビットと最下位 4 ビットの XOR を続けます。今では、最下位ビットを除くすべてのビットはがらくたであり、最後の行はビットごとに 1 を使用して最下位ビットだけを取得し、偶数テストのために反転します。

おそらく、次のように書いた方が簡単です。

int even_ones(unsigned x)
{
    a = (x ^ x>>16) & 0x0000FFFF;
    b = (a ^ a>>8)  & 0x000000FF;
    c = (b ^ b>>4)  & 0x0000000F;
    d = (c ^ c>>2)  & 0x00000003;
    e = (d ^ d>>1)  & 0x00000001;
    return !(e&1);
}

なぜこれが機能するのですか？XOR は、キャリーなしのビットごとの加算に相当するためです。

于 2013-10-15T04:25:47.930 に答える
-3

お役に立てれば ：：

   enum {
      EVEN,
      ODD
    } even_odd;

unsigned int check_even_odd_no_of_ones(unsigned int num)
{
  if(num_of_ones(num) & 1)
    return ODD;
  else
    return EVEN;
}

ありがとうございました

于 2013-10-15T05:42:36.180 に答える