What is a good way to repeat a number through all possible mask values?

Question

Given the bitmask, where the set bits describe where the other number can be one or zero, and the unoccupied bits must be zero in that number. What a good way to iterate through all 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 easiest way to do this is 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 is repeated through too many numbers. It should be about 32 not 2 ** 32.

Answer 1

There are a few tricks for this: it is described in detail in Knuth's book “The Art of Programming” of Volume 4A §7.1.3, see page 150):

Given the mask mask and the current bits combination, you can create the following combination with

 bits = (bits - mask) & mask 

... start from 0 and continue until you return to 0. (Use an unsigned integer type for portability to use, this will not work properly with integers on machines with an extra complement. The best choice for value, which is 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] !)

Answer 2

First of all, it is not clear why 000 will not return [000]. This is mistake?

Otherwise, given the value of the mask "m" and the number "n" that meets the criterion (n and ~ m) == 0, I would suggest writing a formula to calculate the next larger number. One such formula uses the operators "and", "or", "not" and "+", after each.

Answer 3

@ Matthew's trick is awesome. Here's a less complicated, but unfortunately less efficient, recursive version in Python:

 def f(mask): if mask == "0": return ['0'] elif mask == '1': return ['0', '1'] else: bits1 = f(mask[1:]) bits2 = [] for b in bits1: bits2.append('0' + b) if mask[0] == '1': bits2.append('1' + b) return bits2 print f("101") ===> ['000', '100', '001', '101'] 

Answer 4

You can do it with brute force. ;-) Ruby example:

 require 'set' set = Set.new (0..n).each do |x| set << (x & n) end 

(where set is the given data type, i.e. removes duplicates.)

Answer 5

Try this code:

 def f (máscara): se máscara == "0": voltar ['0 '] elif máscara == '1 ': voltar ['0 ', '1'] else: bits1 = f (máscara [1:]) bits2 = [] para b em bits1: bits2.append ('0 '+ b) se máscara [0] == '1 ': bits2.append ('1 '+ b) voltar bits2 print f ("101") ===> ['000 ', '100', '001 ', '101'] 

é interessante.