テクノロジー

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

1: kenzy_n 2025/07/06 20:20

モンティホールよりも面白い。

2: Windymelt 2025/07/06 21:08

へえ

3: tomoP 2025/07/06 21:35

それ逆元っていうの。。?

4: dorapon2000 2025/07/06 22:39

“パフォーマンスが重要ならC/C++でシンプルに実装 Pythonなら組み込み関数(sum)を活用 メモリ制約がある場合はXOR法が圧倒的に有利”

5: hiroshima_pot 2025/07/06 22:53

XORが役に立つケースはもちろんあるけど、このケースではあまり説得力を感じないな。sumでオーバーフローしても結果は出るし、2個の場合は差の数の半分未満と半分以上に分割すればいい。

6: pekee-nuee-nuee 2025/07/06 22:54

ちゃんと読めば理解できそうなのであとで読むぞ

7: nmcli 2025/07/06 23:15

SQL でやると楽しい

8: kazuau 2025/07/06 23:22

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

9: kane-please 2025/07/06 23:34

アルゴリズム 最適化

10: omega314 2025/07/07 00:10

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

11: north_korea 2025/07/07 02:07

おもしろい

12: fraction 2025/07/07 02:49

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

13: aike 2025/07/07 02:59

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

14: dgen 2025/07/07 03:06

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

15: FreeCatWork 2025/07/07 03:24

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

16: timeout 2025/07/07 04:29

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

17: m-naze 2025/07/07 06:33

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

18: snow8-yuki 2025/07/07 06:40

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

19: tettekete37564 2025/07/07 06:59

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

20: mohno 2025/07/07 07:09

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

21: mk173 2025/07/07 07:16

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

22: ytn 2025/07/07 07:28

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

23: infobloga 2025/07/07 07:31

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

24: ad2217 2025/07/07 07:54

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

25: kobak 2025/07/07 08:16

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

26: egory_cat 2025/07/07 08:24

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

27: Wafer 2025/07/07 09:07

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

28: kazkun 2025/07/07 09:44

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

29: strangerxxx 2025/07/07 10:04

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

30: suka6411144 2025/07/07 10:07

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

31: mute0108 2025/07/07 10:27

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

32: t_mori 2025/07/07 11:38

“メモリ”

33: caffephilia 2025/07/07 12:07

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

34: kkobayashi 2025/07/07 12:53

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

35: mag4n 2025/07/07 12:55

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

36: tomono-blog 2025/07/07 13:40

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

37: yarumato 2025/07/07 14:18

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