階段の上下のスイッチをxorで繋ぐと、下で電気をつけて上で消すということができます。マインクラフトでもよく活用されます。しかし、実はxorにはもっと面白い性質がたくさんあります。今回はそれを紹介したいと思います。
2入力のXOR
まず2入力の場合。この場合、「どちらかがON、どちらかがOFF」のときに真を出力します。この性質によって、どちらかのスイッチを押すたびに階段の電気(出力)が切り替わります。2入力の場合はみなさんよくご存知だと思います。
| 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 |
出力が真の行を赤色にしてみました。これをみると 「入力のうち奇数個が真ならば真、偶数ならば偽」 になっています。つまり、入力の偶奇を判定しているわけです。
考察
まず、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が偶奇判定をしていると知っていると、競プロで役に立つことがあります。