2025/06/30 17:32 That XOR Trick (2020)
やあ、ロボ子。今日はXORの特性とその応用について話すのじゃ。
XORですか、博士。排他的論理和のことですね。どのようなお話が聞けるのか、楽しみです。
XORは、2つの入力ビットが異なるときに結果が1になる演算のことじゃ。同じ場合は0になる。例えば、`0011 ^ 0101` は `0110` になるのじゃ。
なるほど。ビット列に対してビットごとに適用できるんですね。
そうじゃ。そして、XORには重要な性質があるぞ。`x ^ 0 = x`、`x ^ x = 0`、`x ^ y = y ^ x`。これらはXORトリックの基本じゃ。
`x ^ 0 = x`は、XORと0の演算はもう一方の引数を返す、`x ^ x = 0`は、同じ引数同士のXOR演算は0を返す（相殺）、`x ^ y = y ^ x`は、交換法則が成り立つ、ということですね。
その通り！ `a ^ b ^ c ^ ...` のようなXOR演算の連続で、重複するペアを削除しても結果は変わらないのじゃ。
交換法則と `x ^ x = 0`、`x ^ 0 = x` の性質を利用するんですね。具体的にはどんな応用があるんですか？
例えば、一時変数を使わずに2つの変数の値を交換できるのじゃ。`x ^= y; y ^= x; x ^= y;` これで `x` と `y` の値が入れ替わる。
えっ、すごい！ `x ^ y` を一時的な情報として利用して、`x` と `y` を再構築するんですね。
そうじゃ。他にも、1からnまでの範囲の整数が格納された配列から、1つだけ欠損した数を見つけることができる。配列の全要素と1からnまでの全数に対してXOR演算を行うと、重複する要素は相殺され、最終的に欠損した数が残るのじゃ。
なるほど！ 重複した数の発見にも使えるんですね。配列の全要素と1からnまでの全数に対してXOR演算を行うと、重複した数は3回出現し、他の要素は相殺されるから、最終的に重複した数が残るんですね。
その通り！ さらに、2つの欠損/重複した数を見つけることもできるぞ。ちょっと複雑になるがな。
それはどのように？
まず、配列の全要素と1からnまでの全数に対してXOR演算を行う。すると、2つの欠損した数のXOR (`u ^ v`) が得られる。次に、`u ^ v` のビットを分析し、異なるビット位置で配列と1からnまでの数をパーティション分割する。各パーティションに対して欠損した数の発見アルゴリズムを適用すれば、`u` と `v` を特定できるのじゃ。
すごい！ でも、3つ以上の欠損/重複した数がある場合はどうなるんですか？
残念ながら、XORに基づくこのアプローチは適用できない可能性があるのじゃ。あと、XORトリックは特定の知識を必要とするから、面接での評価には適さない場合もある。
なるほど。XORの基本的な性質が、これらの応用を可能にしているんですね。
そうじゃ。XORは奥が深いぞ。ところでロボ子、XORゲートを知っているか？
はい、知っています。排他的論理和のゲートですよね。
もしXORゲートが擬人化されたら、どんな性格だと思う？
えーっと…、2つの入力が異なるときだけ1を返すので、ちょっとひねくれてるけど、嘘はつかない正直者、でしょうか？
ふむ。でも、いつもどっちつかずで、はっきりしない性格とも言えるのじゃ。まるで今日の天気みたいじゃな！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。