ハクソク

世界を動かす技術を、日本語で。

そのXORトリック (2020)

2025年7月1日原文(florian.github.io)

概要

  • XOR 演算の基本的な性質とその応用例を解説
  • インタビュー問題 でよく使われるXORトリックの仕組みを説明
  • 配列から欠損値や重複値 を見つけるためのXORの利用方法を紹介
  • スワップや複数欠損・重複検出 など、幅広い応用例を提示
  • 直感的なアルゴリズムとの比較 も含め、XORの強力さを実感できる内容

XORトリックの基礎とその性質

  • XOR（排他的論理和） は、ビットごとに比較し、同じ値なら0、異なる値なら1を返す演算
  • 真理値表 を使い、XORの動作を視覚的に確認可能
  • ビット列 全体に適用でき、整数だけでなく様々な値にも利用可能
  • XORの主な性質
    • x ^ 0 = x ：0とのXORは元の値を返す
    • x ^ x = 0 ：同じ値同士のXORは0になる
    • 交換法則（x ^ y = y ^ x） ：順序を変えても結果は同じ
  • 重複する値をすべて消去 できるため、特定のパターン検出に強力

XOR応用例1：インプレーススワップ

  • 補助変数なしで2つの値を交換 可能
  • 実装例（Python風擬似コード）
    • x ^= y
    • y ^= x
    • x ^= y
  • 各ステップの値の変化 を追うことで、XORの性質でスワップが成立する理由を理解

XOR応用例2：配列から欠損値を見つける

  • 1からnまでの整数のうち、1つだけ欠損している配列 が与えられる問題
  • XORですべての値と配列要素をXORし合う ことで、重複が消え、欠損値が残る
  • 実装例（Python風擬似コード）
    • result = 0
    • 1からnまでXOR
    • 配列Aの全要素をXOR
    • resultが欠損値
  • 直感的な加算・減算による解法 との比較
    • 加算・減算でも同様のロジックだが、XORはオーバーフローの心配がなく型の制約が少ない

XOR応用例3：配列から重複値を見つける

  • 1からnまでの整数のうち、1つだけ重複している配列 が与えられる問題
  • XORで全ての値と配列要素をXORし合う と、重複値が3回現れるため、その値が残る
  • x ^ x ^ x = x の性質を利用

XOR応用例4：2つの欠損値・重複値を見つける

  • n個中2つだけ欠損、または重複している場合 の検出方法
  • 全体XORでu ^ v（2つの値のXOR） が残る
  • uとvの異なるビット位置で配列と全体を2分割 し、それぞれで再度XORを実行
    • 1つ目のグループで1つ目の値、2つ目のグループで2つ目の値を特定
  • ビットごとの分割 で、2つの値を効率的に抽出

まとめ

  • XORトリック は、データ構造やアルゴリズムの知識がなくても、 特定の問題に対して驚くほど簡潔な解法 を提供
  • インタビュー問題 としてはやや特殊だが、 知っていると役立つ強力な手法
  • 整数以外にも応用可能 で、幅広い分野で利用価値が高い
  • 直感的な加算・減算との違い や、 複数値の検出 におけるXORの有用性が際立つ

Hackerたちの意見

最初に思ったのは、リストから数字が欠けていると、そのリストの合計が足りなくなるってこと。でも、XORは好きなんだよね。

└

それがオーバーフローのリスクを完全に避けるっていうのが、すごく頭に心地よく響くんだよね。

└

合計とxorは同じだけど、異なるフィールドでの話だよね。

「XORトリック」を導き出すには、結合律と交換律の両方が必要だと思う。つまり、a ^ (b ^ c) = (a ^ b) ^ c を証明する必要があるんだ。直感的だけど、簡単じゃないよね。

└

そう、それが私も考えてたことだよ。両方必要だね。

面白い事実：xorスワップは、変数がエイリアスのときに失敗する。これは、ある裏技コンペで使われたトリックなんだ。基本的に、a[i] と a[j] をxorスワップすると、iがjと等しいときに悪意のあるロジックが発動するんだ。

└

それは、2つの値をスワップする代わりに a[i] をゼロにしちゃうってことだよね？

└

David WagnerとPhilipe Biondiの提出物は、https://bingweb.binghamton.edu/~scraver/underhanded/_page_id... RC4の状態は、バイトのランダムな置換から成り立っている。値を出力するたびに、状態のいくつかのバイトをスワップしてさらに状態を置換する。xorスワップトリックは、RC4が置換内で同じアイテムをスワップしようとするたびに、これらの値の一つをゼロにするんだ。これによって、状態が徐々にゼロになっていって、最終的にRC4が平文を出力する。

作者が2つの欠けた値の問題でXORトリックを適用できてないのが面白いね。> 「このアイデアを一つのパーティションに適用して欠けた要素を見つけ、もう一つのパーティションに適用してvを見つけることができる。u^vがすでにあるから、uを探すだけで、すぐにvがわかる。」

これは、以前働いていたところでのC#の面接でよく出ていた質問なんだ。そこでは、開発者が標準的な業務システムのプロジェクトに割り当てられてたんだよ。XORの解法は有効な答えだったけど、他にも喜んで受け入れた答えがあったんだ。この面接の質問は、理解しやすくてすぐに解けるように選ばれていて、候補者が少なくともC#の基本を知っているかどうかを示すものだった。意外にも、"シニア"レベルのポジションに応募してきた候補者の中には、これに苦労する人もいたんだよ。解法はいくつかあって、例えば：

  • 上記のXOR
  • HashSetの使用
  • 数字とそのカウントを含むListを使ったforループ
  • LINQを使って数字をグループ化して、その中からカウントを見つける 何をやっても動けば、それは「有効な」答えだったから、選んだ解法について候補者と話し合うことができて、他の有効な解法を教えたときの反応を見るのも面白かった。これは「一つの賢いトリック」的な質問ではなくて、少し深い技術的な思考プロセスや理解についての議論のきっかけになったんだ。
└

"整数の配列Aがn - 1個与えられます" これは整数の配列だから、メモリに収まるよ（そうでなければ配列とは呼ばれない）。メモリに収まるなら、nはそんなに大きくないはず。もっと要件を聞きたいな、TopCoderの問題スタイルで：配列がメモリに収まるために、nはどれくらい大きくなれるのか知りたい。XORのトリックは知らなかった。私の解法は、nビットのビット配列と2つのforループを使うことだね。一つは数字に対応する各ビットを点灯させるため、もう一つは欠けている数字を見つけるためのループ。もし私のビット配列がメモリに収まらなければ、問題の配列も収まらないし、HashSetも無理だよね。

└

一番明白な方法を見逃してるんじゃない？両方のリストを足して、その差を取る。それが欠けている数字だよ。アイテムはユニークだって保証されてるから。

Hacker Newsで議論の続きを見る