実装例付き!bit全探索~計算量の見積もりもあるよ~

今回も競プロネタです。

bit全探索はよく出てくる方法ですが、よく忘れるので記事を書いておくことで記憶の定着を図ることにしました。
未来の自分と、このブログにたまたまたどり着いた幸運な(?)読者の方に参考になれば幸いです。

また、競プロ関連の記事は他にも書いています。今後必要なことを拡充していきたいと思いますので参考にしてみて下さい！
→「プログラミングコンテスト」一覧

bit全探索って何ぞ？
bit演算
AND演算
シフト演算
実装例
まとめ

bit全探索って何ぞ？

bit全探索とは\(n\)個の2択の選択肢があったとき、各選択肢でどちらをとるかを全状態試す探索方法です。
計算量は\(O\left(2^n\right)\)なります。なぜなら各選択肢をA,Bとした場合、全てAの状態からどこかBの状態、全てBまで全状態数が\(2^n\)個あるからです。
なので(私の知っている限りだと)bit全探索を使う問題は制約が小さいです。

bit演算

bit全探索に進む前に、AND演算・シフト演算について説明します。

AND演算

AND演算とは2つのビット列\(x\)、\(y\)のANDをとる演算です。
\(x\)、\(y\)のビットがともに1のとき1
それ以外は0になります。

\(x\)	\(y\)	\(x\) AND \(y\)
0	0	0
0	1	0
1	0	0
1	1	1

c++ではAND演算子を&と書きます。

シフト演算

シフト演算とはビット列全体を右に移動したり左に移動したりする演算です。

例えば「0001」というビット列があったとしてこれを左に1だけシフト演算を行うと「0010」というビット列になり、2だけシフト演算を行うと「0100」になります。
逆に右に1だけシフト演算を行うと「0000」になります。

このようにシフト演算とはビット列を左右に移動させ、空白になるビットは0で埋める演算です。

c++では変数iの右シフト演算を(i >> j)のように「>>」と書き、
左シフト演算を(i << j)のように「<<」と書きます。

実装例

\(n\)個の選択肢をbit全探索する実装例は以下のようになります。

using namespace std;
int main(void){
int n; cin >> n;
for(int bit = 0;bit < (1<<n);++bit){
  for(int i = 0;i<n;++i){
    if((bit >> i) & 1){
      //なんか処理
    }
  }
}

return 0;
}

bitという変数で\(2^n\)個の状態を管理します。
先ほどのシフト演算の話から(1<<n)というのは\(2^n\)を表します。

iという変数で各選択肢を見に行きます。
bitをi個右シフトして1とANDをとることで、選択肢iが1かどうかを見ることができます。

あとは問題に応じて処理をすればbit全探索ができます。