bit全探索のテンプレート文の内容をメモ

記事を書く目的

bit全探索のテンプレート文にbit演算が多用されており、日を空けると忘れて調べ直しが続いているのでそれを無くしたい。

bit全探索テンプレート

for (int bit = 0; bit < (1 << n); bit++) // 1.
    {
        for (int i = 0; i < n; i++) // 2.
        {
            if (bit & (1 << i)) { // 3.
                
            }
        }
        
    }

1行ごとに内容説明

前提としてnが3の時とする

for (int bit = 0; bit < (1 << n); bit++) // 1.

c++だと2**nが使えない＋pow関数は誤差の問題があるので、bitシフトを使った書き方にせざるを得ない。
1 << 3 = 1000(2) = 8だから、0(000(2))から7(111(2))までループを回す

for (int i = 0; i < n; i++) // 2.

nが3だから0から2までループを回す

if (bit & (1 << i)) // 3.

bitが0(000)でiが2の時、1 << 2 = 100,000 & 100 = 000でfalseになる
bitが3(011)でiが2の時、011 & 100 = 000でfalseになる。
bitが7(111)でiが2の時、111 & 100は100でtrueになる。