Python如何对bitset整数使用itertools.combinations且无需转换为集合

实现思路 #

核心是避免不必要的集合转换与求和操作，直接通过位运算生成符合要求的整数，共两种实现方案可选：

• 低改造成本的优化版：保留itertools.combinations依赖，仅优化置位提取和结果生成逻辑
• 高性能无额外依赖版：基于经典位运算算法Gosper's Hack适配，完全不需要存储置位集合

方案1：优化的置位组合版 #

该版本改动最小，仅通过位运算提取置位掩码、用位或替代求和，即可大幅降低原有实现的开销：

import itertools

def combos(bitset, k):
    # 提取所有置位的掩码，无需遍历所有位，仅遍历置位的位置
    bits = []
    b = bitset
    while b:
        lowbit = b & -b # 提取最低位的1
        bits.append(lowbit)
        b ^= lowbit # 移除已提取的最低位1
    if len(bits) < k:
        return
    # 直接位或拼接结果，比整数求和效率更高
    for s in itertools.combinations(bits, k):
        res = 0
        for num in s:
            res |= num
        yield res

方案2：无组合库依赖的高性能版（Gosper's Hack适配） #

该版本完全不需要调用itertools，也不需要额外存储置位列表，直接通过位操作生成所有符合条件的组合，在置位数量较多时性能优势更明显：

def combos(bitset, k):
    # 校验原bitset是否有足够的置位
    # Python<3.10可替换为 bin(bitset).count('1')
    if bitset.bit_count() < k:
        return
    # 初始化第一个组合：最低k位全为1的整数
    sub = (1 << k) - 1
    limit = 1 << bitset.bit_length()
    while sub < limit:
        # 仅返回所有置位都落在原bitset范围内的组合
        if (sub & bitset) == sub:
            yield sub
        # Gosper's Hack逻辑：生成下一个恰好有k个置位的整数
        c = sub & -sub
        r = sub + c
        sub = (((r ^ sub) >> 2) // c) | r

效果验证 #

输入bitset=0b01011（十进制11）、k=2，两个函数的输出均为{0b01010, 0b01001, 0b00011}，与示例要求一致。

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