ビット演算
01 / 一文での本質
整数を「値」ではなくビットの並びとして見る。 同じ数を XOR すれば 0 になり、0 を XOR すれば変わらない。 パターンの肝は、問題に隠れたビットレベルの構造を見抜くこと。
問題ユニークな要素を見つける入力[2, 3, 5, 4, 5, 3, 4]
arr
2
3
5
4
5
3
4
acc
0
0
0
0
0
0
0
0
= 0
7 個の整数の配列。各値は 2 回ずつ出現する — 1 つを除いて。配列全体を XOR 畳み込みして見つける。
ステップ
0 / 15
累積
0
現在
—
結果
—
0 / 15
02 / パターンの骨格
# XOR 畳み込み — 一度だけ現れる要素を見つけるresult ← 0for x in arr:result ← result ⊕ xreturn result# XOR は可換・結合的、かつ a ⊕ a = 0:# 重複ペアは互いに打ち消し合い、ユニークな生き残りが残る。# 同じ骨格が:popcount、ビットマスク DP、ビットによる部分集合列挙にも効く。
03 / このパターンを使うべき合図
「1 回 / 2 回 / k 回現れる」
重複と一意性は XOR の十八番。すべての要素が 2 回ずつ、ただ 1 つを除いてが XOR-fold の典型題、3 回ずつ、ただ 1 つを除いてはビットごとの剰余に変わる。
「部分集合 / 冪集合」
N 要素のすべての部分集合は N ビットのビットマスクに対応する。mask を 0 から 2^N − 1 まで動かせば、 各部分集合を 1 回ずつ列挙できる — N ≤ 20 なら再帰より速く、コードも短い。「立っているビット数 / パリティ」
popcount(
x & (x − 1) は最下位の 1 を消す)とパリティが二大柱。 ハミング距離、釣り合いの取れた文字列、グレイコードなどに登場。「追加変数なしのスワップ / O(1) 追加領域」
明らかにハッシュ集合を使いたい問題に O(1) 追加領域 という制約が付いていれば、 それが最大のヒント。XOR が答えを単一の整数に押し込めるから付いている制約。
04 / よくある落とし穴
i.
XOR と OR を取り違える。
XOR(
⊕、^)は「異なるビット」。OR(|)は「どちらかが 1」。 記号の海では似て見えるが、「すべての要素が 2 回、ただ 1 つを除いて」型の問題では 完全に逆の働きをする — OR を使うと全要素の OR を取るだけで、何の役にも立たない。ii.
XOR の単位元が 0 であることを忘れる。
累積を
arr[0] ではなく 0 で初期化する。0 ⊕ x = x なので、 0 から始めればループ本体がすべての要素を一様に扱える。arr[0] から始めても動くが、 問題が一般化したときの境界 1 ずれが温床になる。iii.
論理 AND とビット AND の混同。
多くの言語で
&& は短絡評価で真偽を返す。& がビット演算。 混同すると式の型が静かに変わり、計算が壊れる。Python では and が論理、& がビット —— 真偽値に見える値の近くではとくに注意。05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。