C++におけるbit全探索記法

1　はじめに

　本記事はC++超初心者である人間が自分なりに理解するために書いたものであるため間違いや誤解があると思いますが温かい目で読んでやってください！！

2　前提

　今回は4つの果物を選ぶか選ばないかを例に挙げます。果物の順番はリンゴ、ミカン、ブドウ、スイカとします。結果が 0 1 1 0 の場合ミカンとブドウだけが選ばれたことを表します。またこの数字の組み合わせは0000~1111までの16通り存在します。

3　実装

bit全探索

//nは果物の数である4を入力として与えます。
#include <iostream>
#include <vector>
using namespace std;

int main(){
   int n = 4;
   vector<vector<int>> fruits_bits;// 全部の部分集合を格納
   
   for (int bit = 0; bit < (1 << n); bit++){
       vector<int> fruits_bit;// 今回の部分集合
       for (int i = n-1; i >= 0; i--){
           if (bit & (1 << i)) fruits_bit.push_back(1);
           else fruits_bit.push_back(0);
       }
       fruits_bits.push_back(fruits_bit);
   }

   //以下は出力用に書いたもの
   for (int a = 0; a < (1 << n); a++){
       for (int b = 0; b < n; b++){
           cout << fruits_bits[a][b];
       }
       cout << " ";
   }
}

4　説明

point１

for (int bit = 0; bit < (1 << n); bit++){}

　1行目で一番わからない部分が(1 << n)という記述だと思います。「<<」 これは左シフト演算子といって、数字を左にずらす操作、つまり2倍することで結果的に 2^n となります。つまりここでは1を左に4シフトしてるので10000となり、bitがあらわす数は2進数では0000~1111つまり16回ループすることになります。

point2

//bit = 0000~1111が入る
for (int i = n-1; i >= 0; i--){}

　ループ変数 i を n-1 から 0 まで減らしながら回します（n=4の場合0000~1111で全部4桁）
ここで i は ビットの位置を表します
i = 3 → 左端の上位ビット
i = 0 → 右端の下位ビット

　ここでなんでfor (int i = 0; i < n; i++)の順番でループしないのかというと、もし下位ビットから判定してしまうと、push_backで集合の末尾に要素を入れることによって、果物の順番と2進数の順番が逆になっちゃうからです。

point3

//bit = 0000~1111
//i = 0~3
if (bit & (1 << i)) fruits_bit.push_back(1);
else fruits_bit.push_back(0);

　bit & (1 << i) → bit の i番目のビットが 1 かどうか判定もし 1 なら そのビットは ON なので 1 をfruits_bit集合に入れる、そうでなければそのビットは OFF なので 0 を入れるという判定です。

出力

出力

 0000 0001 0010 0011 0100 0101 0110 0111 
 1000 1001 1010 1011 1100 1101 1110 1111

　このように全列挙できるので元コードに自分の行いたい判定を入れると探索できます。

まとめ

　C++でのbit全探索ではPythonとちがって2**nを簡単に表せないところが難しく感じる箇所なのかな思いました。また当たり前のことながらに、自分たちが入出力で扱う10進数がコード内部では2進数として扱われていることもループ回数で困惑する原因になっていると感じました(シフト演算子とかとくに)
初めての記事でうまく言語化できない部分もありましたが読んでいただきありがとうございました！！