Iterate through every bit mask of integer in bit c

Question

This question already has answers here:

Generate all binary strings of length n with k bits set (12 answers)

Closed 4 years ago.

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.

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