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

Question

给定一个位掩码，其中设置的位描述了另一个数字可以是1或0的位置，而未设置的位必须是该数字中的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("%dn", i);
    }
}

但是这遍历了太多的数字。应该是32而不是2**32。

Answer 1

对此有一个小技巧(它在Knuth的"计算机编程的艺术"卷4A§7.1.3中有详细描述;见p.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] !)

Answer 2

首先，不清楚为什么000不返回[000]。这是个错误吗?

否则，给定一个掩码值"m"和数字"n"，满足(n &~m)==0，我建议写一个公式来计算下一个更高的数字。其中一个公式使用操作符"and"、"or"、"not"one_answers"+"，各使用一次。

Answer 3

@Matthew的把戏太神奇了。下面是一个不那么棘手，但不幸的是，它也是一个效率较低的Python递归版本:

def f(mask):
    if mask == "0":
        return ['0']
    elif mask == '1':
        return ['0', '1']
    else:
        bits1 = f(mask[1:])
        bits2 = []
        for b in bits1:
            bits2.append('0' + b)
            if mask[0] == '1':
                bits2.append('1' + b)
        return bits2
print f("101")  ===> ['000', '100', '001', '101']

Answer 4

你可以用蛮力。-) Ruby示例:

require 'set'
set = Set.new
(0..n).each do |x|
  set << (x & n)
end

(其中set是一个集合数据类型，即删除重复项)

Answer 5

试试下面的代码:

def f (máscara):
    se máscara == "0":
        voltar ['0 ']
    elif máscara == '1 ':
        voltar ['0 ', '1']
    else:
        bits1 = f (máscara [1:])
        bits2 = []
        para b em bits1:
            bits2.append ('0 '+ b)
            se máscara [0] == '1 ':
                bits2.append ('1 '+ b)
        voltar bits2
print f ("101") ===> ['000 ', '100', '001 ', '101']