求解按位方程

Question

我有一个形式的按位方程

X =（A＆X）+（B＆X）

其中A和B是已知整数，X是未知整数，如何找到X？在这里，＆是按位AND，+是算术加法，A，B和X是整数。

平凡的解决方案之一是零，但如果没有其他解决方案，我必须退还。

我的方法：我知道X的范围，所以我可以在O（n）中对其进行迭代以检查条件，但范围可能很大，因此可能无效。

此外，我尝试在两边都进行与运算以缩短方程式，但无法得出有意义的解决方案。

Answer 1

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

• 情况1：A和B以零结尾。在这种情况下，A & X以0结尾，B & X以0结尾。因此，由于X =A & X+ B & X，X的最后一位必须为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位的组合，我们可以通过查询表来确定X可以使用的位，然后向右移动一个位置以处理下一位。具体来说，该表显示在这里

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

注意，这符合您的直觉，即零永远是一个解决方案，因为这些规则允许您为想要的任何位选择0。但是，如果您想找到一个到处都不为0的解决方案，则可以随时选择1。

作为示例，假设二进制中的A为011101001，二进制中的B为001101010。然后，使用此表，我们有以下选项：

    A 011101001
    B 001101010
    X 0*00000*0

这提供了四种可能性：

010000010
010000000
000000010
000000000

并且我们可以检查一下，实际上，每个都是对X =A & X+ B & X的解决方案。

此解决方案在时间O（b）中运行，其中b是数字A和B中的位数。如果您给以数字A和B，则为O（log A + log B），这意味着way比蛮力搜索要快。

希望这会有所帮助！