0と1を取る入力が3個以上あるとき、XORを順に適用した結果は「1の個数が奇数なら1、偶数なら0」になります。本記事で扱うのは3入力以上の二値論理です。各入力が3種類の値を取る「三値論理」とは区別してください。
まずは2入力のXORを確認
XOR（排他的論理和）は、2入力の値が異なるときに1、同じときに0になります。記号は⊕です。
| A | B | A⊕B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
3入力は2入力ずつ計算する
A⊕B⊕Cは、まずA⊕Bを計算し、その結果とCのXORを取れば求められます。たとえば、1⊕1⊕1＝0⊕1＝1です。「1がちょうど1個のときだけ1」と覚えると、3個の1がある場合に間違えてしまいます。
| A | B | C | 1の個数 | A⊕B⊕C |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 2 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 2 | 0 |
| 1 | 1 | 0 | 2 | 0 |
| 1 | 1 | 1 | 3 | 1 |
4入力以上でも奇数・偶数で判断
XORでは、0を加えると結果は変わらず、1を加えると結果が反転します。0から始めて入力を順に計算すると、1が現れるたびに0と1が切り替わります。このため、1の個数の奇数・偶数で結果が決まります。
例：1⊕0⊕1⊕1＝1（1が3個）。1⊕1⊕1⊕1＝0（1が4個）。これはビット列全体を一つの入力として数えるのではなく、各ビット位置で独立して行う計算です。
確認問題
1⊕0⊕1⊕0⊕1の結果はいくつでしょうか？
解答・解説を見る
1です。1が3個あり、奇数個なので1になります。順に計算しても、1→1→0→0→1となります。
AND・ORやビット列の計算も練習する
無料noteでは、AND・OR・XOR・NOTの違い、ビット列の演算、マスク処理を解説しています。ここで理解したXORを、ほかの演算と比較して定着させましょう。
ほかの学習テーマは、資格・目的別のnote教材ナビから選べます。
参照
元記事の参照先：排他的論理和の解説。2入力XORの仕様はTexas InstrumentsのXORゲート資料でも確認できます。
コメント