bit 全探索

キーワード

bit を用いた全探索の手法。

$\{0,1, \dots, N-1\}$ の全ての部分列を列挙できる。

$\mathrm{O}(N2^N)$

for b := 0; b < (1 << n); b++ {
    for i := 0; i < n; i++ {
        if (b & (1 << i)) == 0 {
				continue
		}
 
        // ...
    }
}

1 << nで $1\underbrace{0 \dots 0}_{n}{}_{(2)} = 2^n{}_{(10)}$ となるので、bは $0$ から $2^n - 1$ まで動く。

その後、各i $=1,\dots,n-1$ について、1 << iで $1\underbrace{0\dots0}_{i}{}_{(2)}$ となるので、(b & (1 << i))で $i$ 桁目が $1$ かどうか判定する。

go の場合は、if 文の条件をbool型しかいれることができないので、 $0$ の場合は早期 return する形にしている。