読者です 読者をやめる 読者になる 読者になる

初めてのビット操作を使った全探索

ビット操作 全探索

問題 (AtCoder ABC002 D)

abc002.contest.atcoder.jp

ソースコード

解説

ビット操作により全探索をする。この問題はNの数が最大でも12なので、最大でも212 = 4096通り。 候補に対して、その要素を含むか否かの2パターンを12要素分行う。 その際、その要素を含むか否かをビットを用いて管理する。 含む=> 1 含まない=> 0

例 N = 4の時、N桁の2進数で管理「0000」。 0001: 一つ目の要素が含まれる 0100: 3つ目の要素が含まれる 0101: 1つ目と3つ目の要素が含まれる

ポイント1

要素を含むか否かを全列挙するためにビット操作

for (int i = 0; i < 1<<N; i++) {
   //....
}

このループで全てのパターンを列挙できる。 1<<Nについて

<<演算子は指定した数値の数だけ左にシフトするというもの。 つまり、N = 3 のとき、1<<N1<<3となり、1000となる。 この時、i < 1000 → iが111まで繰り返すことになる。(2進数だから1000の1つ前は111) これより、このループでは全てのパターンを列挙することができる。

ループ中のiの動き

0
1
10
11
100
101
110
111
1000

ポイント2

if ((1 & i >> j) == 1) { 

について これは、2進数のそれぞれの桁数を見てあげて、その要素が1であればリストに追加するという処理。

i = 101の時
  j = 0 (シフト無し)
  ``1 & i >> j`` → `` 1 & 101`` (1& は一桁目を見るから) → 1

  j = 1 (1つ右にシフト)
  ``1 & i >> j`` → `` 1 & 10`` (1& は一桁目を見るから) → 0

  j = 2 (2つ右にシフト)
  ``1 & i >> j`` → `` 1 & 1`` (1& は一桁目を見るから) → 1

コレによってiの中でフラグが立っている要素のみ、リストに加える事ができる。