1

What is the most efficient way to iterate through all bit masks of the integer in the bit count increasing order?

at first I need to iterate only through one bit masks:

0001 0010 0100 1000

then through two bit masks:

0011 0101 1001 0110 1010 1100

and so on.

ALEXANDER KONSTANTINOV
  • 913
  • 1
  • 7
  • 21
  • I don't quite understand. What does it mean to iterate "through all bit masks of the integer"? Can you give a complete explanation, maybe with integers of only few bits. – Adi Levin Jan 18 '16 at 11:47
  • Probably I'm not explaining well, I need to make the loop for (int i = 1....), where i takes values in the order that I described above – ALEXANDER KONSTANTINOV Jan 18 '16 at 11:49
  • Do you *really* need to get all the one bit masks out first etc., or can you iterate more generally, count the number of one bits, and process accordingly? – Bathsheba Jan 18 '16 at 11:49
  • @AdiLevin he wants to iterate through all integers, but sorted in order of number of non-zero bits. – CompuChip Jan 18 '16 at 11:49
  • Oh. Got it :-) Thanks – Adi Levin Jan 18 '16 at 11:50
  • Is it possible to apply `std::next_permutation` to `bitset`? – MBo Jan 18 '16 at 11:53
  • You basically want, for every bitcount N, to find all sorted tuples of length N whose values are in 0:31. For N=0, this is [()]. For N=1, this is [(0),(1),...,(31)]. For N=2 this is [(0,1),(0,2),....,(30,31)] etc... – Adi Levin Jan 18 '16 at 11:55

1 Answers1

2

Here's an attempt that uses recursion and iterates for 1 to 8 bit masks for all 8 bit numbers.

void generate(int numbits, int acc)
{
    if (numbits <= 0) {
        cout << "0x" << hex << acc << endl;
        return;
    }
    for (int bit = 0; bit < 8; ++bit) {
        if (acc < (1 << bit)) {
            generate(numbits - 1, acc | (1 << bit));
        }
    }
}

int main()
{
    for (int numbits = 1; numbits <= 8; ++numbits) {
        cout << "number of bits: " << dec << numbits << endl;
        generate(numbits, 0);
    }
}

Output:

number of bits: 1
0x1
0x2
0x4
0x8
0x10
0x20
0x40
0x80
number of bits: 2
0x3
0x5
0x9
0x11
0x21
0x41
0x81
0x6
...
number of bits: 7
0x7f
0xbf
0xdf
0xef
0xf7
0xfb
0xfd
0xfe
number of bits: 8
0xff
kfx
  • 8,136
  • 3
  • 28
  • 52