C++のビット演算まとめ【基礎編】

ビット演算とは？

整数を 2進数のビット列として見て、各ビット（0/1）を操作する演算。

• 速い（定数時間）
• 「集合」「フラグ管理」「全探索（2^N）」と相性が良い

基本の演算子（C++）

1) AND &

両方1なら1。

• 典型：特定ビットが立ってるか確認

  • if (mask & (1<<i)) ...
    • maskのi番目が1ならtrue

計算例

  a = 1101 (13)
  b = 1010 (10)
a&b = 1000 (8)

2) OR |

どちらか1なら1。

• 典型：ビットを立てる

  • mask |= (1<<i);（maskのi番目を1にする）

計算例

  a = 1101 (13)
  b = 1010 (10)
a|b = 1111 (15)

3) XOR ^

違えば1、同じなら0。

• 典型：ビット反転（トグル）

  • mask ^= (1<<i);
    • maski番目の0と1を入れ替える

計算例

  a = 1101 (13)
  b = 1010 (10)
a^b = 0111 (7)

4) NOT ~

0↔1 を全部反転（符号付きだと上位ビットも反転するので注意）。

• 典型：ビットマスク処理（使いどころはやや限定）

計算例

 a       = 1101
~a(4bit) = 0010

5) 左シフト <<

ビット列を左へずらす（だいたい×2）。

• 1<<i は i番目だけ1のマスク（2^i）
• mask << 1 は 2倍（オーバーフロー注意）

計算例

a      = 1101 (13)
a<<1   = 11010 (26)
a<<2   = 110100 (52)

6) 右シフト >>

ビット列を右へずらす（だいたい÷2）。

• mask >> i は i番目を下位に持ってくるのに使う

計算例

a      = 1101 (13)
a>>1   = 110 (6)
a>>2   = 11 (3)

具体例（超頻出パターン）

ビットの取得（i番目を0/1で取得する）

• bit = (mask >> i) & 1;

ビットが立っているか判定（i番目が1ならtrue）

• if (mask & (1<<i))

ビットを立てる / 下ろす / トグル

• 立てる：mask |= (1<<i);
• 下ろす：mask &= ~(1<<i);
• トグル：mask ^= (1<<i);

応用方法（AtCoderで使う “型”）

1) 部分集合全探索（Nが小さいときの必殺）

• for (mask=0; mask<(1<<N); mask++)
• 例：選ぶ/選ばない、白/黒、A/Bグループ分け

使う判断基準

• 「各要素に2択」＋「Nが小さい（だいたい N≤20 目安）」→ まず疑う

2) 集合をビットで持つ（高速な集合操作）

• 要素 i を含む ⇔ mask の iビットが1
• 和集合：A|B、共通部分：A&B、差集合：A&~B

3) 状態圧縮DP（bitDP）

• dp[mask] = mask の集合を作った/訪れたときの最小コスト みたいに使う
• 旅行セールスマン、最短ハミルトン、割り当て系など

4) フラグ管理

• たくさんの boolean を1つの整数に詰める（高速＆省メモリ）

よくある注意

• 1<<N は int の範囲に注意（Nが大きいなら 1LL<<N）
• 入力が1-indexなら 0-index化して「i=0..N-1」に揃えるとビットと相性が良い