分かりやすいbit全探索

コインを3回投げた時の表裏の出方は、全部で8通り(2³)あるが、
これらの全パターンは、次のように全探索することができる。(表を○、裏を×とする)
※(1 << n) は 2ⁿ と表せる。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 3;

    for (int bit = 0; bit < (1 << n); ++bit) {  
        vector<string> S;
        for (int i = 0; i < n; ++i) {     
            if (bit & (1 << i)) {                
                S.push_back("○");
            } else {
                S.push_back("×");
            }
        }

        for (int i = 0; i < (int)S.size(); ++i) {
            cout << S[i] << " ";
        }
        cout << endl;
    }
}

・実行結果

× × ×
○ × ×
× ○ ×
○ ○ ×
× × ○
○ × ○
× ○ ○
○ ○ ○

・解説
例えば、表を1、裏を0としたとき、
上記実行結果は、次のように8パターン重複することなく0～7の2進数で表せる。

× × ×->000->0
× × ○->001->1
× ○ ×->010->2
× ○ ○->011->3
○ × ×->100->4
○ × ○->101->5
○ ○ ×->110->6
○ ○ ○->111->7

上記コードでは、0～7(上記でいう変数bit)まで順番に見ながら、

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

bitを2進数で表すとどうなのかを確認している。

 if (bit & (1 << i)) {        

※(1 << i)は2ⁿなので、
例えば(1 << 2)->2²->4->100になる。
今回iは0->2なので、例えばbit=6の時、

 if (bit & (1 << i)) { -> if (110 & (001)) { -> 6を2進数にしたとき、1の位が1かどうか　
 if (bit & (1 << i)) { -> if (110 & (010)) { -> 6を2進数にしたとき、2の位が1かどうか
 if (bit & (1 << i)) { -> if (110 & (100)) { -> 6を2進数にしたとき、4の位が1かどうか

となる。

・こちらのサイトを参考にさせていただきました。 qiita.com