ハクソク

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

そのXORトリック (2020)

329日前原文(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も無理だよね。

└

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

1からnまでのXORを計算するには、閉じた形の解法があるから、ループでXORする必要はないよ。 (n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1) もっと読みやすいバージョンは、[ n, 1, n + 1, 0 ][n % 4] で、これでこの関数が4の長さのパターンを繰り返すことがわかる。これがなぜ機能するかは、4で割り切れるnから始めて、次の数とXORしていくとわかる。最初はxxxxxx00がnだね。次にn + 1（xxxxxx01）とXORすると、すべてのxが消えて00000001になる。次にn + 2（xxxxxx10）とXORすると、xxxxxx11になってn + 3になる。サイクルはn + 3とXORすると00000000になって終わる。だから、n, 1, n + 3, 0が得られて、サイクルが再び始まるんだ。

└

あなたの配列ベースの方程式ではn+1と言ってるけど、説明ではn+3と言ってるよね。それは間違い？

└

面白いね。動いてるのは見えるけど、魔法のサイクル長さが4になる理由がまだよくわからない。

こういうビットレベルのトリックに興味がある人は、Hacker's Delightを本棚に置いておくべきだね。

約1ヶ月前、RedisのVector Sets実装に似た方法（でもちょっと複雑）でXORを使ったんだ。RDBファイルからvsetの値を読み込む際のサニティチェックの文脈でね。これがどう機能するかはかなり面白くて、投稿のトリックの適用範囲を広げるものだと思う。問題は、ベクトルセットではHNSWグラフが各ノードにN個のノードへの双方向リンクを持つという不変条件があること。AがBにリンクしているなら、BもAにリンクしている。これは他のHNSW実装とは違うんだ。私の実装では、リンクが相互である必要があって、そうでないとクラッシュしちゃう。これを考慮しつつ、速度の観点からRedisのベクトルセットは要素→ベクトルとしてシリアライズされず、再読み込みしてHNSWに追加されることはない。これだと遅くなるからね。代わりに、私はグラフ自体をシリアライズするんだ。各ノードにはユニークIDとすべてのリンクが含まれている。でも、グラフを読み込むときには、「正常」でクラッシュしないことを確認しなきゃいけない。相互リンクはそのチェックの一つなんだ。すべてのリンクが相互であることを確認するのはハッシュテーブルでもできるけど（投稿の問題のように）、それだと遅くてメモリを消費しちゃう。じゃあ、どうやってXORを使うかというと、A→Bのリンクを見たときに、AとBを入れ替えて正規化するんだ。相互リンクなら、A→Bが2回見えるから、2つのIDを蓄積するレジスタを使ってXORすると、最後にレジスタがnullでなければ問題があるってことになる。相互リンクがないかもしれないからね。ただ、この特定のケースでは、衝突の問題がある。レジスタが0でも、相互リンクがない場合があるんだ。だから、この部分を修正するために、衝突が極めて起こりにくい強力（かつ大きな）ハッシュ関数を使うんだ。数週間前にこれを使ったときにこのアルゴリズムを知らなかったから、今この投稿を見るのは嬉しいよ。確かに、今の私は自分が何かを発明したとは思ってないから、過去に使われていたことは確信しているけど、もし相互リンクのテストに使われていなかったら、これは上級候補者向けの新しい面接質問になるかもしれないね。

└

アキュムレーターを衝突耐性があり、自己診断できるようにするための面白いトリックだね。すべての正規化されたリンクID x に対して：y = (x もしaccがゼロなら、すべてのリンクは相互的（前と同じ保証）。もしaccがゼロでないなら、(x', h')に戻して分割する：* h(x')を再計算する。* それがh'と等しければ、ちょうど1つのリンクがペアになってなくて、x'がどれかを教えてくれる（または天文学的にありえない衝突）。そうでなければ、問題が2つ以上あるってことだね。これは親コメントのように衝突耐性があって、2回目のパスやハッシュテーブルなしで、単一の問題のあるリンクを特定できる能力も追加してるんだ。

グレイコードはそれにちょっと関係してるね。位置のハードウェアエンコーダーでは、状態間での遷移が1回だけになるようにしたいんだ。つまり、2つの状態のXORでビットが1つだけ立つようにするってこと。普通の2進数だと、例えば011と100の間で3回もビットが変わったりするからね。グレイコードはこうなる：000, 001, 011, 010, 110, 111, 101, 100。

これをk個の欠損数に一般化できるよ。通常の加算の場合と同じように有限体を使ってね。XORは有限体F_2^m上の加算に相当するから、ここでは合計を計算してるんだ。もし2つの数が欠けてたら、合計と平方和を計算して、こうなる：x + y, x^2 + y^2。これからxとyを解けるんだ。（注意、すべての掛け算はガロア体の掛け算で、整数じゃないよ！）同様にk個の数については、高次の和を計算して、高次の多項式方程式を得て答えが出るよ。もちろん、同じ解法は整数でも使えるし、モジュラー算術でも使えると思うけど（まだ確認してないけど）。