给定A、B，如何求满足X≥Y、X&Y=A且X|Y=B的X、Y？

Question

给定两个整数A和B，如何高效求解满足条件X≥Y、X & Y = A 且 X | Y = B 的所有整数对(X, Y)？该问题常见于位运算构造类算法题中。核心难点在于理解按位与（&）和按位或（|）之间的关系：由位运算恒等式可知，X + Y = (X | Y) + (X & Y) = A + B，但这仅在无进位时近似成立。更准确的方法是逐位分析：对于每一位，若A和B在该位的值矛盾（如A该位为1但B为0），则无解；否则可确定X和Y在该位的可能取值组合。最终还需保证X≥Y。问题是：如何设计一个时间复杂度为O(1)或O(log B)的算法，正确构造出所有合法解或判断无解？

Answer 1

一、问题背景与核心洞察

在算法竞赛和系统设计中，位运算构造类问题是考察工程师对二进制表示本质理解的重要题型。给定两个整数 A 和 B，目标是求解所有满足以下条件的整数对 (X, Y)：

• X ≥ Y
• X & Y = A （按位与）
• X | Y = B （按位或）

这类问题的关键在于深入理解位运算之间的内在关系。一个重要的恒等式为：

X + Y = (X | Y) + (X & Y)

该式在无进位加法下成立，但不能直接用于构造解。更有效的方法是逐位分析每一位上 X 和 Y 的可能取值组合。

二、位级约束分析

B_i	A_i	X_i	Y_i	说明
0	0	0	0	唯一可能：两者均为0
0	1	-	-	矛盾！A_i=1要求都为1，但B_i=0不允许任何为1 → 无解
1	0	1,0 或 0,1	可变	一个为1，另一个为0
1	1	1	1	必须都为1

从表中可见，若存在某一位 i 满足 A_i > B_i（即 A 在该位为1而 B 为0），则无合法解。这是判断无解的第一道门槛。

三、构造可行解空间

设 C = B - A。注意：只有当 B 包含 A 的所有置位位时（即 (A | B) == B 且 A & (~B) == 0），C 才是非负整数且具有意义。

进一步观察发现，对于每一位 i：

• 若 A_i = 1，则 X_i = Y_i = 1
• 若 B_i = 1 且 A_i = 0，则 X_i 和 Y_i 中恰好有一个为1
• 其余位均为0

令 D = B ^ A（异或），D 的每一位表示“可自由分配”的位——即在此位上 X 和 Y 可以不同。

于是，我们可以将这些自由位分配给 X 或 Y，从而生成所有候选解对。

四、枚举策略与复杂度优化

设自由位数量为 k = popcount(D)，则最多有 2^k 组候选解。但由于要求 X ≥ Y，我们需剪枝处理。

关键技巧：定义 Z = X - A，W = Y - A。由于 X & Y = A，可推得 Z & W = 0 且 Z | W = D。因此 Z 是 D 的子集，W = D ^ Z。

于是：

X = A | Z
Y = A | (D ^ Z)

其中 Z 遍历 D 的所有子集。然后筛选出满足 X ≥ Y 的解即可。

五、高效算法实现

1. 检查合法性：if ((A & ~B) != 0) return [];
2. 计算 D = B ^ A
3. 遍历 D 的所有子集 Z：
4.   X = A | Z
5.   Y = A | (D ^ Z)
6.   if (X >= Y) 收集 (X, Y)
7. 返回结果列表

时间复杂度为 O(2^{popcount(B^A)})，最坏情况为 O(B)，但在稀疏位情况下接近 O(log B)。

六、代码示例（Python）

def solve_xy_pairs(A, B):
    if A & ~B:
        return []
    D = B ^ A
    results = []
    # 遍历 D 的所有子集
    Z = 0
    while True:
        X = A | Z
        Y = A | (D ^ Z)
        if X >= Y:
            results.append((X, Y))
        if Z == D:
            break
        Z = (Z - D) & D  # 下一个子集
    return results

该实现利用位运算高效枚举子集，避免递归开销。

七、流程图展示逻辑分支

graph TD A[开始] --> B{A & ~B ≠ 0?} B -- 是 --> C[无解] B -- 否 --> D[D = B ^ A] D --> E[Z = 0] E --> F[X = A|Z, Y=A|(D^Z)] F --> G{X ≥ Y?} G -- 是 --> H[添加(X,Y)] G -- 否 --> I[跳过] H --> I I --> J{Z == D?} J -- 否 --> K[Z = (Z-D)&D] K --> F J -- 是 --> L[返回结果]

此流程清晰展示了从输入到输出的完整控制流。

八、边界案例与测试数据

#	A	B	输出	说明
1	2	3	(3,2)	标准单自由位
2	1	1	(1,1)	仅全同解
3	4	6	(6,4),(5,5)?	验证：5&5=5≠4 → 实际仅(6,4)
4	0	0	(0,0)	零解
5	8	7	[]	A & ~B ≠ 0 → 无解
6	3	7	(7,3),(6,4),(5,5)	多解情况
7	0	1	(1,0),(0,1)但只保留(1,0)	X≥Y过滤
8	12	15	多个组合	D=3, 子集枚举
9	5	5	(5,5)	完全重合
10	6	10	[]	6 & ~10 = 6 & 5 = 4 ≠ 0 → 无解

通过覆盖各种位模式，确保算法鲁棒性。