競プロとかで毎回bit全探索を調べ直しているのでまとめる。
bit全探索とは
bit全探索とは、bit演算を使って全探索をする方法。bit全探索を使えば、部分集合を全パターン列挙することができる。
例えばAtCoderの「C - たくさんの数式 / Many Formulas」のような問題で、各文字列中のどこに+を入れるかというパターンを簡単に全探索できる。
bit全探索の例
例のコードは以下のようになる。（参考：ビット演算 (bit 演算) の使い方を総特集！ - Qiita）
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 3;
// {0, 1, ..., n-1} の部分集合の全探索
for (int bit = 0; bit < (1<<n); ++bit) {
vector<int> S;
for (int i = 0; i < n; ++i) {
if (bit & (1<<i)) { // 列挙に i が含まれるか
S.push_back(i);
}
}
cout << bit << ": {";
for (int i = 0; i < (int)S.size(); ++i) {
cout << S[i] << " ";
}
cout << "}" << endl;
}
}
標準出力は以下のようになる。
0: {}
1: {0 }
2: {1 }
3: {0 1 }
4: {2 }
5: {0 2 }
6: {1 2 }
7: {0 1 2 }
bit全探索のコード解説
一つずつ上記のコードを解説していく。まずは最初のfor文を見てみる。
// {0, 1, ..., n-1} の部分集合の全探索
for (int bit = 0; bit < (1<<n); ++bit) {
//
}
見慣れないのはおそらく(1<<n)の部分だと思う。(1<<n)は2^nと覚えよう。2^nは全パターン数と一致する。
<<という演算子はビット演算子で、ビット（2進数）を左へシフトする。int型は透過的に整数として扱えるが、実際に内部ではbitで管理されている。例えば3を8bitで保持するのであれば、0b00000011になる（2進数は先頭に0bをつける）。
そして1 (0b00000001)を左へ3ビットシフトする場合は1<<3と書き、結果は8(0b00001000)となる。
AND演算
次にこの部分を見る。
if (bit & (1<<i)) { // 列挙に i が含まれるか
まずは(1<<i)この部分。これは先ほど説明した通り、iが3なので2^3で8となる。
&の部分はAND演算、つまり「両方のビットが 1 のときのみ結果が 1 になるビット演算」である。
出力が7: {0 1 2 }となる場合は、bitが7 (0b00000111)である。というのも、どのビット位置（0~2番目）にもビットが立っているため、iが0~2どれであってもAND演算子ではtrueになり、全パターンである0 1 2を列挙することになる。
逆に4: {2 }の場合は4 (0b00000100)は右から3番目にしかビットが立ってないため、0~2の内、3番目である2しか列挙しないことになる。
このようにbitの特性を活かして全探索することができる。
bit全探索まとめ
(1<<n)は2^nと覚える(bit & (1<<i))はAND演算子であり、bitの特性を活かして列挙することができる
実際に手を動かして試すのが一番分かりやすい。