对两个数字进行按位异或运算会得到这两个数字的和或差。

Question

当我对任意两个数字执行XOR操作时，结果将是它们的差的绝对值或者它们的和。

我在Google上搜索了很多相关的公式，但没有找到明显的公式或陈述。

例如：

10 XOR 2 = 1010 XOR 10 = 1000(8)
 1 XOR 2 =   01 XOR 10 =   11(3)

这对所有数字都成立吗？

- Anil Kumar K K

---

这个减法属性不适用于有符号的二进制补码整数 - 即 0x1111 (-1) ^ 0x0001 (1) = 0x1110 (-2)，而 |-1 - 1| = 2。 - CmdrMoozy

Answer 1

正如Dukelings的回答和CmdrMoozy的评论所显示的，这并不总是正确的。但就像您的帖子所显示的那样，它至少在某些情况下是正确的。因此，这里提供稍微详细的分析。

加法方面： 显然，如果（但不仅仅是）(x & y) == 0，那么(x ^ y) == x + y，因为：x + y = (x ^ y) + ((x & y) << 1) 这解释了3³²种情况（对于每个位位置，有三种选择会导致AND后为0），其中(x ^ y) == (x + y)。

然后是(x&y)!=0的情况。这些情况恰好是这些情况：(x & y) == 0x80000000，因为最高位的进位是唯一不影响任何东西的进位。

这增加了3³¹种情况（对于31个位位置，有三种选择，对于最高位只有一种选择）。

减法方面： 对于减法，有一个较少人知道的恒等式：x - y == (x ^ y) - ((~x & y) << 1)。

这与加法没有太大区别，分析几乎相同。这一次，如果（但不仅仅是）(~x & y) == 0，那么(x ^ y) == x - y。那么3³²种情况就不会改变：~不会改变案例数量。其中大部分情况与先前不同，但并非全部（考虑y = 0，那么x可以是任何东西）。

这里再次有3³¹种额外情况，来自于(~x & y) == 0x80000000。

两侧的情况： + 和 - 两边并不是不相交的。有时候，x ^ y = x + y = x - y。只有当 y = 0 或者 y = 0x80000000 时才会发生这种情况。如果 y = 0，那么 x 可以是任何值，因为对于所有的 x，(x & 0) == 0 并且 (~x & 0) == 0。如果 y = 0x80000000，那么 x 再次可以是任何值，因为 x & 0x80000000 和 ~x & 0x80000000 都可以计算出 0 或者 0x80000000，这两种情况都没问题。

这样就有 2³³ 种情况使得 x ^ y = x + y = x - y。

同时，还有 (3³² + 3³¹) * 2 - 2³³ 种情况使得 x ^ y 是 x + y 或者 x - y 或者二者皆是，其值为 4941378580336984 或者用十六进制表示为 118e285afb5158，这也是这个网站给出的答案。

这是很多的情况，但仅占总空间 2⁶⁴ 的大约 0.02679%。

- harold

Answer 2

不，这并不总是正确的。

6 = 110
3 =  11
   ----
XOR 101 = 5

SUM   9
DIFF  3

这并不算是完整的分析，但这是我所看到的：

对于您的第一个示例，最低有效位的1010与10的位相同，因此当进行异或运算时会得到差异。

对于您的第二个示例，所有相应位都不同，因此当进行异或运算时会得到总和。

为什么会出现这些属性应该很容易理解。

- Bernhard Barker

Answer 3

实际上，对于你的观察有一个有趣的答案，并且可以解释为什么你会在这么多数字中观察到这一点。
a + b和a ^ b之间存在关系。它由以下公式给出：

a + b = a^b + 2*(a & b)

因此，

a^b = a + b - 2*(a & b)

(其中^是按位异或，&是按位与)
请查看链接以了解上述关系的更多信息。因此，对于每个a和b，其中a & b = 0，您将得到a+b = a^b，这解释了求和部分。如果a & b不等于0，则解释了差异部分。希望它能澄清您的问题！ :D

- Shaswat Lenka

Answer 4

假设N是2的幂次方，即N=2的k次方，则有：

当0<=X

当N<=Y<2的k+1时，N XOR Y总是N与Y的差。

- 7575 mohan

---

你能否添加支持你的论点的示例？ - जलजनक