Generate all bit patterns for a given mask

Question

My problem is this: I have the value x and the pattern p both variables of the same size. The goal is to iterate over all bit patterns x that are not masked by p.

Example: if we have p = 1001 , we want to find 0000 , 0001 , 1000 and 1001 - not necessarily in that order.

The standard implementation is in C99 (a return value indicates whether we returned all values):

 static bool next(size_t val, size_t mask, size_t *out) { if (val == mask) { return false; } size_t current = val & mask; size_t inc = 1; size_t new_val = current + inc; while ((new_val & mask) <= current) { inc++; new_val = current + inc; } *out = new_val; return true; } 

I would have thought there should be some trick to make this more efficient, but I can’t find any big improvements (other than calculating the trailing zeros of the mask and setting the initial value of inc accordingly, which isn’t a big part of the improvement).

Edit: It is also important that for each generated value a lot of additional work is generated, which means that a lot of duplicates are out of the question (some duplicates, even if they are not recognized, will be fine, there are no side effects to the work done, this just slowdown).

Answer 1

This generates all bit patterns in the reverse order (the initial value of val should be equal to mask ):

 static bool next(size_t val, size_t mask, size_t *out) { if (val == 0) { return false; } *out = (val - 1) & mask; return true; } 

---

And this (slightly less obvious code) generates all bit patterns in direct order (the initial value of val must be zero):

 static bool next(size_t val, size_t mask, size_t *out) { if (val == mask) { return false; } *out = (val - mask) & mask; return true; } 

Answer 2

From your example, this pseudo code seems to do the trick:

 current = p // set up current getNotMasked(p, 0) // initial call bitString current getNotMasked(int pos) if (pos == current.length) print(current) return if (current[pos] == 1) current[pos] = 0 getNotMasked(pos+1) current[pos] = 1 getNotMasked(pos+1) else getNotMasked(pos+1) 

It is not difficult to create C code here - replace bitString with int and [pos] with & 1 << pos or similar.

Answer 3

The most optimal way:

• Count the number of bits set in the mask, p
• Find out how to shuffle bits from a “normalized” binary value to a pattern-defined position
• Count after 0..2 ^p -1
• For each shuffle value to create a pattern-compatible value

This, of course, assumes that shuffling is reasonably efficient, otherwise it is easier to drag and drop, just calculating from 0 to the maximum possible value depending on the total number of bits in the pattern and applying a pattern on each count. Finding duplicates can be a bit expensive.

For p = 9 (binary 1001 ₂ ), there are only two bits, so we know that to generate 2, the values ​​are ² = 4.

Scanning the picture on the right for 1 bit, we can form the following shuffle table:

• Bit 0 is copied from bit 0
• Bit 3 is copied from bit 1

So, we can calculate from 0 to 3, and for each value regroup in accordance with the table:

• 00 ₂ outputs pin 0000 ₂
• 01 ₂ outputs 0001 ₂
• 10 ₂ gives a conclusion of 1000 ₂
• 11 ₂ displays the result 1001 ₂