如何用Python找出满足按位或结果的所有a1、a2二进制状态（a1<a2）

思路分析 #

要找出所有满足a1 | a2 = target且a1 < a2的二进制数对，核心逻辑如下：

1. a1必须是target的子集（即a1的所有二进制位都在target中存在，否则a1 | a2必然超出target）。
2. 对于每个合法的a1，a2必须包含target中a1缺失的所有位（保证或运算结果等于target），同时可以包含a1已有的任意位。
3. 筛选出a2 > a1的组合，转换为指定长度的二进制字符串即可。

Python实现代码 #

def find_valid_pairs(target, bit_length=None):
    # 处理输入的target：支持二进制字符串或整数
    if isinstance(target, str):
        bit_length = len(target)
        target = int(target, 2)
    else:
        # 若未指定位数，自动取target的二进制位数（0的情况默认1位）
        if bit_length is None:
            bit_length = target.bit_length() if target != 0 else 1
    
    valid_pairs = []
    a1 = 0
    while a1 <= target:
        # 跳过不是target子集的a1
        if (a1 | target) != target:
            a1 += 1
            continue
        
        # 计算a2必须包含的位：target中a1缺失的部分
        required_bits = target ^ a1
        # 遍历a1的所有子集，生成合法的a2
        s = 0
        while True:
            a2 = required_bits | s
            if a2 > a1:
                # 转换为指定长度的二进制字符串，补前导零
                a1_bin = format(a1, f'0{bit_length}b')
                a2_bin = format(a2, f'0{bit_length}b')
                valid_pairs.append((a1_bin, a2_bin))
            # 遍历完所有子集后退出
            if s == a1:
                break
            # 生成a1的下一个子集（高效遍历子集的技巧）
            s = (s - a1) & a1
        
        a1 += 1
    
    return valid_pairs

测试示例 #

以题目中的target = '0011'为例：

result = find_valid_pairs('0011')
print(result)
# 输出：[('0000', '0011'), ('0001', '0010'), ('0001', '0011'), ('0010', '0011')]

注：题目示例中遗漏了('0010', '0011')这个合法组合，该组合满足0010 | 0011 = 0011且0010 < 0011。

扩展说明 #

• 支持任意位数的二进制数：若输入为整数，可通过bit_length参数指定输出二进制字符串的长度；若未指定，自动取target的二进制位数。
• 高效遍历子集：使用s = (s - a1) & a1的技巧快速生成a1的所有子集，避免了低效的全量枚举。

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