求满足表达式 (A|X)和(B|X)=C

Question

如何找到满足表达式(A|X(的X的最小值&对于给定的A，B，C，(B|X(=C。如果不存在这样的X，则返回-1

|位或运算符、&位和运算符

我不知道该如何处理这个问题。最简单的暴力方法是遍历每个X，并将其放入按预期超时的方程中。

然而，给定的布尔表达式可以简化为(A&B(|X=C。

由此，我可以很容易地计算出A&B并将其转换为二进制。我还将C转换为二进制。

我的方法：

1. 浏览A&B如果它是1并且C为0，返回-1，因为您不能将1与任何要返回0的内容进行OR运算
2. 否则，将C的位添加到X

我不知道这是否是最好的方法，甚至会导致最小值。它确实找到了一个解决表达式的X，但不确定它是否是最好的X。

def minXFinder(A,B,C):
bits = bin(A&B)[2:]
C_bits = bin(C)[2:]
bits='0'*(len(C_bits)-len(bits))+bits
C_bits='0'*(len(bits)-len(C_bits))+C_bits
X = ''
for i in range(len(bits)):
if bits[i] == '1' and C_bits[i] == '0':
return -1
else:
X+=C_bits[i]
X=int(X,2)
return X,(A|X)&(B|X)==C

Answer 1

给定A,B,C，我们想找到最小的非负整数X，使得(A|X)&(B|X) = C。如前所述，这可以重写为(A&B)|X = C。

让我们首先考虑暴力手段。注意，如果存在X，则该值不应大于C。这是因为，如果X > C，则存在至少一个比特，其中X具有1并且C具有0。该比特在(A&B)|X中也将是1，这与相等条件相矛盾。因此，我们只需要从零到C搜索X就可以找到解决方案。

def f1(A,B,C):
# brute force
AandB = A&B
for X in range(C+1):
if AandB|X == C:
return X
return -1

为了寻求更有效的方法，请考虑我们需要具有平等要求的逐位关系。

• 如果A&B和C中的一个比特都是1，那么X不会影响结果(左手边无论如何都是1(。由于我们想要最小化X，因此在这种情况下我们想要0
• 如果A&B=1和C=0，那么对于任何X，左手边都将是1，因此我们不能满足等式条件
• 如果A&B=0和C=1，那么我们需要有X=1来满足等式
• 如果A&B=0和C=0，那么我们需要有X=0来满足等式

总结如下。

-

A&B	C	X
1	1	0
1	0
0	1	1
0	0	0