個人的ビット全探索と仲良くなる覚書

ビット演算と、それを用いたビット全探索について個人的な覚え書きとしてまとめます。

ビット全探索いつ使う

• しらみつぶしに組み合わせ知りたい時
  • 特に$N$個の整数から何個か選んでほにゃほにゃするのとかよくある
  • 数学的にいうなら「集合$N$に含まれる部分集合$e∈N$の組み合わせを列挙したいとき」?
  • ただ計算量オーダーが$O(N2^N)$らしいのであんまでかいデータにはつかえん

ビット演算

• $AND$はビット(2進数)どうしの同じ位がどちらも1だった時にそこの位にだけ1を足したやつ返す

  • 101 AND 001 = 001
  • ビット全探索はこいつが1以上の時TRUEである性質を使う

• 左シフト(i << s)…iを2進数換算でs回左にずらす

  • ずらす数が1の場合、実質的に1だけがずれていくので各ケタ1回ずつ1がこんにちはしていく　この性質も使う　あと(たぶん)1のときは$2^s$でもある

    // 1 << 0 -> 0001 2^0(1)
    // 1 << 1 -> 0010 2^1(2)
    // 1 << 2 -> 0100 2^2(4)
    // ...
    
    

ビット全探索

流れは

1. "組み合わせパターンID"であるi = 0を1 << N(組み合わせの総数)でループをまわす(以下まわす)
2. ループの中でj = 0をN(シフトできる回数=要素の個数)でまわす
   1. 1をjだけ左シフト(1 << j)させて各ケタの1とANDで照合

      if (i & (1 << j)) // カッコ大事 &はビット演算のAND
      // if (各「組み合わせパターン」と各「1をjケタ移動させた数」のどちらの同じケタにも1が含まれているか?)
      

   2. 「TRUE=要素がその部分集合に含まれている」ということなのでNの中身配列a[idx]などのインデックスにjをあてはめて該当する要素の値を取り、sumに加算などする
   3. 2-1.~2-2. をjが尽きるまで(=すべてのケタ試すまで)くりかえす

確かに計算量は$O(N2^N)$っぽい(jのループを$N$回やるiのループを$2^N$回)

そもなんでビットで行けるのか

$e=\{ a_1, a_2, a_3 \}$って集合があったとしてそれぞれの要素$a_{nanchara}$と"組み合わせナンバー"を2進数表記した時のそれぞれのケタを1つずつ対応させられるから

集合	組み合わせナンバー(i)	2進数表記
$e = ∅$	0	000	すべてのはじまり
$e = \{a_1\}$	1	001	$a_1, a_2$は透明なイメージ
$e = \{a_2\}$	2	010	$a_1, a_3$は透明
$e = \{a_1, a_2\}$	3	011
$e = \{a_3\}$	4	100
$e = \{a_1,a_3\}$	5	101
$e = \{a_2,a_3\}$	6	110
$e = \{a_1,a_2,a_3\}$	7	111	最終回

ただ注意!　a[idx]と2進数表記では要素の方向が逆になる(2進数というか1は左に進んでいくが、a[idx]は右に進んでいくため)。正確には順番を逆で定義しているだけだが、ただこっちの方がforが0からインデックスをとる仕様などと都合がいい。