bit全探索

bit全探索とは、N個のものから、いくつか選ぶ方法を全列挙して調べ上げる方法

参考

習得の流れ

座学：各ループ及び変数が何を表現しているか自分の言葉で表現する。

演習：

bit全探索最初の一歩 O(2^N)

C++ for(int bit=0; bit < (1<<N); ++bit ){

python for bit in range(1<<N):

Rust for bit in 0..1<<N{

整数値から、「いくつか選ぶ方法」への復元

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

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

理解

(2^N)全探索って呼ぶと私は理解しやすい。

1次ループ（変数bit）に対して、2次ループ（変数i）で各桁のbitが立っているか

立っているなら任意の処理（今回は要素を足す）する。1次ループが2^n回すからめっちゃまわる。