Module: Iterate over all subpatterns of a given mask

It happens that it is necessary to enumerate all bit sequences of a certain length. Or in other words, iterate over all possible options, where for each object one of two possible states is selected.

In such situations, it is possible to implement enumeration using bit masks. The advantage of this approach is that such code works non-recursively and operates on numbers instead of collections or the like, which greatly improves performance.

The general code using bitmasks is given below: intn; // number of oobjects (length of bit sequence) for (int mask = 0; mask < (1 << n); mask++) { // loop through all numbers from 0 to 2^n - 1, where each number corresponds to a bitmask // the current number mask is a bitmask, where the i-th bit specifies the state of the i-th object for (int i = 0; i < n; i++) { // iterate over n bits to understand what state each object has if ((1 << i) & mask) { // check if the i-th bit is equal to one // process the option that the i-th object has the state '1' } else { // case when the i-th bit is zero // process the option that the i-th object of the state '0' } } }
This code runs in O(2^n * f(n)), where f(n) is the time it takes you to process one particular iterable.