通过位计数递增的顺序整数的每一个位掩码迭代 [英] Iterate through every bit mask of integer in bit count increasing order

问题描述

什么是通过该位的整数的所有位掩码迭代计算递增的顺序最有效的方法是什么？

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

然后通过两个位掩码：

0011
0101
1001
0110
1010
1100

等。

推荐答案

下面是一个使用递归迭代和1〜8位掩码的所有8位数字的一种尝试。

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);
    }
}

输出：

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

这篇关于通过位计数递增的顺序整数的每一个位掩码迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！