Understanding Bit Exhaustive Search

TL;DR

Bit exhaustive search is an important algorithm for exhaustive enumeration. By using bit exhaustive search, you can enumerate all subsets of a given set.

However, I found it difficult to intuitively understand what the actual code is doing, so I summarized it in a way that makes sense to me.

Bit Exhaustive Search Algorithm

The bit operations used in bit exhaustive search are as follows. 0b indicates binary notation.

1. Left-shift a bit n times (2^n) and loop that many times
2. Inside the loop, iterate n times (for each subset element)
3. The values at positions where the bit matches form the subset for that iteration

When we organize the values at matching bit positions, we store each i where (bit & (1 << i)) is not 0 into a sequence, resulting in the following (0b denotes binary notation).

When written out, the subsets are neatly enumerated. In other words, (bit & (1 << i)) returns a non-zero value at positions where the bits match.

Implementation

nim

import sequtils

let n = 3

# Enumerate all subsets of {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