如何找到满足(A|X)&(B|X)=C的最小X值？无解返回-1

AI 小北

2026-8-17

求解满足(A|X)&(B|X)=C的最小X值

给定三个整数A、B、C，需找到满足表达式(A|X)&(B|X)=C的最小非负整数X；若不存在符合条件的X，返回-1。其中|为按位或运算符，&为按位与运算符。

表达式化简

先对原表达式做布尔化简：
(A|X)&(B|X) 等价于 (A&B)|X，按二进制位逐一验证：

当X的某一位为0时：(a|0)&(b|0) = a&b = (a&b)|0
当X的某一位为1时：(a|1)&(b|1) = 1 = (a&b)|1
因此原问题可转化为求解满足(A&B)|X = C的最小X。

存在性判断与最小X推导

存在性判断

对于A&B的每一位：

若该位为1，那么(A&B)|X的对应位必然为1，因此如果C的对应位为0，则不存在符合条件的X，直接返回-1。

最小X的构造规则

要得到最小的X，需让X的二进制中1的数量尽可能少、高位尽可能为0，具体每一位取值规则：

若A&B的某一位为1：
- 此时C的对应位必为1（否则已判定无解），X的该位取0（0比1更小，且不影响等式成立）
若A&B的某一位为0：
- 此时(A&B)|X的对应位等于X的对应位，因此X的该位必须等于C的对应位，才能满足等式。

修正后的代码

def minXFinder(A, B, C):
    ab = A & B
    # 判断是否存在解：若ab某一位为1但C对应位为0，直接返回-1
    if (ab & (~C)) != 0:
        return -1
    # 构造最小X：ab为1的位取0，ab为0的位取C对应位
    X = C & (~ab)
    return X

# 验证示例
print(minXFinder(3, 3, 3))  # 输出0，(3|0)&(3|0)=3，符合条件且X最小
print(minXFinder(1, 2, 3))  # 输出3，此时A&B=0，X必须等于C才能满足等式
print(minXFinder(3, 5, 4))  # 输出-1，A&B最低位为1但C最低位为0，无解