XOR演算子を徹底解説：GF(2)で理解するビット演算と実用応用
エバープレイ編集部XOR演算子とは――概要
XOR（排他的論理和、exclusive OR）は、2つのビットやブール値を比較して「どちらか一方だけが真（1）であるときに真になる」演算です。ビット演算ではビット単位で適用され、ソフトウェアやハードウェアの基礎的な操作として広く使われます。数学的には GF(2)（2元体）における加算（加算は 2 での剰余）と一致し、符号なし整数のビットごとの和（キャリーを無視）として理解できます。
真理値表と基本的な性質
2入力のXORの真理値表は次の通りです。
- 0 XOR 0 = 0
- 0 XOR 1 = 1
- 1 XOR 0 = 1
- 1 XOR 1 = 0
ここから導かれる主な性質：
- 可換性：a ^ b = b ^ a
- 結合性：a ^ (b ^ c) = (a ^ b) ^ c
- 単位元：a ^ 0 = a
- 自己逆元性（自己相殺）：a ^ a = 0
- 否定との関係（1 ビット）：a ^ 1 = ¬a（ビット幅が固定の場合、すべて1とのXORはビット反転）
- ブール値に対しては「a XOR b」は「a != b」と同値（真偽が異なれば真）
ビット演算としてのXOR
プログラミング言語では一般に ^ がビット単位の排他的論理和（bitwise XOR）を表します（C/C++/Java/JavaScript/Pythonなどで使用）。整数の各ビット位置に対してXORを行うため、マスクによるビットの切り替え（トグル）、パリティ計算、シンプルなチェックサムなどに使われます。
例：8ビットで 0b10110010 と 0b01011100 の XOR は 0b11101110 です。
ブール論理とプログラミングでの扱いの違い
- 多くの言語で ^ は整数に対するビット演算子だが、言語によってはブールに対しても論理XORとして振る舞う（JavaやC#では boolean に対する ^ は論理XOR）。
- JavaScript の ^ は常に数値に変換してからビット演算を行うため、論理的な真偽のみのXORを意図する場合は !== を用いるのが確実。
- Python では bool が int のサブクラスなので True/False に対して ^ を使えるが、論理XORの用途なら != を使うことが多い。
等式と代数的表現（GF(2)として）
XORは GF(2) 上の加算と同等であり、ビットごとの足し算（繰り上がりなし）として振る舞います。これにより線形代数的な操作（線形独立、基底、ガウスの消去法）をビット列に対して行うことが可能です。
重要な恒等式：
- a ^ a = 0
- a ^ 0 = a
- a ^ b = (a & ~b) | (~a & b)（論理式による表現）
- AND は XOR に関して分配的：a & (b ^ c) = (a & b) ^ (a & c)
注意：XOR が AND に分配するわけではない（XORはAND上で一般に分配則を満たさない）。反例を挙げると a=1,b=1,c=0 のとき a ^ (b & c) ≠ (a ^ b) & (a ^ c) です。
実用例・アルゴリズムでの活用
- 重複のある配列で一意な要素を見つける：全要素を XOR していくと、ペアで存在する要素は相殺され、1つだけ現れる値が残る（O(n)、追加メモリ不要）。
- スワップ演算（テンポラリ変数なし）：a = a ^ b; b = a ^ b; a = a ^ b。ただし参照が同じ変数やオーバーフロー・可読性を考慮すると実用上の利用は限定的。
- パリティ計算・簡易チェックサム：ビットの奇遇数（パリティ）を調べる際に XOR を使う。
- RAID 5 等のストレージ冗長化：ブロックのパリティ計算に XOR を用いてデータ復元を行う。
- 暗号（ストリーム暗号・ワンタイムパッド）：平文と鍵を XOR して暗号化・復号を行う。完全な一回限りのランダム鍵（one-time pad）の場合は理論上完全な秘匿性を持つが、鍵の再利用や予測可能な鍵では安全ではない。
- 最大XOR部分集合や区間XORクエリ：プレフィックスXORを使った高速な区間XOR取得や、ビットごとの基底を使う最大化問題（XOR basis）など。
ハードウェア実装
XORは論理ゲートとしても基本的で、2入力XORゲートは上の真理値表に従う回路です。論理式では a ⊕ b = (a & ~b) | (~a & b) と表せ、NAND/AND/ORで実装可能です。組み合わせ回路や加算器（桁ごとの加算における和ビットとして）で多用されます。
注意点・落とし穴
- 型と意味の混同：^ を使う際はその言語でビット演算か論理演算かを確認すること。JSでは真偽値に対する ^ は意図しない動作を生む。
- ワード幅の扱い：複数ビットの反転を意味するためには「全ビットが1のマスク」とのXORが必要。固定幅を想定せずにビット反転を行うと符号付表現や無限幅表現（Pythonの ~）で期待と異なる可能性がある。
- 暗号利用時の注意：単純なXOR暗号（繰り返し鍵のXOR）は容易に破られる。暗号学的には安全な鍵管理とランダム性が必須。
まとめ
XORは簡潔ながら強力な演算で、ビット操作、アルゴリズム、ストレージの冗長化、暗号処理など幅広い分野で使われます。可換・結合・自己相殺といった性質や GF(2) としての線形代数の視点を押さえておくと、実装やアルゴリズム設計で役に立ちます。一方で型やビット幅、暗号用途での鍵管理などの注意点も忘れてはいけません。
参考文献
- 排他的論理和（Wikipedia 日本語）
- Exclusive-or (Wikipedia)
- Bitwise operation (Wikipedia)
- One-time pad (Wikipedia)
- Parity bit (Wikipedia)
- RAID（RAID レベルの説明、特に RAID 5 のパリティ） (Wikipedia)
- XOR swap algorithm (Wikipedia)
- Linear algebra over GF(2) (Wikipedia)
投稿者プロフィール
