XOR(排他的論理和)の計算
Grundy数を計算する際にXORの計算をしました。Exclusive orとか日本語では排他的論理和と言われているものですね。基本的なことですが、どうやって計算するのかを紹介します。
まずは基本から
まずは表で計算結果を見てみましょう。
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
このようになります。なお、0をfalseあるいは偽、1をtrueあるいは真に置き換えても大丈夫です。プログラミングでboolを使ったことある方ならよく見る表現ですよね。同じものを入力すれば0、違うものを入力すれば1になるのがXORです。では、入力の個数を増やして見ましょう。
| A | B | C | A XOR B XOR C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
こんな感じです。個人的に、今回の規則性はこの並びだと分かりにくいと思うので並べ直してみます。
| A | B | C | A XOR B XOR C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 |
これで規則性が見えてきたのではないでしょうか。1が偶数個(0個も含む)あれば出力は0、1が奇数個あれば出力は1になります。入力がさらに多くてもこの規則通りになります。なお、計算の順番が違っても計算結果は同じになるため
(A XOR B) XOR C
A XOR (B XOR C)
のどちらで解いても良いですし、
(A XOR C) XOR B
と順番を入れ替えても構いません。では、今のところ真理値(0と1あるいはfalseとtrue)でしか計算していませんが、これを拡張して実数でも計算出来るようにします。
