ビット演算

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 / よくある落とし穴

XOR と OR を取り違える。
XOR(⊕、^)は「異なるビット」。OR(|)は「どちらかが 1」。 記号の海では似て見えるが、「すべての要素が 2 回、ただ 1 つを除いて」型の問題では 完全に逆の働きをする — OR を使うと全要素の OR を取るだけで、何の役にも立たない。
XOR の単位元が 0 であることを忘れる。
累積を arr[0] ではなく 0 で初期化する。0 ⊕ x = x なので、 0 から始めればループ本体がすべての要素を一様に扱える。arr[0] から始めても動くが、 問題が一般化したときの境界 1 ずれが温床になる。
論理 AND とビット AND の混同。
多くの言語で && は短絡評価で真偽を返す。& がビット演算。 混同すると式の型が静かに変わり、計算が壊れる。Python では and が論理、& がビット —— 真偽値に見える値の近くではとくに注意。

05 / LeetCode で練習

簡単19

01Add Binary— LC 67→02Single Number— LC 136→03Reverse Bits— LC 190→04Number of 1 Bits— LC 191→05Power of Two— LC 231→06Missing Number— LC 268→07Power of Three— LC 326→08Counting Bits— LC 338→09Power of Four— LC 342→10Find the Difference— LC 389→11Convert a Number to Hexadecimal— LC 405→12Fizz Buzz— LC 412→13Hamming Distance— LC 461→14Number Complement— LC 476→15Complement of Base 10 Integer— LC 1009→16Number of Steps to Reduce a Number to Zero— LC 1342→17Sort Integers by The Number of 1 Bits— LC 1356→18XOR Operation in an Array— LC 1486→19Check if the Sentence Is Pangram— LC 1832→

中級20

01Reverse Integer— LC 7→02Divide Two Integers— LC 29→03Pow(x, n)— LC 50→04Subsets— LC 78→05Single Number II— LC 137→06Repeated DNA Sequences— LC 187→07Bitwise AND of Numbers Range— LC 201→08Single Number III— LC 260→09Maximum Product of Word Lengths— LC 318→10Sum of Two Integers— LC 371→11Maximum XOR of Two Numbers in an Array— LC 421→12Total Hamming Distance— LC 477→13Beautiful Arrangement— LC 526→14Partition to K Equal Sum Subsets— LC 698→15Maximum Length of a Concatenated String with Unique Characters— LC 1239→16Number of Steps to Reduce a Number in Binary Representation to One— LC 1404→17Decode XORed Permutation— LC 1734→18Minimum Number of Work Sessions to Finish the Tasks— LC 1986→19Fair Distribution of Cookies— LC 2305→20Bitwise XOR of All Pairings— LC 2425→

難しい7

01Shortest Path Visiting All Nodes— LC 847→02Find the Shortest Superstring— LC 943→03Smallest Sufficient Team— LC 1125→04Parallel Courses II— LC 1494→05Maximum Number of Achievable Transfer Requests— LC 1601→06Minimum One Bit Operations to Make Integers Zero— LC 1611→07Distribute Repeating Integers— LC 1655→