高效生成N位M置位值及其位反转值

def trailing_zeros(v):
    """
    计算给定整数v的尾随零的数量。
    例如：trailing_zeros(0b10100) 返回 2
    """
    if v == 0:
        return 0 # 或者根据需求返回None/错误，这里假设v非零
    return (v & -v).bit_length() - 1

def bit_permutations_original(popcount, bits):
    """
    生成所有N位中M个置位的二进制值。
    :param popcount: 置位（1）的数量 M
    :param bits: 总位数 N
    """
    if popcount < 0 or popcount > bits:
        # 无效输入，不生成任何值
        pass
    elif popcount == 0:
        # 0个置位，只有0
        yield 0
    elif popcount == bits:
        # 所有位都是1，只有 (1 << bits) - 1
        yield (1 << bits) - 1
    else:
        # 初始值：最低的popcount个位为1
        v = (1 << popcount) - 1
        while v < (1 << bits):
            yield v
            # Gosper's Hack: 计算下一个具有相同置位数的整数
            t = v | (v - 1)
            v = (t + 1) | (((~t & -~t) - 1) >> (trailing_zeros(v) + 1))

def reverse_fixed_bits(v, bits):
    """
    针对特定位数（例如 <= 16）进行优化的位反转函数。
    此方法通过多次位移和按位或操作实现。
    """
    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) # 调整到正确的位数

def trailing_zeros(v):
    """
    计算给定整数v的尾随零的数量。
    """
    if v == 0:
        return 0
    return (v & -v).bit_length() - 1

def bit_permutations_optimized(popcount, bits):
    """
    生成所有N位中M个置位的二进制值，并同时生成其位反转形式。
    :param popcount: 置位（1）的数量 M
    :param bits: 总位数 N
    """
    if popcount < 0 or popcount > bits:
        # 无效输入
        pass
    elif popcount == 0:
        # 0个置位，只有0，其反转也是0
        yield 0, 0
    elif popcount == bits:
        # 所有位都是1，其反转也是自身
        all_ones = (1 << bits) - 1
        yield all_ones, all_ones
    else:
        v = (1 << popcount) - 1
        while v < (1 << bits):
            # 核心优化：在生成原始值v的同时计算其位反转值
            # 1. 格式化为固定宽度的二进制字符串
            # 2. 反转字符串
            # 3. 将反转后的字符串转换回整数
            reverse_v = int(format(v, f'0{bits}b')[::-1], 2)
            yield v, reverse_v

            # Gosper's Hack: 计算下一个具有相同置位数的整数
            t = v | (v - 1)
            v = (t + 1) | (((~t & -~t) - 1) >> (trailing_zeros(v) + 1))

# 示例：生成5位中3个置位的二进制值及其位反转形式
popcount_example = 3
bits_example = 5

print(f"生成 {bits_example} 位中 {popcount_example} 个置位的二进制值及其位反转形式：")
for perm, reverse_perm in bit_permutations_optimized(popcount_example, bits_example):
    print(f"原始值: {format(perm, f'0{bits_example}b')} ({perm}), "
          f"反转值: {format(reverse_perm, f'0{bits_example}b')} ({reverse_perm})")

# 预期输出 (部分):
# 原始值: 00111 (7), 反转值: 11100 (28)
# 原始值: 01011 (11), 反转值: 11010 (26)
# ...