给定一个位掩码其中该组比特表示，其中另一数目可以是一或零和非设定位必须是在该次数为零。什么是遍历所有可能的值的好办法？

Given a bitmask where the set bits describe where another number can be one or zero and the unset bits must be zero in that number. What's a good way to iterate through all its possible values?

例如：

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]

要做到这一点就做这样的最简单的方法：

The simplest way to do it would be to do it like this:

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

不过这个遍历太多的数字。它应该是32的顺序而不是2 ** 32。

But this iterates through too many numbers. It should be on the order of 32 not 2**32.

推荐答案

有一个位变换伎俩这个（它的详细Knuth的描述卷4A§7.1.3计算机程序设计艺术，见第150页）：

There's a bit-twiddling trick for this (it's described in detail in Knuth's "The Art of Computer Programming" volume 4A §7.1.3; see p.150):

鉴于口罩面膜和当前相结合位，您可以生成

Given a mask mask and the current combination bits, you can generate the next combination with

bits = (bits - mask) & mask

...从0开始，并继续下去，直到你回到0（使用一个无符号整数类型的便携性;对非二进制补码机有符号整数，这将无法正常工作的无符号整数是一个。一个值更好的选择，被视为一组位反正。）

...start at 0 and keep going until you get back to 0. (Use an unsigned integer type for portability; this won't work properly with signed integers on non-two's-complement machines. An unsigned integer is a better choice for a value being treated as a set of bits anyway.)

例如在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] ！答案）