按位XOR（异或）是什么意思？

我试图理解二进制运算符在C＃或一般，特别是^ – 排他或。

例如：

给定一组正整数。所有的数字偶数次出现，除了一个奇数次的数字。在O（n）时间和恒定的空间find数字。

这可以用^完成，如下所示：对所有元素进行按位异或操作。最后我们得到奇数的数字。

它是如何工作的？

当我做：

int res = 2 ^ 3; res = 1; int res = 2 ^ 5; res = 7; int res = 2 ^ 10; res = 8;

实际上发生了什么？什么是其他的魔法？任何参考我可以查阅和了解更多关于他们？

要看看它是如何工作的，首先你需要用二进制编写这两个操作数，因为按位操作在个别位上工作。

然后，您可以为您的特定运营商应用真值表。它作用于两个操作数中相同位置的每一对位（相同的位置值）。所以A的最左位（MSB）与B的MSB组合以产生结果的MSB。

例如： 2^10 ：

  0010 2 XOR 1010 8 + 2 ---- 1 xor(0, 1) 0 xor(0, 0) 0 xor(1, 1) 0 xor(0, 0) ---- = 1000 8

结果是8。

我知道这是一个相当古老的post，但是我想简化答案，因为我在寻找别的东西的时候偶然发现了它。
异或（eXclusive OR / or或），可以简单地翻译为开/关。
这将排除或包含指定的位。

使用4位（1111）我们从0-15得到16个可能的结果：

  0: 0000 1: 0001 2: 0010 3: 0011 (1+2) 4: 0100 5: 0101 (1+4) 6: 0110 (2+4) 7: 0111 (1+2+4) 8: 1000 9: 1001 (1+8) 10: 1010 (2+8) 11: 1011 (1+2+8) 12: 1100 (4+8) 13: 1101 (1+4+8) 14: 1110 (2+4+8) 15: 1111 (1+2+4+8)

至于XOR背后的逻辑是什么，这里有一些例子
从原来的post

2 ^ 3 = 1

2是1 + 2 （3）移除2 = 1的成员

2 ^ 5 = 7

2不是1 + 4的成员（5）加2 = 1 + 2 + 4 （7）

2 ^ 10 = 8

2是2 + 8 （10）移除2 = 8的成员

更多的例子

1 ^ 3 = 2

1是1 + 2 （3）删除1 = 2的成员

4 ^ 5 = 1

4是1 + 4 （5）删除4 = 1的成员

4 ^ 4 = 0

4是自己删除4 = 0的成员

1 ^ 2 ^ 3 = 0
逻辑：（（1 ^ 2）^（1 + 2））

（1 ^ 2）1不是2的成员加2 = 1 + 2 （3）

（3 ^ 3）1和2是1 + 2 （3）的成员删除1 + 2 （3） = 0

1 ^ 1 ^ 0 ^ 1 = 1
逻辑：（（（1 ^ 1）^ 0）^ 1）

（1 ^ 1）1是1的成员删除1 = 0

（0 ^ 0）0是0的成员删除0 = 0

（0 ^ 1）0不是1的成员加1 = 1

1 ^ 8 ^ 4 = 13
逻辑：（（1 ^ 8）^ 4）

（1 ^ 8）1不是8的成员add 1 = 1 + 8 （9）

（9 ^ 4）1和8不是4的成员加1 + 8 = 1 + 4 + 8 （13）

4 ^ 13 ^ 10 = 3
逻辑：（（4 ^（1 + 4 + 8））^（2 + 8））

（4 ^ 13）4是1 + 4 + 8 （13）的成员删除4 = 1 + 8 （9）

（9 ^ 10）8是2 + 8 （10）去掉8 = 2的成员

1不是2 +8 （10）的成员add 1 = 1 + 2 （3）

4 ^ 10 ^ 13 = 3
逻辑：（（4 ^（2 + 8））^（1 + 4 + 8））

（4 ^ 10）4不是2 + 8的成员（10）加4 = 2 + 4 + 8 （14）

（14 ^ 13）4和8是1 + 4 + 8 （13）的成员删除4 + 8 = 1

2不是1 ~~+ 4 + 8~~的成员（13）加2 = 1 + 2 （3）

另一种显示方式是使用XOR的代数; 你不需要知道任何关于个人位。

对于任何数字x，y，z：

XOR是可交换的： x ^ y == y ^ x

XOR是关联的： x ^ (y ^ z) == (x ^ y) ^ z

身份是0： x ^ 0 == x

每个元素都是它自己的逆元素： x ^ x == 0

鉴于此，certificate结果很容易。考虑一个序列：

a ^ b ^ c ^ d ...

由于XOR是可交换和关联的，所以顺序无关紧要。所以sorting元素。

