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

Panda Noir

JavaScript の限界を究めるブログです。

3入力のXORがあるらしいです

今まで2入力固定だと思ってました…よく考えると、3入力以上でも問題ないです。

2入力のXOR

まず2入力の場合。この場合、「どちらかがON、どちらかがOFF」言い換えると「ONになっているものが奇数個」のとき真を出力します。

3入力のXOR

説明するよりも、真偽表を見てもらう方が早いです。

次の表は2入力のXORの真偽表です。

ABOUT
000
011
101
110

このOUTをA'として、A'とCの真偽表が次の表です。

A'COUT
000
101
110
011

まとめると以下のようになります。

ABCOUT
0000
0011
0101
0110
1001
1010
1100
1111

わかりやすいように、出力が真の行を赤色にしてみました。気が付きましたか?そうです。 「真が奇数個入力されたときは真、偶数個のときは偽」 になっています。

考察

2入力のXORは「真となっている個数が奇数個なら真」を返していました。しかし、真偽表をよく見ると、「真を出力したならば、それまでの入力に真は奇数個」とも言えます。

3入力のXORは A1 ^ A2 ^ A3 と表せます。A1 ^ A2 が真ならば、入力に真は1つです。偽ならば0 or 2個です。

そして、これとA3とXORをしてみると、これまたうまいことできていて、真の総数が奇数個(1 or 3個)のときのみ真、偶数個なら偽になります。

N入力のXOR

以上を踏まえると、

A1 ^ A2 ^ A3 ^ … ^ An は「A1, … , An のうち、真となるものが奇数個である」という命題と同値です。

XOR、実におもしろいですね。何かに使えそうです