有效地生成二进制掩码中的所有整数

Question

假设我有一些二进制掩码mask。（例如 0b101011011101）

是否有一种有效的方法来计算所有整数 k 使得 k & mask == k？（其中 & 是按位与运算符）（或者，k & ~mask == 0）

如果mask有m个，那么正好有2^m个数满足这个属性，所以好像有应该是某种 O(2^m) 的过程。枚举小于掩码的整数是一种浪费（尽管很容易消除不适用的值）。

Answer 1

我想通了...您可以像下面这样识别所有单位模式，因为在计算 k & (k-1) 时清除了任何整数 k 的最低有效 1 位：

def onebits(x):
    while x > 0:
        # find least significant 1 bit
        xprev = x
        x &= x-1
        yield x ^ xprev

然后我可以使用 ruler function 对 1 位的各种组合进行异或，以模拟每次切换计数器的哪些位：

def maskcount(mask):
    maskbits = []
    m = 0
    for ls1 in onebits(mask):
        m ^= ls1
        maskbits.append(m)
    # ruler function modified from 
    # http://lua-users.org/wiki/LuaCoroutinesVersusPythonGenerators
    def ruler(k):
        for i in range(k):
            yield i
            for x in ruler(i): yield x    
    x = 0
    yield x
    for k in ruler(len(maskbits)):
        x ^= maskbits[k]
        yield x

看起来像这样：

>>> for x in maskcount(0xc05):
...     print format(x, '#016b')
0b00000000000000
0b00000000000001
0b00000000000100
0b00000000000101
0b00010000000000
0b00010000000001
0b00010000000100
0b00010000000101
0b00100000000000
0b00100000000001
0b00100000000100
0b00100000000101
0b00110000000000
0b00110000000001
0b00110000000100
0b00110000000101

Answer 2

解决问题的一个简单方法是找到掩码中设置的位，然后简单地用i计数，然后用掩码中的相应位替换i的位。

def codes(mask):
    bits = filter(None, (mask & (1 << i) for i in xrange(mask.bit_length())))
    for i in xrange(1 << len(bits)):
        yield sum(b for j, b in enumerate(bits) if (i >> j) & 1)

print list(codes(39))

每次迭代的工作量为 O(log(N))（其中 N 是 mask 中设置的位数）。

通过使用 gray codes 进行计数，可以提高效率，并且每次迭代的工作量为 O(1)。使用格雷码计数，每次迭代仅更改一个位，因此可以有效地更新当前值 v。显然这比上面的简单解决方案更难理解。

def codes(mask):
    bits = filter(None, (mask & (1 << i) for i in xrange(mask.bit_length())))
    blt = dict((1 << i, b) for i, b in enumerate(bits))
    p, v = 0, 0
    for i in xrange(1 << len(bits)):
        n = i ^ (i >> 1)
        v ^= blt.get(p^n, 0)
        p = n
        yield v

print list(codes(39))

使用格雷码的一个缺点是结果不是按数字顺序返回的。但幸运的是，这不是问题的条件！

有效地生成二进制掩码中的所有整数

efficiently generating all integers within a binary mask

combinatorics