这个方程x+y=x&y+xy如何成立（假设x，y>0)？

Question

我最近参加了一个代码部队的比赛。 在竞赛的编辑部分，我看到了位运算符之间的一个漂亮的关系，即x+y=x&； y+xy。 我还不知道证据。 我取了几个数字，看看这个方程式是不是真的。 我很兴奋知道证据。 我上网查了一下，找不到任何有意义的参考资料。 请帮我找到证明，或者至少给我这个美丽方程式背后的直觉。 提前致谢

Answer 1

对于x和y，您可以拆分位，将它们相加，并得到相同的答案，对吗？
示例:

0101 (x) + 0110 (y) == (0100 + 0001) + (0100 + 0010)

现在。 查看逻辑运算符:
a&； b给出两个数字中的位（读:计数2）
a b给出两个数字中的位（读:计数≥1)

所以基本上，你取两个数字中的位，把它们相加:

0111 == 0100 (in x, y) + 0010 (in y) + 0001 (in x)

您还需要取两个数字中的位（即需要计数两次的位），并将其加到和:

0100 == 0100 (in x, y)

因此，您最终将出现一次，一次的位和出现两次，两次的位相加:

0111 (bits that appear once or twice) + 0100 (bits that appear twice)

Answer 2

所以，当你试图计算出按位计算时，最简单的方法就是为所有情况制作一个图表，特别是当变量很少的时候。

 A | B | A AND B | A OR B |     A + B     | (A AND B) + (A OR B)
---+---+---------+--------+---------------+----------------------
 0 | 0 |    0    |    0   |   0 + 0 = 0   |     0 + 0 = 0
---+---+---------+--------+---------------+----------------------
 0 | 1 |    0    |    1   |   0 + 1 = 1   |     0 + 1 = 1
---+---+---------+--------+---------------+----------------------
 1 | 0 |    0    |    1   |   1 + 0 = 1   |     0 + 1 = 1
---+---+---------+--------+---------------+----------------------
 1 | 1 |    1    |    1   |   1 + 1 = 2   |     1 + 1 = 2

现在您可能可以看到:

• 如果a==b，则a+b和a&； B+AB本质上是相同的。
• 如果a！=b，则a&； B+A B可能会改变两个值的顺序，但当然，A+B=B+A，因此它们本质上与while相同。

Answer 3

假设您正在执行A+B。

请注意，将a的第i位数字（从最右边的数字开始计算）与b的第i位数字交换不会影响和。 示例:123+456==156+423。 无论基的选择如何，这都是有效的，因此它也适用于二进制加法。

接下来，请注意，从a+b到a&b+ab的转换可以通过以上述方式（二进制）交换一些数字来完成。 如果a[i]==1和b[i]==0，则交换a[i]和b[i]； 之后，a变成a&b，b变成ab。 因此，这种转换并不影响结果。