Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

3入力以上のXORは奇数か判定している

今までXORは2入力固定だと思ってましたが、3入力以上でも問題ありませんでした。

2入力のXOR

まず2入力の場合。この場合、「どちらかがON、どちらかがOFF」のとき真を出力します。見方を変えると、真が奇数個のとき真を出力とも捉えることができます。

3入力のXOR

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

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

ABOUT
000
011
101
110

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

(A⊕B)⊕C=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 のうち、真となるものが奇数個である」と同値です。

const xor = (a, b) => !a && b || a && !b;
const hasOddNumberOfTrue = (...args) => args.reduce(xor, false);

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