XOR

XOR（排他的論理和、Exclusive OR）は、2つの入力のうち一方のみが真（1）であるときに真を出力する論理演算である。記号としては「⊕」や「⊻」、または「^」などが用いられ、デジタル回路や暗号理論、誤り検出など幅広い分野で基礎的な役割を果たす。真理値表では、(0,0)→0、(0,1)→1、(1,0)→1、(1,1)→0 と定義される。

1 定義

1.1 真理値表

XORの真理値表は、2入力のすべての組み合わせに対する出力を示す。

1.2 論理式による表現

XORは論理式として次のように表される。

• A ⊕ B = (A ∧ ¬B) ∨ (¬A ∧ B)
• または A ⊕ B = (A ∨ B) ∧ ¬(A ∧ B)

1.3 他の論理ゲートとの関係

XORはAND、OR、NOTの組み合わせで構成可能である。また、XNOR（否定排他的論理和）はXORの否定に相当する。NANDゲートのみでXORを構成することもできる（4個のNANDで実現される）。

2 代数的性質

2.1 交換則・結合則

XORは交換則と結合則を満たす。

• 交換則：A ⊕ B = B ⊕ A
• 結合則：(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

これにより、多入力XORの演算順序は任意に変更できる。

2.2 単位元と逆元

XORにおける単位元は0である（A ⊕ 0 = A）。任意の入力Aに対する逆元はA自身である（A ⊕ A = 0）。この性質は、暗号や誤り訂正において重要な役割を果たす。

2.3 べき等性の欠如

XORはべき等性を持たない。すなわち、A ⊕ A = 0 ≠ A（Aが1の場合）。これにより、同一値の繰り返し適用で元の値が打ち消される。

3 応用

3.1 デジタル回路

3.1.1 半加算器と全加算器

半加算器は2つの1ビット入力を加算し、和（XOR）と桁上がり（AND）を出力する。全加算器はさらに下位からの桁上がりを考慮し、3入力のXORと2つのANDで構成される。

3.1.2 パリティチェック

XORはパリティビットの生成に利用される。データビットのXORをとることで偶数パリティまたは奇数パリティを計算し、伝送誤りの検出に用いる。

3.2 暗号理論

3.2.1 ワンタイムパッド

ワンタイムパッドでは、平文と鍵（乱数）のXORをとることで暗号文を得る。復号は同一鍵とのXORで行う。この方式は情報理論的に完全な秘匿性を持つ。

3.2.2 ブロック暗号における利用

多くのブロック暗号（AESなど）では、XORがラウンド関数内で鍵とデータの混合、またはサブバイト変換後の拡散に用いられる。

3.3 誤り検出・訂正

3.3.1 CRCとの関係

巡回冗長検査（CRC）の計算では、シフトレジスタを用いたXOR演算が中心となる。多項式除算の剰余をビット単位のXORで求める。

3.3.2 ハミング符号

ハミング符号では、複数のパリティビットがデータビットのXORにより生成される。受信側でXORを再計算することで、1ビット誤りの位置を特定・訂正できる。

4 拡張と関連概念

4.1 多入力XOR

多入力XORは、入力のうち奇数個が1であるときに1を出力する。これはパリティ関数に一致し、結合則により任意の順序で計算可能である。

4.2 XORと排他的論理和の違い

「XOR」と「排他的論理和」は同義だが、日本語環境では「排他的論理和」が正式な用語である。ただし、日常的には略称XORが広く使われる。

4.3 ソフトウェアにおける実装

多くのプログラミング言語ではXOR演算子（^やxor）が用意されている。ビット演算として整数値の各ビットに独立に適用される。また、変数のスワップにXORを用いるテクニック（x ^= y; y ^= x; x ^= y）が知られているが、現代のコンパイラでは推奨されない。