Given a bitmask where the set bits describe where another number can be one or zero and the unset bits must be zero in that number. What's a good way to iterate through all its possible values?
For example:
000 returns [000]
001 returns [000, 001]
010 returns [000, 010]
011 returns [000, 001, 010, 011]
100 returns [000, 100]
101 returns [000, 001, 100, 101]
110 returns [000, 010, 100, 110]
111 returns [000, 001, 010, 011, 100, 101, 110, 111]
The simplest way to do it would be to do it like this:
void f (int m) {
int i;
for (i = 0; i <= m; i++) {
if (i == i & m)
printf("%d\n", i);
}
}
But this iterates through too many numbers. It should be on the order of 32 not 2**32.
There's a bit-twiddling trick for this (it's described in detail in Knuth's "The Art of Computer Programming" volume 4A §7.1.3; see p.150):
Given a mask mask
and the current combination bits
, you can generate the next combination with
bits = (bits - mask) & mask
...start at 0 and keep going until you get back to 0. (Use an unsigned integer type for portability; this won't work properly with signed integers on non-two's-complement machines. An unsigned integer is a better choice for a value being treated as a set of bits anyway.)
Example in C:
#include <stdio.h>
static void test(unsigned int mask)
{
unsigned int bits = 0;
printf("Testing %u:", mask);
do {
printf(" %u", bits);
bits = (bits - mask) & mask;
} while (bits != 0);
printf("\n");
}
int main(void)
{
unsigned int n;
for (n = 0; n < 8; n++)
test(n);
return 0;
}
which gives:
Testing 0: 0
Testing 1: 0 1
Testing 2: 0 2
Testing 3: 0 1 2 3
Testing 4: 0 4
Testing 5: 0 1 4 5
Testing 6: 0 2 4 6
Testing 7: 0 1 2 3 4 5 6 7
(...and I agree that the answer for 000
should be [000]
!)
First of all, it's unclear why 000 wouldn't return [000]. Is that a mistake?
Otherwise, given a mask value "m" and number "n" which meets the criterion (n & ~m)==0, I would suggest writing a formula to compute the next higher number. One such formula uses the operators "and", "or", "not", and "+", once each.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With