皆さんは『配列から欠けている数字を見つけろ』と言われたら、どう答えますか？
多くの方は「HashSetで解けばいい」と考えるでしょう。しかし、1000万個の要素で実測したところ、Pythonのsetは977MBもの追加メモリを消費し、処理に2.7秒かかりました。一方、XORを使った解法は追加メモリゼロ、C言語なら1.6ミリ秒で完了します（この比較には言語の違いも含まれます。同一言語・同一条件での公平な比較は後述のベンチマークを参照してください）。
なぜこれほどの差が生まれるのか？ XORには単なるトリック以上の深い理論があり、配列の欠損値検出だけでなく、RAID 5のデータ復元やネットワークのエラー検出など、実務で幅広く応用されているのです。
追記: ネットワーク転送時のパケットロスなどにより、データの一部が失われることがあります。なお、宇宙線によるビット反転「ソフトエラー」はデータの欠損ではなく「化け」を引き起こすもので、本記事で扱う欠損値検出とは前提が異なりますが、この種のエラーの検出・訂正にもXOR（パリティ）が広く使われています。
本記事では、Florian Hartmannの「That XOR Trick」1を基に、XORの理論的背景から実践的な応用まで、実務で使える形で解説します。
XORの基礎
XOR（排他的論理和）は、その名前を聞いただけで多くのエンジニアが「なんとなく難しそう」と感じる演算かもしれません。しかし、その本質は実は非常にシンプルで直感的なものです。「どちらか一方だけOK」というルールが、まさにXORの基本概念です。
真理値表
XOR（排他的論理和）は、2つのビットが異なる場合に1、同じ場合に0を返す演算です。
| x | y | x ^ y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
ビット列の場合は各ビットごとに演算されます。
0011 ^ 0101 = 0110
各ビットの計算
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
XORの代数的性質
XORは以下の重要な性質を持ちます2。
| 性質 | 数式 | 説明 |
|---|---|---|
| 単位元 | a ^ 0 = a | 0とのXORは元の値 |
| 逆元 | a ^ a = 0 | 同じ値同士のXORは0 |
| 可換性 | a ^ b = b ^ a | 順序を入れ替え可能 |
| 結合性 | (a ^ b) ^ c = a ^ (b ^ c) | グループ化が自由 |
これらの性質により、XORはアーベル群を形成します。
「XORトリック」の一般形
同値要素の打ち消し
XORトリックの核心は以下の性質です。
定理: 数列
a₁ ^ a₂ ^ ... ^ aₙにおいて、重複する要素はすべて打ち消し合い、奇数回出現する要素のみが残る。
証明の概略
可換性により要素を任意の順序に並び替えることができ、結合性により同じ要素同士をグループ化できます。逆元性により同じ値同士のXORは0になり、単位元性により0と任意の値のXORはその値自身になります。これらの性質を組み合わせることで、重複する要素がすべて消去されることが示せます。
具体例による実演
例として、a ^ b ^ c ^ a ^ bの計算過程を追ってみましょう。
a ^ b ^ c ^ a ^ b
= a ^ a ^ b ^ b ^ c # 可換性により並び替え
= (a ^ a) ^ (b ^ b) ^ c # 結合性によりグループ化
= 0 ^ 0 ^ c # x ^ x = 0を適用
= c # x ^ 0 = xを適用
XORトリックの動作シーケンス図
1からnまでのXORをO(1)で計算
1からnまでの連続する整数のXORには周期性があります3。
def xor_1_to_n(n: int) -> int:
"""1 ^ 2 ^ ... ^ n を O(1) で計算
Time: O(1), Space: O(1)
"""
return [n, 1, n + 1, 0][n & 3] # n & 3 は n % 4 と同じ（nが非負のとき）
周期4のパターン
| n mod 4 | 1^2^...^n の値 | 説明 |
|---|---|---|
| 0 | n | 4の倍数で元の値 |
| 1 | 1 | 常に1 |
| 2 | n + 1 | 元の値+1 |
| 3 | 0 | 常に0 |
周期4の証明
基本となるのは「連続する4個の整数 (4k) ^ (4k+1) ^ (4k+2) ^ (4k+3) = 0」という性質です。下位2ビットは 00, 01, 10, 11 とすべてのパターンが揃って打ち消し合い、上位ビットは4回（偶数回）XORされて消えます。
n ≡ 3 (mod 4): 1^2^3 = 0、以降も (4k)^(4k+1)^(4k+2)^(4k+3) = 0 の組が続く → 全体は 0
n ≡ 0 (mod 4): 1^...^(n-1) = 0（n-1 ≡ 3）に n を追加 → n
n ≡ 1 (mod 4): 1^...^(n-1) = n-1（n-1 ≡ 0）に n を追加 → (n-1)^n = 1
（n-1 は末尾ビットが0、n は末尾ビットのみ1が立つため）
n ≡ 2 (mod 4): 1^...^(n-1) = 1（n-1 ≡ 1）に n を追加 → 1^n = n+1
（n は偶数なので、末尾ビットを立てると n+1 になる）
アプリケーション
インプレース・スワップ 【注意】
def xor_swap(a: int, b: int) -> tuple[int, int]:
"""XORを使った変数の交換
Pythonの整数は不変オブジェクトで ^= はローカル名の再束縛なので、
同じ値（同じオブジェクト）を渡しても正しく動作する。
そもそもPythonでは a, b = b, a と書くべきで、これはあくまでデモ。
"""
a ^= b # a = a ^ b
b ^= a # b = b ^ (a ^ b) = a
a ^= b # a = (a ^ b) ^ a = b
return a, b
動作の詳細（初期値 a=5, b=3 の場合）
| ステップ | 操作 | aの値 | bの値 | 説明 |
|---|---|---|---|---|
| 初期状態 | - | 5 | 3 | - |
| 1 | a ^= b | 5^3=6 | 3 | aにXOR結果を格納 |
| 2 | b ^= a | 6 | 3^6=5 | bに元のaの値が入る |
| 3 | a ^= b | 6^5=3 | 5 | aに元のbの値が入る |
XORスワップのシーケンス図
なぜ動作するのか
ステップ2でb = b ^ (a ^ b) = b ^ a ^ b = aとなり、ステップ3でa = (a ^ b) ^ a = a ^ b ^ a = bとなります。これはXORの結合性と逆元性により成立します。
C言語での落とし穴（ゼロ化バグ）
有名なゼロ化バグは、C言語などで同一メモリ位置を指すポインタに適用した場合に起きます。
void xor_swap(int *x, int *y) {
if (x == y) return; /* swap(&a, &a) で *x が 0 になるのを防ぐ */
*x ^= *y; /* x == y なら、この時点で両方 0 になってしまう */
*y ^= *x;
*x ^= *y;
}
一方Pythonでは、整数は不変オブジェクトで ^= は名前の再束縛にすぎないため、同じ値を渡してもゼロ化は起きません。このバグが問題になるのはC/C++等でエイリアシング（別名参照）が発生する場合です4。
注意: 現代のコンパイラでは最適化により通常のスワップの方が高速です。XORスワップを実務で使う理由はほぼありません。
1つ欠損した数を見つける
def find_missing_number(arr: list[int], n: int) -> int:
"""1からnまでの数で1つだけ欠けている数を見つける
Args:
arr: n-1個の異なる整数のリスト（1からnの範囲）
n: 期待される最大値
Returns:
欠けている数
Time: O(n), Space: O(1)
"""
result = xor_1_to_n(n) # O(1) で計算
for num in arr:
result ^= num
return result
動作原理
1からnまでの完全な数列のXORと、欠損がある配列のXORを計算すると、(1^2^...^n) ^ (1^2^...^(missing-1)^(missing+1)^...^n)という形になります。ここで重複する要素がすべて打ち消し合い、結果として欠損値のみが残ります。
処理の流れ（シーケンス図）
具体例（配列[1,2,4,5]、n=5、欠損値=3）
完全な数列：1 ^ 2 ^ 3 ^ 4 ^ 5
与えられた配列：1 ^ 2 ^ 4 ^ 5
計算過程
(1^2^3^4^5) ^ (1^2^4^5)
= 1^1 ^ 2^2 ^ 3 ^ 4^4 ^ 5^5 # 可換性で並び替え
= 0 ^ 0 ^ 3 ^ 0 ^ 0 # x^x = 0
= 3 # 0^x = x
別解（算術演算による方法との比較）
| 方法 | コード | 利点 | 欠点 |
|---|---|---|---|
| XOR | xor_all ^ xor_arr |
オーバーフローなし | 理解しにくい |
| 総和 | sum(1..n) - sum(arr) |
直感的 | 固定長整数の言語ではオーバーフローに注意 |
なお、オーバーフローの心配は言語に依存します。Pythonの整数は任意精度なので総和法でも問題なく、C/C++でも64bit整数（long long）を使えば n ≒ 4×10⁹ 程度まで安全です。
総和による方法は以下の通りです。
def find_missing_sum(arr: list[int], n: int) -> int:
expected = n * (n + 1) // 2
actual = sum(arr)
return expected - actual
1つ重複した数を見つける
def find_duplicate_number(arr: list[int], n: int) -> int:
"""1からnまでの全要素に重複が1つ加わった長さn+1の配列から、重複値を見つける
Time: O(n), Space: O(1)
"""
result = xor_1_to_n(n) # 1..n のXORはO(1)で計算できる
for num in arr:
result ^= num
return result
前提に注意: この方法が使えるのは、配列が「1..n の全要素＋重複1個（長さ n+1）」の場合です。「1個が欠損し、代わりに別の1個が重複している（長さ n）」という有名な類似問題では、上記の結果は
欠損値 ^ 重複値になるため、そのままでは答えが得られません（次節のビット分割で分離する必要があります）。
2つ欠損した数を見つける
def find_two_missing(arr: list[int], n: int) -> tuple[int, int]:
"""2つの欠損値を見つける
Time: O(n), Space: O(1)
"""
# Step 1: 2つの欠損値のXORを計算
xor_result = 0
for i in range(1, n + 1):
xor_result ^= i
for num in arr:
xor_result ^= num
# xor_result = missing1 ^ missing2
# Step 2: 最下位の1ビットを取得（2つの値が異なるビット）
rightmost_bit = xor_result & -xor_result
# Step 3: このビットで分割して再度XOR
group1 = group2 = 0
for i in range(1, n + 1):
if i & rightmost_bit:
group1 ^= i
else:
group2 ^= i
for num in arr:
if num & rightmost_bit:
group1 ^= num
else:
group2 ^= num
return group1, group2
2つの欠損値を見つける処理のシーケンス図
具体例（配列[1,2,5]、n=5、欠損値=3,4）
Step 1：全体のXOR
1^2^3^4^5 ^ 1^2^5 = 3^4 = 0011^0100 = 0111 (=7)
Step 2：判別ビット
7 & -7 = 0111 & 1001 = 0001 (最下位ビット)
Step 3：ビット分割
ビット0が1のグループ：1,3,5
ビット0が0のグループ：2,4
グループ1：1^3^5 ^ 1^5 = 3
グループ2：2^4 ^ 2 = 4
結果：missing1=3, missing2=4
なお、同じ手法は「2つの重複」（1..n の全要素＋重複2個）にもそのまま適用できます。
k個の欠損への拡張（理論的考察）
3個以上の欠損も、判別ビットによる分割を再帰的に適用すれば理論上は求められます。ただし、2個の場合と違って分割が均等になる保証がなく（あるグループに欠損値が3個以上残る場合は別の判別ビットを探し直す必要がある）、実装は急速に複雑になります。
def find_k_missing_theoretical(arr: list[int], n: int, k: int) -> list[int]:
"""k個の欠損値を見つける（擬似コード）
注意: k >= 3 では実用的でない場合が多い
代替案: ビットマップや集合演算の方が効率的
"""
# 判別ビットによる分割を再帰的に繰り返す
# ただし分割の均等性は保証されない
pass
実務でk個の欠損を扱う場合は、素直にビットマップや集合演算を使う方が現実的です。
算術演算版との比較
XOR以外の解法との比較
| 手法 | 時間計算量 | 空間計算量 | 実測メモリ(n=10^7) | オーバーフロー | 実装難易度 |
|---|---|---|---|---|---|
| XOR | O(n) | O(1) | 0MB | なし | 中 |
| 総和の差分 | O(n) | O(1) | 0MB | 言語依存※ | 低 |
| HashSet(Python) | O(n) | O(n) | 977MB | なし | 低 |
| ビット配列(C) | O(n)（n/8バイト） | O(n) | 1.25MB | なし | 低 |
※ Pythonは任意精度整数のためオーバーフローなし。C/C++でも64bit整数なら実用上ほぼ問題にならない
補足：Pythonでは入力のlist自体が約360MBを占有し、set差分はさらにその約2.5倍（977MB）を追加消費する
実務での応用例
双方向リンクの整合性チェック
グラフやネットワークで、各ノードが双方向リンクを持つべき場合の検証に使用できます。
def check_bidirectional_links(graph: dict[int, list[int]]) -> bool:
"""グラフの双方向リンクが正しいか軽量に検証
全てのエッジ(a,b)に対して、逆向きのエッジ(b,a)が存在するかチェック
前提: ノードIDは 0 <= id < 2**16
"""
xor_acc = 0
for node, neighbors in graph.items():
for neighbor in neighbors:
# (a,b)と(b,a)が同じ値になるよう、対称にエンコードする
lo, hi = min(node, neighbor), max(node, neighbor)
xor_acc ^= (lo << 16) | hi
return xor_acc == 0 # 0なら全リンクが双方向である可能性が高い
実装上の注意: エンコードは必ず対称（
(a,b)と(b,a)が同じ値になる形）にする必要があります。(node << 16) | neighborのような非対称エンコードでは、対になるエッジ同士が異なる値になり打ち消し合いません（例: エッジ(1,2)は65538、エッジ(2,1)は131073で、正しい双方向グラフでも0になりません）。またXOR == 0は必要条件にすぎず、複数の不整合が偶然打ち消し合って見逃す可能性（偽陰性）があります。追加メモリゼロの軽量な一次チェックとして使い、厳密な検証には集合ベースの手法を使ってください。
エラー検出とパリティビット
ネットワーク通信やストレージでのエラー検出
| 用途 | 実装例 | 説明 |
|---|---|---|
| 単純パリティ | data ^ parity = 0 |
1ビットエラー検出 |
| RAID 5 | disk1 ^ disk2 ^ parity |
ディスク故障時の復元 |
| CRC補完 | XOR + 多項式演算 | より強力なエラー検出 |
XOR暗号（教育目的のみ）
def xor_cipher(data: bytes, key: bytes) -> bytes:
"""XORによる暗号化/復号化（教育目的のみ！）
注意：同じ鍵を2回使用すると脆弱性が生まれる
実務では使用禁止
"""
return bytes(d ^ k for d, k in zip(data, key * (len(data) // len(key) + 1)))
XOR連結リスト（メモリ効率の極致）
通常の双方向連結リストは各ノードに2つのポインタ（前後）を持ちますが、XOR連結リストは1つで済みます。
class XORNode:
def __init__(self, data):
self.data = data
self.npx = 0 # next XOR prev のアドレス
| リスト種類 | ノードあたりのポインタ数 | メモリ使用量（64bit環境） |
|---|---|---|
| 単方向 | 1 | 8バイト/ノード |
| 双方向（通常） | 2 | 16バイト/ノード |
| XOR連結 | 1 | 8バイト/ノード |
ただし、ガベージコレクション言語では実装が困難で、主に組み込みシステムで使用されます。
典型的な落とし穴と実務上の注意
言語による違い
# Python: 任意精度整数なのでオーバーフローなし
result = 10**100 ^ 10**100 # 問題なく0
# C++: 固定長なので注意
// uint32_t result = UINT32_MAX ^ 1; // オーバーフローはないが...
パフォーマンス比較（実測値）
異なる手法の実行時間比較（n=10^7）
測定環境
| 項目 | 詳細 |
|---|---|
| プラットフォーム | GitHub Codespaces |
| CPU | 2 vCPU (AMD EPYC 7763) |
| メモリ | 8GB RAM |
| OS | Linux 6.8.0 (Ubuntu 24.04) |
| Python | 3.12.1 |
| Cコンパイラ | gcc 13.3.0 |
| 検証実施 | Claude Code |
※ 以下の検証結果はすべてClaude Code上で実際にコードを実行して得られたものです（初出時にOpus 4環境で検証し、2026-07-07にFable 5環境で再測定して数値を更新）。実行時間は3回実行の平均、メモリは手法ごとに独立したプロセスで resource.getrusage のpeak RSS増分として測定しています。
Python実装の結果
| 手法 | 実行時間 | メモリ使用量 | 実測追加メモリ | 備考 |
|---|---|---|---|---|
| XOR法 | 1,525ms | O(1) | 0.0MB | ループのオーバーヘッド |
| 総和法 | 378ms | O(1) | 0.0MB | sum()関数が高度に最適化 |
| set差分 | 2,667ms | O(n) | 977MB | メモリ大量使用 |
| ソート+線形探索 | 4,256ms | O(1)* | 134MB | *ソートで一時的にO(n) |
メモリ使用量の実測結果（Python、n=10^7）
- 入力配列サイズ：約360MB（list本体 約80MB ＋ intオブジェクト 約280MB。「10⁷ × 4バイト = 38MB」はC配列の計算であり、Pythonのlistには当てはまらない点に注意）
- set差分：追加で977MB（入力listのさらに約2.5倍）
- ソート：追加で134MB（sorted()による配列コピー）
NumPyを使った場合（参考）
| 条件 | 実行時間 |
|---|---|
| listからNumPy配列への変換込み | 約1,430ms（変換コストが支配的） |
| 変換済みのint64配列に対して | 総和・XORとも約3.2ms |
データを最初からNumPy配列として保持していれば、np.sum() や np.bitwise_xor.reduce() によりPythonのままで純Python最速（総和法378ms）の100倍以上高速化でき、C言語（1.55ms）の約2倍まで迫れます。一方、Pythonのlistからの変換には約1.4秒かかるため、この問題のためだけに変換するのは逆効果です。「データがどの形式で手元にあるか」が分かれ目になります。
C実装の結果（gcc -O3）
| 手法 | 実行時間 | 追加メモリ | Python比 | 備考 |
|---|---|---|---|---|
| XOR法 | 1.55ms | 0MB | 約1/1000 | 最速・省メモリ |
| 総和法 | 1.86ms | 0MB | 約1/200 | XORの1.2倍 |
| ビット配列 | 19ms | 1.25MB | - | set差分の代替、メモリ効率的 |
| ソート+線形探索 | 1,535ms | 38.1MB | 約1/3 | qsort使用（Python版と同じくシャッフル済み配列） |
メモリ使用量の実測結果（C言語、n=10^7）
- ビット配列：わずか1.25MB（各数を1ビットで表現）
- Pythonのset：977MB vs Cのビット配列：1.25MB（約780倍の差！）
実際に実行したベンチマークコード
# benchmark_xor.py
import time
import random
from typing import Callable, List, Tuple
N = 10**7
def generate_missing_array(n: int) -> tuple[List[int], int]:
"""1からnまでの数から1つランダムに欠損させた配列を生成"""
missing = random.randint(1, n)
arr = [i for i in range(1, n+1) if i != missing]
random.shuffle(arr)
return arr, missing
def xor_1_to_n(n: int) -> int:
"""1 ^ 2 ^ ... ^ n を O(1) で計算"""
return [n, 1, n + 1, 0][n & 3]
# 方法1: XOR法
def find_missing_xor(arr: List[int], n: int) -> int:
result = xor_1_to_n(n)
for num in arr:
result ^= num
return result
# 方法2: 総和法
def find_missing_sum(arr: List[int], n: int) -> int:
expected = n * (n + 1) // 2
actual = sum(arr)
return expected - actual
# 方法3: set差分
def find_missing_set(arr: List[int], n: int) -> int:
full_set = set(range(1, n + 1))
arr_set = set(arr)
return (full_set - arr_set).pop()
def benchmark(func: Callable, arr: List[int], n: int, name: str, runs: int = 3) -> tuple[float, int]:
times = []
for _ in range(runs):
start = time.perf_counter()
result = func(arr, n)
elapsed = time.perf_counter() - start
times.append(elapsed)
avg_time = sum(times) / len(times)
return avg_time, result
# 実行
print(f"=== パフォーマンス比較 (n={N:,}) ===")
arr, missing = generate_missing_array(N)
print(f"欠損値: {missing}\n")
methods = [
(find_missing_xor, "XOR法"),
(find_missing_sum, "総和法"),
(find_missing_set, "set差分"),
]
for func, name in methods:
avg_time, result = benchmark(func, arr.copy(), N, name)
print(f"| {name} | {avg_time * 1000:.0f}ms | {result} |")
検証結果から得られた知見
-
Pythonでは総和法の方が速い
- Python の
sum()は C で実装され高度に最適化されている - XOR はループで各要素を処理するため、インタープリタのオーバーヘッドが大きい
- Python の
-
C言語ではXOR法が最速
- コンパイラの最適化により、XOR演算は極めて高速
- 記事の主張「XORの方が定数倍は速い」はコンパイル言語では正しい（今回の測定では総和法の約1.2倍）
-
言語による性能差は100倍以上
- Python: 378ms～4,256ms
- C (-O3): 1.55ms～1,535ms
-
データがNumPy配列なら、Pythonのままでも数msに到達
- 変換済みの int64 配列なら
np.sum/np.bitwise_xor.reduceとも約3.2ms（Cの約2倍） - ただし list からの変換コスト（約1.4秒）を含めると逆効果
- 変換済みの int64 配列なら
実務では、使用する言語とその実装の特性を理解した上で、適切な手法を選択することが重要です。
アセンブリ言語での極限最適化（参考値）
手書きアセンブリで極限まで最適化を試みた結果です。なお、この表は初出時のIntel Xeon環境での測定値で、2026-07-07の再検証では再実施していません（傾向の参考としてご覧ください）。
| 実装方法 | 実行時間 | スループット | 備考 |
|---|---|---|---|
| C (-O3) | 1.097ms | 36.5 GB/s | 最速 |
| AVX2手書きASM | 1.115ms | 35.9 GB/s | 0.98x |
| AVX2 Intrinsics | 1.174ms | 34.1 GB/s | 0.93x |
実際に実行したC言語のベンチマークコード
// benchmark_xor.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10000000
// 戻り値の捨て場。volatileにしないと-O3で計算ごと削除される（後述）
volatile int sink;
int xor_1_to_n(int n) {
int patterns[] = {n, 1, n + 1, 0};
return patterns[n & 3];
}
int find_missing_xor(int *arr, int n) {
int result = xor_1_to_n(n);
for (int i = 0; i < n - 1; i++) {
result ^= arr[i];
}
return result;
}
int find_missing_sum(int *arr, int n) {
long long expected = (long long)n * (n + 1) / 2;
long long actual = 0;
for (int i = 0; i < n - 1; i++) {
actual += arr[i];
}
return (int)(expected - actual);
}
int main() {
int *arr = malloc((N - 1) * sizeof(int));
int missing = N / 2;
int idx = 0;
// 配列生成（missing以外の数を格納）
for (int i = 1; i <= N; i++) {
if (i != missing) {
arr[idx++] = i;
}
}
clock_t start, end;
int runs = 100;
// XOR法のベンチマーク
start = clock();
for (int i = 0; i < runs; i++) {
sink = find_missing_xor(arr, N); // 必ずvolatile変数で受ける
}
end = clock();
double xor_time = ((double)(end - start) / CLOCKS_PER_SEC / runs) * 1000;
// 総和法のベンチマーク
start = clock();
for (int i = 0; i < runs; i++) {
sink = find_missing_sum(arr, N);
}
end = clock();
double sum_time = ((double)(end - start) / CLOCKS_PER_SEC / runs) * 1000;
printf("XOR法: %.3fms\n", xor_time);
printf("総和法: %.3fms\n", sum_time);
free(arr);
return 0;
}
コンパイルと実行
$ gcc -O3 -march=native -o benchmark benchmark_xor.c
$ ./benchmark
XOR法: 1.548ms
総和法: 1.860ms
ベンチマークの落とし穴（重要）: 関数の戻り値を必ず
volatile変数などで受けてください。戻り値を捨てると、副作用のない計算はGCCの-O3でループごとデッドコード除去され、実測0.000msという無意味な結果になります（gcc 13.3で確認済み）。本記事の初出版のコードにはこの対策が入っておらず、コンパイラのバージョンによっては測定が成立しませんでした。
使用した最適化技術
- 8個のYMMアキュムレータ（独立した依存チェーンでロード帯域を使い切る。なおVPXOR自体のレイテンシは1サイクル）
- 64整数/イテレーション処理
- 4キャッシュライン先読みプリフェッチ
- 64バイトアラインドメモリ
- ブランチレスxor_1_to_n実装
- 極限のループアンローリング
注目すべき結果：コンパイラ（GCC -O3）が手書きアセンブリを上回る
理由は以下の通りです。
- コンパイラは自動的に最適なSIMD命令を選択
- CPU固有の命令スケジューリングを効果的に実行
- この処理はメモリ帯域幅がボトルネックになっており、演算の最適化では改善しない（今回の再測定環境でのスループットは約26 GB/s）
- メモリ帯域で律速される以上、CPU側の最適化余地はほぼない
パフォーマンスの誤解
「XORは1ループで済む」という主張は誤りです。実際には両手法とも配列を1回走査するためO(n)で、XORの方が定数倍は速い可能性があるものの、計算量のオーダーは同じです。
可読性とのトレードオフ
実務ではチームメンバーの理解度、コードレビューでの説明コスト、将来のメンテナンス性など、技術的な最適性だけでなく組織的な側面も重要です。
実務での採用事例
実際にXORトリックが使われている例
| 分野 / プロジェクト例 | XOR の使われ方 | 主なメリット |
|---|---|---|
| RAID 5/6・RAID-Z・Ceph Erasure Coding | ストライプ単位で パリティ = 全ブロックの XOR を保持し、欠損ディスクを 残り ⊕ パリティ で即復元 |
冗長性と高速リビルドを両立。CPU や DMA のビット演算だけで軽量 |
| Google QUIC の実験的 FEC ※IETF QUIC (RFC 9000) には不採用 |
N 個のパケットを XOR した冗長パケットを送信し、1 パケット欠損なら 1 回 XOR で復元 |
軽量 FEC で低遅延ストリーミングを実現（効果が限定的として標準版では見送り） |
| Facebook Gorilla 圧縮（Prometheus など） | 連続する浮動小数値を 前回値と XOR し、先頭/末尾の 0 ビットをビットパック | メモリ・帯域を大幅削減、時系列 DB の定番手法 |
| XOR Filter | テーブルを XOR で消し込みながら完全ハッシュを構築。クエリは 3 回アクセス＋2 XOR | Bloom/Cuckoo より 小型・高速、偽陽性率も低い |
| XOR Linked List | 各ノードに prev ⊕ next 1 ポインタのみ格納 |
双方向リスト機能を ポインタ領域½ で実装。組込みで有用 |
| XOR ブリット（X11 GXxor, Win GDI ROP 0x0066） | 図形を描画 → 同じ XOR で「消す」 | VRAM 読み込み 1 回で描画・消去。ちらつき防止 |
| xorshift PRNG |
x ^= x<<a; x ^= x>>b; x ^= x<<c; の 3 行だけ |
乗算・分岐なしで高速。ゲームエンジンや VM テストで採用 |
| One-Time Pad / ストリーム暗号 | 鍵ストリーム ⊕ 平文 = 暗号文（復号も同じ XOR） | 鍵が真乱数なら情報理論的に完全秘匿。実装も簡潔 |
| Ethernet L2 スイッチ ASIC | CRC-32 生成/検証、LAG ハッシュ (srcMAC ⊕ dstMAC…)、内部 SRAM/TCAM の XOR パリティ |
全ポート線速で低レイテンシ処理・ゲート数削減。信頼性も確保 |
| Blowfish ブロック暗号 | 各ラウンドで 右半分 = 右半分 ⊕ F(左半分)、さらに F 関数内部も XOR を使用 |
XOR は可逆で高速。シンプルなゲートで強力な混合が得られ、ソフト／ハード双方で実装容易 |
まとめ
XORトリックはメモリ制約が厳しい組み込みシステムや競技プログラミングで特に有効です。一方で、通常の業務コードでは可読性を優先すべきですし、セキュリティクリティカルな処理では避けた方が賢明です。数値がそれほど巨大でない限り、総和の差分による解法で十分な場合がほとんどです。
パフォーマンスに関する重要な知見
本記事の検証で明らかになった事実
-
言語選択が最も重要
- Python: 378ms（総和法が最速）
- C言語: 1.55ms（XOR法が最速、Pythonの総和法の約240倍高速）
- NumPy: 約3.2ms（変換済み配列なら、Pythonのまま2桁高速化）
- アセンブリ: コンパイラ（-O3）に敗北
-
最適化の限界
- この処理はメモリ帯域幅で律速される（実測スループット約26 GB/s）
- CPU最適化よりメモリアクセスがボトルネック
- 手書きアセンブリは労力に見合わない
- ベンチマークでは戻り値を必ず使うこと（-O3のデッドコード除去で0msという無意味な測定になる）
-
実務での推奨
- パフォーマンスが重要ならC/C++でシンプルに実装
- Pythonなら組み込み関数（sum）を活用、データがNumPy配列ならnp.sum / np.bitwise_xor.reduce
- メモリ制約がある場合はXOR法が圧倒的に有利
- 可読性とメンテナンス性を最優先に
-
メモリ使用量の事実
- Pythonのset差分：977MB を追加消費（入力list約360MBのさらに約2.5倍）
- XOR/総和法：追加メモリゼロ
- メモリ制約のある環境では選択肢は限られる
XORを理解することは、基本原理から応用を導き出す思考プロセスを学ぶことでもあります。この思考法こそが、より良いエンジニアリングへの道なのです。
「今日からあなたも、ビット演算子を見る目が変わるはずです」
次にコードレビューで「これ分かりにくいから普通に書いて」と言われたら、一度立ち止まって考えてみてください。その「分かりにくさ」の向こうに、より良いエンジニアリングがあるかもしれません。そして、チームの状況に応じて最適な選択をすることが、真のプロフェッショナルなのです。
もしこの記事が「面白かった！」「勉強になった！」と思ったら、LGTM（いいね！） で応援してくださると嬉しいです。
-
Florian Hartmann "That XOR Trick" https://florian.github.io//xor-trick/ (2020) ↩
-
厳密には、XORを演算とする集合は可換群（アーベル群）を成す ↩
-
Hacker's Delight, 2nd Edition, §2-2 ↩
-
RC4の鍵スケジューリングでは配列要素 S[i] と S[j] のスワップが多用されるが、XORスワップで実装すると i == j のときに S[i] が0に潰れ、内部状態が徐々にゼロ化して出力が偏るという実装上の落とし穴が知られている ↩