如何生成所有整数 i, n & i == n (保持位长)

Question

我正在尝试想出一个有效的算法来生成所有整数 i、n 和 i == n。比如对于n == 4，bin(n) == '0b100'，我需要产生：

4 ('0b100')
5 ('0b101')
6 ('0b110')
7 ('0b111')

如何在 Python 中有效地做到这一点？

Answer 1

n = 4
b = n.bit_length()  # => 3
start = 1 << (b-1)  # => 1 << 2 => 4
for i in range(start, start*2):
    print(i, bin(i))

输出：

这将为 5、6、7（所有 3 位）产生相同的输出

Answer 2

这个有效：

def get_matches(n, bin_n):
    # It would be easier to pass number and numbits,
    # but this was the problem definition, so we'll
    # make sure they match...
    assert n == int(bin_n, 0), (n, bin_n)

    numbits = len(bin_n) - bin_n.index('b') - 1
    fmt = "{0:d} ('0b{0:0%db}')" % numbits
    for i in range(2 ** numbits):
        if i & n == n:
            print(fmt.format(i))

get_matches(4, '0b100')

结果：

4 ('0b100')
5 ('0b101')
6 ('0b110')
7 ('0b111')

Answer 3

我会开始使用简单的列表生成器：

n = 7; u = 256
for i in [x for x in range(n,u) if x & n == n]
    print(i)

您可以根据您的特定目的调整上限 (256) 和按位校验值 (7)。使用 n 的起始值是因为符合该条件的最小数字是 n 本身。

如果您发现列表变得太大（[...] 实际上会在内存中生成一个临时列表），您可以使用生成器而不是列表。它延迟计算每个值，因此您不必存储如此庞大的列表。这只是使用 (...) 而不是 [...]:

的问题

n = 7; u = 4294967296
for i in (x for x in range(n,u) if x & n == n):
    print(i)

对于十六位（如您在评论中指定的那样），这些内置方法应该足够快。在我的机器上，输出所有 16 位数字（使用 n = 0）只需要不到半秒 CPU 的时间，如果您什么都不做，则需要更令人印象深刻的 1/25 秒。

Answer 4

这是一个适用于任意整数的递归算法，而不仅仅是 2 的幂：

def matching_bitfields(n):
    if n == 0:
        yield 0
    else:
        has_free_bit = n & 1 == 0
        for m in matching_bitfields(n >> 1):
            m <<= 1
            if has_free_bit:
                yield m
            yield m | 1

def print_matching_bitfields(n):
    for x in matching_bitfields(n):
        print '%r (%r)' % (x, '0b{0:b}'.format(x))

print_matching_bitfields(4)

这将打印：

4 ('0b100')
5 ('0b101')
6 ('0b110')
7 ('0b111')

Answer 5

您只需递增 i 并确保 n 中的位保持设置即可获得此信息：

def next(n):
    i = n
    while (i >> 1) < n:
        yield i
        i = (i + 1) | n

这里我假设当 i 需要比 n 多的位时您想退出迭代。

如何生成所有整数 i, n & i == n (保持位长)

How to generate all integers i, n & i == n (keeping bit length)

python

bit-manipulation