Generating All Bitsets

Posted: December 16, 2020 | Author: | Filed under: Bit twiddling, C++ | Leave a comment

Here’s a simple trick for iterating through all bitstrings with bits set only at certain positions (specified by a mask):

#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <bitset>

typedef uint16_t T;
T nextbitset(T n, T mask) {
  n |= ~mask; // Set all bits not in the mask
  n += 1;     // Increment
  n &= mask;  // Clear all bits not in the mask
  return n;
}

int main(int argc, char *argv[]) {
  T mask = strtoul(argv[1],0,2), n = 0; // Read in binary
  do {
    std::cout << std::bitset<8*sizeof(T)>(n) << "\n";
    n = nextbitset(n,mask);
  } while (n);
}

$ g++ -Wall bitset.cpp -o bitset
$ ./bitset 100011
0000000000000000
0000000000000001
0000000000000010
0000000000000011
0000000000100000
0000000000100001
0000000000100010
0000000000100011