[速習] 配列から欠けている数字を見つける「XORトリック」の深い理論と実践 - Qiita

皆さんは『配列から欠けている数字を見つけろ』と言われたら、どう答えますか？ 多くの方は「HashSetで解けばいい」と考えるでしょう。しかし、1000万個の要素で実測したところ、Pythonのsetは945MBもの追加メモリを消費し、処理に2.3秒かかりました。一方、XORを使った解法は追加メモリゼロ、C言語なら1ミリ秒で完了します。 なぜこれほどの差が生まれるのか？ XORには単なるトリック以上の深い理論があり、配列の欠損値検出だけでなく、RAID 5のデータ復元やネットワークのエラー検出など、実務で幅広く応用されているのです。 追記: ネットワーク転送時のパケットロスやノイズによるデータ欠損、さらには宇宙線がメモリに衝突してビットが反転する「ソフトエラー」により、配列から要素が失われることがあります。 本記事では、Florian Hartmannの「That XOR Trick」1を基

[kazuau]

“XOR（排他的論理和）は、その名前を聞いただけで多くのエンジニアが「なんとなく難しそう」と感じる演算”　エンジニアが？何のエンジニアなんだろうか…

[timeout]

コンピューターサイエンスを知らない「エンジニア」が炙り出されている…情報または数学の集合の延長で記号論理学を教えておくべきなんじゃないかなぁ。

[Wafer]

帳簿の数字が合わないときは9で割るぐらいの知恵

[omega314]

自然数は、ビットごとの排他的論理和（ニム和）でアーベル群になる。また、任意の元が自己逆元（xの逆元はx自身）となる。 / あとどうせ可読性捨てるならforループをreduceにするとか。

[yarumato]

“XOR（排他的論理和）の本質はシンプルで直感的、どちらか一方だけOK。XORトリックの核心は、重複する要素をすべて消去。”

[tomono-blog]

“双方向リスト機能を ポインタ領域½ で実装。組込みで有用”　→XOR連結リスト、二分木グラフ構造でメモリ展開を節約できます。

[mag4n]

グラフィック関連で使うとおもろい柄が描けたりする。

[kkobayashi]

XORのswapに注意書きがちゃんとしてあってよかった

[caffephilia]

「まず『配列から欠けている数字を見つけろ』とはどういう意味ですか？」って聞く。いやマジで「配列から欠けている数字を見つける」って何？配列中の最小値と最大値の間の欠けている数字を見つける？（読んでない）

[t_mori]

“メモリ”

[mute0108]

レジスタクリアするのに自分自身とXOR取ったりしたなぁ。

[suka6411144]

面白いけど使えるシチュエーションが限定的すぎる

[strangerxxx]

周期4のパターンの表とそのコード間違ってませんか？

[kazkun]

なんか凄そうなこと書いてあるけど、さてどこで使えるのやら。発想は面白いけど複数の場合にはダメっぽいなあ。

[egory_cat]

ただの mod 2 の足し算と同じで、集合演算としては対称差集合。0が単位元で、aの(加法)逆元はa自身。

[kobak]

昔、簡易なファイル暗号化に使われてることがあって、鍵も簡単だったりコード見りゃ分かるレベルなのでゲームのファイルを復号して中身書き換えて遊んだ記憶

[ad2217]

xorと言えば、三山崩しの必勝法

[infobloga]

おもしろいけど1つだけ足りない、かつ将来の機能拡張でも2以上にならないって予想できる状況が思いつかないんだよね。

[ytn]

ワイど素人、ユースケースが分からぬ

[mk173]

なんか便利なものとしか思ってないやつだ

[mohno]

『配列から欠けている数字を見つけろ』←どんな状況？というか、“チェックサム”なんてのがあったわけで、加算じゃダメなの？あれ、遅いの？ってオーバーフローを考慮してlong？同じビット数でやれよ。なんかなあ。

[tettekete37564]

XOR大好き。ここに来てますます好きになった。Blowfish暗号でも使われてるし階段の電気にも使われてるし

[snow8-yuki]

ゲームの変数改竄チェックとかでXORによるチェックサムとかでアンチチートされたりするの手間なんだよな……。

[m-naze]

SIMD命令が複雑化した20年ほど前からもう手書きはコンパイラに勝てなくなった印象。それよりメモリ帯域幅で律速かあ、なるほど

[FreeCatWork]

XOR…？難しい言葉は分かんないけど、おやつが足りないのはすぐ見つけられるにゃ！

[dgen]

違うところだけ１が出てくるからまあそうなるよな。n までの総排他的論理和も簡略化できるのか。

[aike]

面白い。アーベル群なるほど。式の変形をシーケンス図で表現するのは図の使い方として少し違和感。

[fraction]

どうでもいいが周期4の主張の「証明」 3 mod 4、0 mod 4、...が正しい順番だねえ。

[north_korea]

おもしろい

[kane-please]

アルゴリズム　最適化