Panda Noir

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

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

階段の上下のスイッチを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が偶奇判定をしていると知っていると、競プロで役に立つことがあります。