おさらい: まず2入力の場合 の xor。この場合は、「どちらかがON、どちらかがOFF」のときに真を出力します。
| A | B | A^B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
3入力のXOR
3入力のXORの真偽表は以下のようになります。
| A | B | C | A^B^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 |
出力が真の行(赤色の行)に着目してみると、 入力のうち奇数個が真ならば真、偶数ならば偽 だと気づきます。つまり、3入力の場合には入力の偶奇を判定できています。
考察
まず、2入力のXORは「真の個数が1個ならば真」を出力していました。逆に、出力側から見ると xorが真を出力したならば、真の入力は1個である と言えます。
3入力のXORは A1 ^ A2 ^ A3 と表せます。まず、A1 ^ A2 が真ならば、A1、A2のうち真は1つだけです。偽ならば0 or 2個です。
A1^A2とA3とXORをしてみることを考えます。真ならばA1^A2とA3のうち真は1つだけです。ということは、A1、A2、A3のうち真は1つ or 3つです。偽ならば真は0個 or 2つです。
N入力のXOR
以上を踏まえると、
A1 ^ A2 ^ A3 ^ ... ^ An は「A1, ... , An のうち、真となるものが奇数個であるか？」と同値です。
const xor = (a, b) => !a && b || a && !b; const hasOddNumberOfTrue = (...args) => args.reduce(xor, false); hasOddNumberOfTrue(true, true, true); // true hasOddNumberOfTrue(false, false, false); // false hasOddNumberOfTrue(true, false, true); // false
XORが偶奇判定をしていると知っていると、競プロで役に立つことがあります。
