Iterate through every bit mask of integer in bit count increasing order [duplicate]

Question

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.

Diplomacy

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. – Recessional

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 – Diplomacy

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? – Littles

@AdiLevin he wants to iterate through all integers, but sorted in order of number of non-zero bits. – Boldface

Oh. Got it :-) Thanks – Recessional

Is it possible to apply std::next_permutation to bitset? – Veronique

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... – Recessional

Answer 1

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

Currajong