如何用Python实现高效查找符合整数B的所有整数A的算法

核心判定规则 #

符合要求的整数A需满足：(A & B) == B。这个位运算表达式直接定义了约束——B中所有为1的二进制位，A对应位置必须也是1，其余位可自由为0或1。

高效实现思路（适配极大整数） #

如果B的二进制中有大量0位，符合条件的A总数为2^k（k为B中0的位数），直接枚举所有结果会导致内存爆炸。因此最优方案是用生成器逐个生成结果，避免一次性占用大量内存。

经典位运算子集枚举法 #

这是效率最高的实现方式，利用位运算技巧遍历所有可自由设置的位的子集：

1. 计算B有效位范围内的可自由设置位掩码：mask = ((1 << B.bit_length()) - 1) ^ B，该掩码仅在B为0的位上为1。
2. 通过(sub_mask - 1) & mask快速生成mask的所有子掩码，每个子掩码与B按位或得到符合条件的A。

代码实现（生成器版）

def generate_valid_A(B):
    if B == 0:
        yield 0
        return
    bit_len = B.bit_length()
    free_bits_mask = ((1 << bit_len) - 1) ^ B
    current_submask = free_bits_mask
    while True:
        yield B | current_submask
        if current_submask == 0:
            break
        current_submask = (current_submask - 1) & free_bits_mask

代码说明

• 该算法时间复杂度为O(2^k)，但生成器模式下内存占用始终为常数，即使处理极大整数（比如B是数百位的大整数）也能稳定运行。
• Python的无限精度原生整数完美支持超大数值运算，无需额外处理溢出问题。

验证示例 #

当B=9（二进制1001）时：

• 可自由设置位掩码为0110（十进制6）
• 生成的子掩码依次为6、4、2、0
• 对应A为：15（1111）、13（1101）、11（1011）、9（1001）
  （注：严格来说9本身也符合条件，原示例可能遗漏了该结果）

性能优化关键点 #

• 优先使用生成器：避免预先生成所有结果，尤其当k（B中0的位数）很大时，能显著降低内存消耗。
• 全程用位运算：位运算是Python中效率最高的整数操作，远快于字符串解析或列表操作，适配极大整数场景。

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