今までXORは2入力固定だと思ってましたが、3入力以上でも問題ありませんでした。
2入力のXOR
まず2入力の場合。この場合、「どちらかがON、どちらかがOFF」のとき真を出力します。見方を変えると、真が奇数個のとき真を出力とも捉えることができます。
3入力のXOR
説明するよりも、真偽表を見てもらう方が早いです。
次の表は2入力のXORの真偽表です。
| A | B | OUT |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
このOUTをA'として、A'とCの真偽表が次の表です。
(A⊕B)⊕C=A'⊕Cということです。
| A' | C | OUT |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 0 | 1 | 1 |
まとめると以下のようになります。
| A | B | C | OUT |
| 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 |
わかりやすいように、出力が真の行を赤色にしてみました。気が付きましたか?そうです。 「真が奇数個入力されたときは真、偶数個のときは偽」 になっています。
考察
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、実におもしろいですね。何かに使えそうです