【AtCoder向け】bit操作 完全攻略ガイド
AtCoderをやっていると、ある日突然こう思う。
「bit操作、毎回ググってるな…」
-
S >> i & 1の意味を毎回考える -
1 << Nが出てくると一瞬止まる - bit全探索やbitDPを見ると脳がフリーズする
この記事は、その状態から脱出するための完全ガイドです。
目的は3つ：
- bit操作を「暗記」ではなく「理解」で使えるようにする
- AtCoderで頻出のパターンを即座に書けるようにする
- bitDPや集合表現を「怖くない」状態にする
0. bit操作とは何か（超重要）
bit操作とは、
整数を2進数（0と1の列）として扱い、
各桁（bit）を直接操作する技術
です。
なぜAtCoderでbit操作が重要？
理由は明確で、bitは「集合」を最も高速に表現できるから。
| 表現 | 計算量 | 備考 |
|---|---|---|
| list / set | O(N) | Pythonでは遅い |
| bit | O(1) | 超高速・省メモリ |
1. 2進数とbitの対応関係
例：整数 13
13 = 1101 (2進数)
↑↑↑↑
3210 ← bit番号
| bit番号 | 値 |
|---|---|
| 0 | 1 |
| 1 | 0 |
| 2 | 1 |
| 3 | 1 |
「i番目のbit」= 2^i の位
2. 基本中の基本：ビット演算子一覧
| 演算子 | 意味 | 例 |
|---|---|---|
& |
AND | 101 & 110 = 100 |
| ` | ` | OR |
^ |
XOR | 101 ^ 110 = 011 |
~ |
NOT | ~101 = ...010 |
<< |
左シフト | 1 << 3 = 1000 |
>> |
右シフト | 1000 >> 3 = 1 |
3. AtCoder最頻出：1 << i の意味
1 << i
これは、
「i番目のbitだけが1の数」
| i | 2進数 | 10進数 |
|---|---|---|
| 0 | 0001 | 1 |
| 1 | 0010 | 2 |
| 2 | 0100 | 4 |
| 3 | 1000 | 8 |
集合で言うと「要素 i だけを含む集合」
4. i番目のbitが立っているか判定する
王道パターン（最重要）
if (S >> i) & 1:
意味を分解すると：
-
S >> i→ i番目を一番右に持ってくる -
& 1→ 最下位bitを見る
例
S = 13 # 1101
i = 2
(S >> 2) & 1
= 11 & 1
= 1 → 立っている
5. bit集合としての整数（ここが核心）
N個の要素 {0,1,...,N-1} を考える。
整数 S は：
「bitが1の場所の集合」を表す
例（N=4）
| S | 2進数 | 集合 |
|---|---|---|
| 0 | 0000 | {} |
| 1 | 0001 | {0} |
| 5 | 0101 | {0,2} |
| 15 | 1111 | {0,1,2,3} |
6. bit全探索（全ての部分集合）
書き方（完全テンプレ）
for S in range(1 << N):
for i in range(N):
if (S >> i) & 1:
# 要素 i が含まれる
計算量
- 全集合数：
2^N - N ≤ 20 が目安
7. bit操作で集合を操作する
要素を追加
S | (1 << i)
要素を削除
S & ~(1 << i)
要素が含まれるか
(S >> i) & 1
集合のサイズ（popcount）
bin(S).count("1")
（※PyPyではやや遅い）
8. bitDPとは何か（思想）
bitDPとは：
「状態を集合（bit）で持つDP」
典型構造
dp = [INF] * (1 << N)
dp[0] = 初期値
for S in range(1 << N):
for i in range(N):
if 条件:
dp[newS] = min(dp[newS], dp[S] + cost)
9. 実戦例：ペアリング問題（超頻出）
N人を2人ずつペアにする最小コスト。
ポイント
- 使った人をbitで管理
- 「最初の未使用」を固定して重複を防ぐ
実装例
dp = [10**18] * (1 << N)
dp[0] = 0
for S in range(1 << N):
if dp[S] == 10**18:
continue
# 最初の未使用 i を探す
i = -1
for k in range(N):
if not (S >> k) & 1:
i = k
break
if i == -1:
continue
for j in range(i+1, N):
if (S >> j) & 1:
continue
nS = S | (1 << i) | (1 << j)
dp[nS] = min(dp[nS], dp[S] + cost[i][j])
10. よくあるバグ集
❌ 1 << N-1
1 << N-1 # ← これは (1 << N) - 1 ではない
✅ 正しくは
(1 << N) - 1
❌ bit判定の優先順位ミス
if S >> i & 1: # ← 読みにくい
✅
if (S >> i) & 1: