按位异或(独占或)是什么意思？

我试图理解 C # 或一般情况下的二进制运算符，特别是 ^-独家或。

例如:

给定一个正整数数组。所有数字出现偶数次，除了一个数字出现奇数次。求 O (n)时间和常数空间中的数。

这可以通过 ^ 来完成，如下所示: 对所有元素执行按位异或操作。最后得到出现奇数的数字。

它是怎么工作的？

当我这样做:

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

实际上发生了什么? 还有什么其他的魔法? 有什么参考资料我可以查阅并了解更多关于它们的信息吗？

96041 次浏览
小开
最佳答案

要了解它是如何工作的，首先需要用二进制写入两个操作数，因为按位操作对单个位进行操作。

然后您可以为您的特定操作符应用 真相表。它作用于两个操作数中位置相同的每一对位(相同的位值)。因此，将 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。

小开

位运算符将整数值中的位视为 微小的比特阵列。每一个都像是 极小的 bool值。当您使用按位排它或运算符时，对运算符的一种解释是:

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

最终的结果是，一个位开始于 false，如果“切换”的总数是偶数，那么在结束时它仍然是 false。如果“切换”的总数是奇数，那么结尾处将是 true。

只要想一想“布尔值的小数组”，就会开始有意义了。

小开

另一种表示方法是使用 XOR 的代数; 您不需要知道任何关于单个位的信息。

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

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

XOR 是结合的: x ^ (y ^ z) == (x ^ y) ^ z

身份是0: x ^ 0 == x

每个元素都有自己的逆元素: x ^ x == 0

考虑到这一点，很容易证明所述结果。考虑一个序列:

a ^ b ^ c ^ d ...

因为 XOR 是交换的和结合的，顺序并不重要，所以对元素进行排序。

现在任何相邻的相同元素 x ^ x都可以用 0(自反性质)代替。任何 0都可以删除(因为它是标识)。

尽可能长时间地重复。任何出现偶数次的数字都有整数对，所以它们都变成0并消失。

最终只剩下一个元素，即出现奇数次的元素。每次出现两次，这两个人就会消失。最终你只剩下一件事。

[更新]

注意，这个证明只需要关于操作的某些假设。具体来说，假设一个带有操作符 .的集合 S 具有以下属性:

协同性: x . (y . z) = (x . y) . z对于 S 中的任何 x，y和 z。

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

闭包: 对于 S 中的任何 x和 y，x . y也在 S 中。

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

事实证明，我们不需要假设交换性，我们可以证明它:

(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)

现在，我说“你不需要知道任何关于单个比特的事情”。我认为满足这些性质的任何组都足够了，而且这样的组不一定与异或下的整数同构。

但是@Steve Jessup 在评论中证明了我的错误，如果你用{0,1}来定义标量乘法:

0 * x = 0
1 * x = x

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

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

小开

XOR (独占 OR)运算符的定义是:

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

想象一下，右边的“1”改变了左边的比特，而右边的0不改变左边的比特。但是，XOR 是可交换的，所以如果两边相反，也是如此。 由于任何数字都可以用二进制表示，所以任何两个数字都可以用异或表示。

为了证明它是可交换的，你可以简单地查看它的定义，并且可以看到，对于任何一边的每个位的组合，如果两边被改变，结果是相同的。为了证明它是结合的，您可以简单地运行所有可能的组合，将3位相互异或，结果将保持不变，无论顺序是什么。

现在，正如我们证明了上述，让我们看看，如果我们异或相同的数字在本身会发生什么。因为这个运算是针对单个比特的，所以我们只能在两个数字上进行测试: 0和1。

0 XOR 0 = 0
1 XOR 1 = 0

因此，如果将一个数字 XOR 到它本身上，总是得到0(信不信由你，但是当需要将一个0加载到 CPU 寄存器时，编译器已经使用了 XOR 的这个属性。执行位操作比显式地将0推入寄存器更快。编译器只会生成汇编代码，将寄存器异或到自身上)。

现在，如果 X XOR X 是0，并且 XOR 是关联的，那么你需要找出在一个所有其他数字都重复了两次(或者任何其他奇数次)的数列中有哪些数字没有重复。如果我们把重复的数字放在一起，它们将异或为0。任何用0表示的 XOR-ed 都将保持其本身。因此，在异或处理这样一个序列时，您最终将得到一个不重复(或重复偶数次)的数字。

小开

这个 有很多通过位处理完成的各种功能的示例。有些可能相当复杂，所以要小心。

要理解位操作，您需要做的至少是:

  • 二进制形式的输入数据
  • 告诉你如何“混合”输入以形成结果的真理表

对于异或，真值表很简单:

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

为了在结果中获得位 n，您应用该规则来处理第一个和第二个输入中的位 n。

如果您尝试计算 1^1^0^1或任何其他组合，您将发现，如果存在1的奇数，则结果为1，否则为0。您还会发现，任何与其自身异或相同的数字都是0，这与计算的顺序无关，例如 1^1^(0^1) = 1^(1^0)^1。

这意味着当你对列表中的所有数字进行 XOR 时，那些重复的数字(或出现偶数次数的数字)将被 XOR 为0，只剩下出现奇数次数的数字。

小开

我知道这是一个相当老的职位，但我想简化的答案，因为我无意中发现它，而寻找其他东西。
可以简单地转换为开/关切换。
它将排除(如果存在)或包含(如果不存在)指定的位。

使用4位(1111) ，我们从0-15得到16个可能的结果:

 decimal | binary | bits (expanded)
0 | 0000   | 0
1 | 0001   | 1
2 | 0010   | 2
3 | 0011   | (1+2)
4 | 0100   | 4
5 | 0101   | (1+4)
6 | 0110   | (2+4)
7 | 0111   | (1+2+4)
8 | 1000   | 8
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 和其他按位操作中使用的数值，表示关联位的总值。有关更多细节，请参见 电脑编号格式和 二进制数-十进制。

例如: 0011的第1位和第2位是 on，第4位和第8位是 off。它表示为 3的十进制值，以表示打开的位，并以展开形式显示为 1+2。

至于 XOR 背后的逻辑是怎么回事，这里有一些例子
从最初的职位

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 < br/> 逻辑: ((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 < br/> 逻辑: (((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 < br/> 逻辑: ((1 ^ 8) ^ 4)

  • (1 ^ 8)1不是8加1 = 1 + 8 (9)的成员
  • (9 ^ 4)1和8不是4加 1 + 8 = 1 + 4 + 8 (13)的成员

4 ^ 13 ^ 10 = 3 < br/> 逻辑: ((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)的成员

4 ^ 10 ^ 13 = 3 < br/> 逻辑: ((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)的成员
小开

这是基于一个简单的事实: 一个数与它自己的异或结果为零。

如果一个数字为0，则 XOR 结果为该数字本身。

所以，如果我们有一个数组 = {5,8,12,5,12}。

5发生了2次。 8发生1次。 12发生了2次。

我们必须找到出现奇数次的数字，很明显，8就是这个数字。

我们从 res = 0和 XOR 开始，使用数组的所有元素。

Int res = 0; For (int i: array) Res = res ^ i; 

    1st Iteration: res = 0^5 = 5
2nd Iteration: res = 5^8
3rd Iteration: res = 5^8^12
4th Iteration: res = 5^8^12^5 = 0^8^12 = 8^12
5th Iteration: res = 8^12^12 = 8^0 = 8
小开

从名称(按位)可以明显看出，它在位之间进行操作。 看看效果如何, 例如，我们有两个数 a = 3和 b = 4, 3的二进制表示是011,4的表示是100，所以基本上相同位的 xor 是0，对于相反的位，它是1。 在给定的示例3 ^ 4中，其中“ ^”是 xor 符号，将给出111，其十进制值为7。 另一个例子，如果你给出一个数组，其中除了一个元素外，每个元素出现两次，你必须找到那个元素。 你怎么能这么做？相同数字的简单 xor 总是0，只出现一次的数字将是输出。因为任何一个0的数字的输出都是相同的名字，因为这个数字有0没有的设置位。


提交答案