如何有效地生成具有 M 个设置位的所有 N 位值以及相应的位反转值？

Question

我使用以下 Python 代码来生成所有具有

popcount

设置位的值，其中

bits

总位数：

def trailing_zeros(v):
    return (v & -v).bit_length() - 1

def bit_permutations(popcount, bits):
    if popcount < 0 or popcount > bits:
        pass
    elif popcount == 0:
        yield 0
    elif popcount == bits:
        yield (1 << bits) - 1
    else:
        v = (1 << popcount) - 1
        while v < (1 << bits):
            yield v
            t = v | (v - 1)
            v = (t + 1) | (((~t & -~t) - 1) >> (trailing_zeros(v) + 1))

例如，

bit_permutations(5, 3)

会产生

0b00111, 0b01011, 0b01101, 0b01110, 0b10011, 0b10101, 0b10110, 0b11001, 0b11010, 0b11100

。

对于上述每个值，我还需要其按位反转，例如

0b11100, 0b11010, 0b10110, 0b01110, 0b11001, 0b10101, 0b01101, 0b10011, 0b01011, 0b00111

。目前，每次

reverse

生成值时，我都会调用单独的

bit_permutations

函数：

def reverse(v, bits):
    assert bits <= 16
    v = ((v >> 1) & 0x5555) | ((v & 0x5555) << 1);
    v = ((v >> 2) & 0x3333) | ((v & 0x3333) << 2);
    v = ((v >> 4) & 0x0F0F) | ((v & 0x0F0F) << 4);
    v = ((v >> 8) & 0x00FF) | ((v & 0x00FF) << 8);
    return v >> (16 - bits)

然而，这似乎效率低下。是否可以修改

bit_permutations

，使其直接生成每个排列及其逆排列，而不是使用单独的、效率较低的

reverse

函数？

Answer 1

是的，可以修改

bit_permutations

函数来直接生成每个排列及其按位反转。我们可以通过在迭代排列时为反转位维护一个单独的掩码来实现这一点。

def trailing_zeros(v):
    return (v & -v).bit_length() - 1

def bit_permutations_with_reverse(popcount, bits):
    if popcount < 0 or popcount > bits:
        pass
    elif popcount == 0:
        yield 0, 0
    elif popcount == bits:
        yield (1 << bits) - 1, (1 << bits) - 1
    else:
        v = (1 << popcount) - 1
        reversed_mask = 1 << (bits - 1)
        while v < (1 << bits):
            yield v, v ^ reversed_mask
            t = v | (v - 1)
            v = (t + 1) | (((~t & -~t) - 1) >> (trailing_zeros(v) + 1))

# Example usage
for perm, reversed_perm in bit_permutations_with_reverse(3, 5):
    print(f"Original: {bin(perm)}, Reversed: {bin(reversed_perm)}")