有没有可能用给定的 B 和 C 在 "A & B = C" 中恢复 A？

Question

请问：A、B、C都是任意二进制数。在获得 C = A & B 之后（& 是 AND 运算符），是否有可能从 B 和 C 中恢复 A？

我知道A的信息会通过操作丢失。我们可以构造一个像 B <...> C = A 这样的函数吗？它有多复杂？

例如：

A = 0011
B = 1010
C = A & B = 0010

C的第2位是1，即A和B的第2位必须是1。但是，其他位缺少需要恢复的信息。

提前谢谢你。

Answer 1

不，这不可能。你可以从真相中看出这一点 table for AND:

A  B  C (A & B)

0  0  0
0  1  0
1  0  0
1  1  1

假设你知道B是0，C是0。A可以是1也可以是0，所以不能从B和C推导出来。

Answer 2

您只能恢复在 B 的相应位中具有 1 的 A 位。对于 B 中有零的位，A 在相应位置有什么并不重要，因为 C 中的位无论如何都会为零：

A = 1xx0x011x0
B = 1001011101
    ----------
C = 1000001100

A中标有x的位置可以是0也可以是1；无论哪种方式，它们中的信息都会丢失。

Answer 3

假设您只是在谈论二进制逻辑而不是 C 变量，那么不会。

考虑： a=0111, b=1010 因此 c=0010

所以你有 b=1010, c=0010 那么现在你怎么能找到 a？

最左边的位在c中是0，在b中是1所以我们知道a它一定是0 c 中的第二位是 0，在 b 中它是 0 所以你无法分辨它在 a 中是什么（1 或 0 导致 [=14= 中的 0 ])

此时我们已经证明你做不到。

Answer 4

不，因为没有唯一的解决方案。无论其他位如何，具有与 B 相同位设置的 A 的任何值都将满足等式。

Answer 5

无法恢复A，但可以写入A = (X & ~B) ^ C。在这里，X 可以是任何东西（它给出了所有 A）。

当然这只适用于 B 和 C 这样 C & ~B == 0.

这是一个参数化的解决方案。 python

中的示例

>>> A = 32776466
>>> B = 89773888
>>> C = A & B
>>> C
22020352
>>> X = 1234567890    # arbitrary value
>>> U = (X & ~B) ^ C
>>> U
1238761874
>>> U & B     # same result as A & B
22020352

Answer 6

这是一道关于方程式的问题。这是不可能的，因为自由度不为零。这与询问 a+b = 10 相同——a 是什么，b 是什么？

有没有可能用给定的 B 和 C 在 "A & B = C" 中恢复 A？

Is there any possibility to recover A in "A & B = C" with given B and C?

c

algorithm

logic

circuit