読者です 読者をやめる 読者になる 読者になる

へなちょここーだー

プログラミング初心者がtopcoderなどの競技プログラミングに挑戦。勉強したアルゴリズムなどを書いていきます。現在topcoder緑でcodeforces青。どちらもDiv1昇格を目指しています。

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)でしか計算していませんが、これを拡張して実数でも計算出来るようにします。

実数での計算

例えば、19 XOR 5について考えてみます。まずは、この2つの数を2進法で表します。次にその2数を桁をそろえて並べます。そして、すべての桁においてXORの計算をすれば完了です。今回の例題は次のようにして解きます。
f:id:augusuto04:20150504032150j:plain
繰り上がりの計算を忘れた2進数の足し算だと思えば良いでしょうか。いいえ、各ビットにおいてXORを計算していると考えましょう。C++でこの計算を行うときは次のようにするだけです。

//a XOR bを返す
return a ^ b;

Javaなどでもこの表現みたいですね。