求解位方程

Solving Bitwise Equation

我有一个

形式的按位方程

X = (A & X) + (B & X)

其中 A and B 是已知整数，X 是未知整数，如何找到 X？ 这里，&是按位与，+是算术加法，A、B、X是整数。

一个简单的解决方案是零，但我必须 return 如果没有其他解决方案是可能的。

我的方法：我知道 X 的范围，所以我可以在 O(n) 中对其进行迭代以检查条件，但范围可能非常大，因此可能效率不高。

此外，我尝试对两边进行 AND 运算以缩短等式，但无法得出有意义的解。

让我们首先关注 X 的最后一位。它可以是 0 或 1，并且根据 A 和 B 的结构，我们可以排除某些选项。 A 和 B 的最后一位有四种组合，但由于对称性，实际上只有三种情况需要考虑：

  • 情况 1：A 和 B 以零结尾。在这种情况下，A & X 以 0 结尾，B & X 以 0 结尾。因此，由于 X = A & X + B & X，[=15 的最后一位=] 必须为 0。
  • 情况2：A和B其中一个以1结尾，另一个以0结尾。不失一般性，假设A以1结尾，B以0结尾。则A & X + B & X = 0 + X = X，因此 X 的最后一位的任一种选择都有效。
  • 情况3：A和B都以1结束。那么，A & X以X的最后一位结束，B & X以X的最后一位结束。那么X 由 A & X + B & X = X + X = 2X = 0 给出，因为将任意位乘以 2 并查看最低的结果位给出 0.

换句话说，在每种情况下，对于 A 和 B 位的组合，我们可以通过查阅 [=69] 来确定 X 可能的位=] 然后向右移动一个位置来处理下一位。 table，具体显示在这里

 A | B | X
---+---+---
 0 | 0 | 0
 0 | 1 | any
 1 | 0 | any
 1 | 1 | 0

请注意，这符合您的直觉，即零始终是一个解决方案，因为这些规则允许您为您想要的任何位选择 0。但是如果你想找到一个不是到处都是0的解决方案，只要有选择就填1。

举个例子，假设二进制的A是011101001，二进制的B是001101010。然后，使用这个 table，我们有这些选项：

    A 011101001
    B 001101010
    X 0*00000*0

这给出了四种可能性：

010000010
010000000
000000010
000000000

而且我们可以检查，确实，每一个都是 X = A & X + B & X.

的解

这个解决方案的运行时间为 O(b)，其中 b 是数字 A 和 B 中的位数。那就是 O(log A + log B)，如果给定 A 和 B 的数字，意味着这 方式 比暴力搜索快。

希望对您有所帮助！