bit全探索を理解する

はじめに

bit全探索は競技プログラミングをやっていると，必ず必要となる知識でしょう．
当記事は，筆者がbit全探索を理解した際のメモです．

bit全探索でできること

集合の部分集合を全て列挙することができます．
例えば， {1, 2, 3} の部分集合を全て列挙します．このとき部分集合は2³ =8通りあります．それは，集合の要素それぞれに「この要素を取るか取らないか」という2択の選択が生じているためです．これを2進数を用いて表現します．具体的には，0のときは「取らない」，1のときは「取る」とします．010の時は，{1}は0だから取らない，{2}は1だから取る，{3}は0だから取らないとなり，部分集合は{2}となります．

以上から，000から111まで繰り返せば，全ての部分集合を列挙することができます．

シフト演算とアンド演算

bit全探索を実装するには，bitを直接演算する必要があります．ここでは，演算の際に特に用いられるシフト演算とアンド演算について説明します．

シフト演算

bitを左右にシフトします．
例えば，0110は右に1bitシフトすると0011となり，左に1bitシフトすると1100となります．

C++では，以下のように記述することで実装できます．(0bを付けることで2進数になります)

// 左に1ビットシフト
0b0110 << 1
// 右に1ビットシフト
0b0110 >> 1

アンド演算

複数の2進数において，同じ位置のbitを比較し両方が1のときに1を返します．
例えば，0101と1100では0100を返します．

C++では，以下のように記述することで実装することができます．

0b0101 & 0b1100

実装

C++で先ほどの例を実装してみましょう．

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> a = {1, 2, 3};
  int n = a.size();
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if (i & (1 << j)) {
        cout << a[j] << ' ';
      }
    }
    cout << endl;
  }
  return 0;
}

解説

• 以下で集合のサイズを求めています．

int n = a.size();

• for文では，1を集合サイズである3つ分，左にシフトさせることで000から111までループさせています．

for (int i = 0; i < (1 << n); i++)

• 各桁を1とアンド演算し1のときのみ出力しています．

for (int j = 0; j < n; j++) {
  if (i & (1 << j)) {
    cout << a[j] << ' ';
  }
}