通过掩码的所有可能值迭代数字的好方法是什么？

Question

给定位掩码,其中设置位描述另一个数字可以是1或0的位置,并且未设置的位在该数字中必须为零.迭代所有可能值的好方法是什么？

例如:

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]

最简单的方法是这样做:

void f (int m) {
    int i;
    for (i = 0; i <= m; i++) {
        if (i == i & m)
            printf("%d\n", i);
    }
}

但这会迭代太多数字.它应该是32而不是2**32.

Answer 1

这是一个有点蠢蠢的技巧(在Knuth的"计算机程序设计的艺术"第4A卷§7.1.3中有详细描述;参见第150页):

给定一个掩码mask和当前组合bits,您可以生成下一个组合

bits = (bits - mask) & mask

...从0开始继续运行直到你回到0.(使用无符号整数类型来实现可移植性;对于非二进制补码机器上的有符号整数,这将无法正常工作.无符号整数是更好的选择无论如何,一个值被视为一组位.)

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

这使:

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

(......我同意答案000应该是[000]!)