现在任何相邻的相同元素x ^ x可以用0 （自反特性）replace。任何0都可以被删除（因为它是身份）。

重复尽可能长的时间。任何出现偶数次的数都有一个整数对，所以它们全部变为0并消失。

最终你只剩下一个出现奇数次的元素。每次出现两次，那两个就消失了。最终你只剩下一次。

[更新]

请注意，这个certificate只需要对操作进行一定的假设。具体来说，假设有一个操作符集合S. 具有以下属性：

缔造力： x . (y . z) = (x . y) . z x . (y . z) = (x . y) . z x . (y . z) = (x . y) . z对于S中的任何x ， y和z

身份：存在一个单一的元素， e . x = x . e = x e . x = x . e = x 对于S中的所有x ， e . x = x . e = x

closures：对于S中的任何x和y ， x . y x . y也在S.

自反：对于S中的任何x ， x . x = e x . x = e

事实certificate，我们不需要假设交换性。我们可以certificate这一点：

 (x . y) . (x . y) = e (by self-inverse) x . (y . x) . y = e (by associativity) x . x . (y . x) . y . y = x . e . y (multiply both sides by x on the left and y on the right) y . x = x . y (because x . x = y . y = e and the e's go away)

现在我说“你不需要知道个别的东西”。我在想，任何满足这些性质的群体都是足够的，而这样的群体并不一定与XOR下的整数是同构的。

但@Steve Jessup在评论中certificate我错了。如果你用{0,1}定义标量乘：

 0 * x = 0 1 * x = x

…那么这个结构满足整数mod 2 上的向量空间的所有公理。

因此，任何这样的结构在分量XOR下同构于一组位向量。

按位运算符将整数值内的位视为微小的位数组 。每一个位都像一个微小的bool值 。当你使用按位异或运算符时，对运算符的一个解释是：

对于第一个值中的每个位，如果第二个值中的对应位被置位，则切换该位

最终的结果是，一个单独的位开始是false ，如果“切换”的总数是偶数，那么它最终仍然是false的。如果“切换”的总数是奇数，最后是true 。

只要想一想“一小堆布尔值”，它就会开始有意义。

XOR（异或）运算符在位上的定义是：

 0 XOR 0 = 0 0 XOR 1 = 1 1 XOR 0 = 1 1 XOR 1 = 0

其中一种想象的方式是，右侧的“1”从左侧改变位，而右侧的0不改变左侧的位。然而，XOR是可交换的，所以如果双方相反，情况也是如此。由于任何数字都可以以二进制forms表示，所以任何两个数字都可以异或。

为了certificate它是可交换的，你可以简单地看一下它的定义，并且看到对于每一边的每个位的组合，如果边被改变，结果是相同的。为了certificate它是联想的，你可以简单地遍历所有可能的3位被异或的组合，不pipe顺序如何，结果都是一样的。

现在，正如我们在上面certificate的那样，让我们看看如果我们在自己XOR相同的数字会发生什么。由于该操作对个别位有效，因此我们可以在两个数字上进行testing：0和1。

 0 XOR 0 = 0 1 XOR 1 = 0

所以，如果你把一个数字XOR到自己，你总是得到0（信不信由你，但是XOR的属性已经被编译器使用，当一个0需要被加载到一个CPU寄存器中时。而不是明确地将0推入寄存器，编译器只会产生汇编代码来将寄存器异或）。

现在，如果X XOR X为0，并且XOR是关联的，那么您需要找出在所有其他数字重复两次（或任何其他奇数次）的数字序列中未重复的数字。如果我们把重复的数字放在一起，它们将异或为0，任何与0异或的东西都将保留。所以，从XOR这样一个序列中，你最终会留下一个不重复的数字（或重复偶数次）。

这有很多样本的各种function完成的位摆弄。有些可能相当复杂，所以要小心。

你需要做什么来理解位操作，至less是这样的：

input数据，以二进制forms
一个真值表，告诉你如何“混合”input来形成结果

对于XOR，真值表很简单：

 1^1 = 0 1^0 = 1 0^1 = 1 0^0 = 0

要获得结果中的第n位，将规则应用于第一个和第二个input中的第n位。

如果您尝试计算1^1^0^1或任何其他组合，您会发现如果存在1的奇数，结果为1，否则为0。你也会发现，与它自己异或的任何数字都是0，那么按照你的计算顺序是没有关系的，例如1^1^(0^1) = 1^(1^0)^1 。

这意味着当你对列表中的所有数字进行异或时，那些重复（或偶数次）的数字将异或为0，并且只剩下一个出现奇数次的数。

可以使用按位“异或”来交换2个数字

 x = x^y; y = x^y; x = x^y;

如果你两次XOR一个数字，它将被取消出来，唯一剩下的就是在你的情况下迭代结束时的和数。

这就是algorithm的工作原理。