如何修改位排列生成函数，高效输出N位M置位值及其位反转值？

我用以下Python代码生成总bits位中包含popcount个置位的所有值：

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(3, 5)会生成0b00111, 0b01011, 0b01101, 0b01110, 0b10011, 0b10101, 0b10110, 0b11001, 0b11010, 0b11100。

现在我需要每个生成值的位反转结果，比如对应上面的序列，反转后是0b11100, 0b11010, 0b10110, 0b01110, 0b11001, 0b10101, 0b01101, 0b10011, 0b01011, 0b00111。目前我是在每次生成值后调用单独的reverse函数：

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函数？

当然可以通过调整生成逻辑，直接输出原数值和其位反转值，核心是减少额外函数调用开销，或者利用位排列的对称性优化。以下是两种可行方案：

方案一：内嵌反转计算，同步输出 #

直接把位反转的逻辑整合到生成循环中，避免单独调用reverse函数的开销，同时保持原生成顺序不变：

def bit_permutations_with_reverse(popcount, bits):
    if popcount < 0 or popcount > bits:
        return
    elif popcount == 0:
        yield (0, 0)
    elif popcount == bits:
        full_mask = (1 << bits) - 1
        yield (full_mask, full_mask)
    else:
        v = (1 << popcount) - 1
        # 预定义反转用的掩码和位移量，避免重复创建
        mask_list = (0x5555, 0x3333, 0x0F0F, 0x00FF)
        shift_list = (1, 2, 4, 8)
        while v < (1 << bits):
            # 内嵌位反转计算
            rv = v
            for mask, shift in zip(mask_list, shift_list):
                rv = ((rv >> shift) & mask) | ((rv & mask) << shift)
            rv = rv >> (16 - bits)
            # 同时输出原数值和反转值
            yield (v, rv)
            # 生成下一个排列的逻辑不变
            t = v | (v - 1)
            v = (t + 1) | (((~t & -~t) - 1) >> ((v & -v).bit_length()))

方案二：利用对称性，生成反转对 #

观察位排列的特性：数值v的反转值rv置位数量和v完全相同，且除了对称数值（如4位的0b1010反转后仍是自身），其他数值都是成对出现的。我们可以利用这一点减少遍历次数：

def bit_permutations_with_reverse_pair(popcount, bits):
    if popcount < 0 or popcount > bits:
        return
    elif popcount == 0 or popcount == bits:
        val = 0 if popcount == 0 else (1 << bits) - 1
        yield (val, val)
        return
    # 记录已处理的数值，避免重复输出
    processed = set()
    v = (1 << popcount) - 1
    while v < (1 << bits):
        if v not in processed:
            # 计算反转值
            rv = v
            rv = ((rv >> 1) & 0x5555) | ((rv & 0x5555) << 1)
            rv = ((rv >> 2) & 0x3333) | ((rv & 0x3333) << 2)
            rv = ((rv >> 4) & 0x0F0F) | ((rv & 0x0F0F) << 4)
            rv = ((rv >> 8) & 0x00FF) | ((rv & 0x00FF) << 8)
            rv = rv >> (16 - bits)
            processed.add(v)
            processed.add(rv)
            yield (v, rv)
            # 非对称数值额外输出反转对
            if v != rv:
                yield (rv, v)
        # 生成下一个排列
        t = v | (v - 1)
        v = (t + 1) | (((~t & -~t) - 1) >> ((v & -v).bit_length()))

方案对比 #

• 方案一逻辑简单，和原生成流程几乎一致，适合需要严格保持原排列顺序的场景，仅通过内嵌计算减少函数调用开销。
• 方案二利用对称性减少近一半的遍历次数（无对称数值时），性能更优，但需要额外集合记录已处理数值，适合对性能要求较高的场景。

内容的提问来源于stack exchange，提问作者user200783