bit全探索を理解するために

published: 2021/8/26 update: 2021/8/28

Table of Contents

TL;DR

全探索をする際の重要なアルゴリズムとして、bit全探索が挙げられます。bit全探索を使うことで、部分集合を全パターン列挙できます。

しかし、実際のコードを見て何をやっているのか直感的に理解することが難しかったので、自分が理解しやすい形でまとめてみました。

bit全探索のアルゴリズム

bit全探索で使用するbit演算は以下です。0bは2進数表記であることを示します。

演算名演算子説明
bitごとのAND&共に1のところだけが1になる0b0101 & 0b0011 = 0b0001
bitごとの左シフト<<2倍0b01011 << 1 = 0b10110
  1. bitをn回左シフトし(2^n)、その数ループを回す
  2. ループ内でn回ループさせる(部分集合分)
  3. bitが当てはまる部分の数値がそのループ内での部分集合

bitが当てはまる部分の数値を整理すると(bit & (1 << i))が0にならないiをseqに格納していくことから以下のようになります(0bは二進数表記)。

書き下してみるときれいに部分集合が列挙されています。すなわち、(bit & (1 << i))はbitが一致する場所は0以外になる、ということです。

bitbit(0b)i=0(0b)bit&ii=1(0b)bit&i(0b)i=2(0b)bit&2array
00000000100010001000()
10001000110010001000(0)
20010000100010201000(1)
30011000110010201000(0,1)
40100000100010001004(2)
50101000110010001004(0,2)
60110000100010201004(1,2)
70111000110010201004(0,1,2)

実装

nim

import sequtils

let n = 3

# {0, 1, ..., n-1}の部分集合を全探索
for bit in 0..<(1 shl n):
  var vec = newSeq[int]()
    for i in 0..<n:
      if (bit and (1 shl i)) != 0:
        vec.add(i)
  echo bit, " : ", vec

記事に間違い等ありましたら、お気軽に以下までご連絡ください

E-mail: illumination.k.27|gmail.com ("|" replaced to "@")

Twitter: @illuminationK

当HPを応援してくれる方は下のリンクからお布施をいただけると非常に励みになります。

Ofuse

Other Articles

Site Map

Table of Contents

    TL;DR

    bit全探索のアルゴリズム

    実装

      nim


当HPを応援してくれる方は下のリンクからお布施をいただけると非常に励みになります。

Ofuse
Privacy Policy

Copyright © illumination-k 2020-2021.