按位运算符 XOR

Question

为了理解 XOR 的重要性，我发现了这段代码：

Given a set of numbers where all elements occur even number of times except one number, find the odd occurring number

但我无法想象它。异或按位运算符如何将奇数元素转出？

// Function to return the only odd occurring element
int findOdd(int arr[], int n) {
    int res = 0, i;
    for (i = 0; i < n; i++)
        res ^= arr[i];
    return res;
}

int main(void) {
    int arr[] = { 12, 12, 14, 90, 14, 14, 14 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("The odd occurring element is %d\n", findOdd(arr, n));
    return 0;
}

输出：The odd occurring element is 90

Answer 1

二进制异或是异或运算，一次执行一位。相当于减法，模2.

XOR 的真实情况 table：

a   b   a^b
1   0    1
1   1    0
0   0    0
0   1    1

如您所见，当输入位中有一个为 1 时，XOR 将一个位设置为 1（真），但不是两个都为 1。

现在，考虑一下：什么是 1 xor 1？从事实table，你知道它是零。

什么是 1 xor 1 xor 1？嗯，你知道 1^1==0，所以剩下 0^1，也就是 1.

因此，对 1 位进行异或运算，偶数次将产生零，奇数次将产生 1。

因此，如果我们取 a ^ a ^ a，对于 a 的某个值，我们会得到一个结果，其中 a 的二进制表示中的所有 1 位都已设置。（也就是说，我们回来了'a'。）

而如果我们取 a ^ a ^ a ^ a，对于 a 的某个值，我们得到的结果是 a 的二进制表示中的所有 1 位都是 0。（也就是说，我们得到 0。 )

当然，0 是个例外。0 的二进制表示中没有设置位，因此这种方法无法指示 0 的个数是偶数还是奇数。

Answer 2

XOR 表示异或，对于操作数中的每一位，如果操作数的任一对应位是 1 但不是两者，则结果位是 1：

0 ^ 0 = 0、1 ^ 0 = 1、1 ^ 0 = 0 和 1 ^ 1 = 0.

对于所有值，相同的数字相互抵消为 x ^ x == 0。对数组的所有元素进行异或运算的最终结果是出现奇数次的数字，假设只有一个。

如果除一个以外的所有重复数字都出现偶数次，并且单个条目出现奇数次，则此方法有效。

Answer 3

But I can't visualize it

那么您应该一次一行地逐步执行代码，并在循环的每次迭代中密切关注 res。

或者只是在纸上做——写下 12 的二进制形式，即 00001100，然后将该值与下一个值异或，也就是 00001100，这让你回到00000000。然后用它异或下一个值，依此类推。您可能想从一个简短的数字对列表开始，例如 {12, 12, 15, 15}，然后看看会发生什么。然后尝试删除最后一个，这样你就有了 {12, 12, 15}，看看你得到了什么。然后尝试重新排序列表：{12, 15, 12}。计算每个位被翻转的次数。

Answer 4

这就是异或运算符。

^ 是按位异或。
例如，
12^5 == 1100^0101 == (1^0)(1^1)(0^1)(0^1) == 1011

根据 XOR 的数学定义，如果输入中 1(s) 的数量为奇数，则输出为 1。

本例：
当一个数字出现偶数次时，二进制表示也会在每个位置得到两个 1 或两个 0，使结果变为 0.

例如：

2^2^3 == (1^1^1)(0^0^1) == 11 == 3
 i.e.   10 (2) 
        10 (2) 
        11 (3)
       --------
        11 (3)
       ========

5^7^5 == (1^1^1)(0^1^0)(1^1^1) == 111
         101 (5)
         111 (7)
         101 (5)
        ---------
         111 (7)
        =========

请注意，即使出现的数字在这里也没有影响。

Answer 5

XOR 是可交换的：a ^ b 等于 b ^ a。
XOR 是关联的：a ^ (b ^ c) 等于 (a ^ b) ^ c.

这两者一起意味着您可以在异或链中任意重新排序操作数。

此外：

0 是中性元素：a ^ 0 等于 a.
每个数字都是它自己的倒数：a ^ a 等于 0.

在您的代码中我们正在做 12 ^ 12 ^ 14 ^ 90 ^ 14 ^ 14 ^ 14。

我们可以将其重新排序为 (12 ^ 12) ^ (14 ^ 14) ^ (14 ^ 14) ^ 90，将出现偶数次的每个元素与其自身配对。

这简化为 0 ^ 0 ^ 0 ^ 90（因为所有相等元素对相互抵消，得到 0），这简化为 90（因为与 [=14= 进行异或运算]什么都不做）。

Answer 6

给定以下公理：

x ^ x      == 0
y ^ y ^ y  == y
z ^ 0      == z

然后例如：

x ^ x ^ y ^ y ^ y == y
\___/   \_______/
  0   ^     y     == y

另外：

x ^ y == y ^ x

所以操作数的顺序并不重要。

该点是一个值出现奇数次的结果为该值，而偶数次的结果为零，与零异或的值就是该值。

因此，正如代码开头的注释所暗示的，它仅在单个值出现奇数次且所有其他值出现偶数次时才有效。否则结果只是所有奇数出现值的异或，例如：

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

既不是 x 也不是 y。

Answer 7

我读它的方式你真的在问两个问题：

异或的重要性是什么？
XOR 如何帮助找到数列中数字的奇数出现？

要理解问题(2)，就必须理解问题(1)。理解问题 (1) 需要充分介绍 XOR 逻辑及其具有的属性。

异或的重要性是什么？

定义：异或运算的输出为真当且仅当真输入的数量为奇数。通常称为"one or the other, but not both"

这被以下真理所捕获table： XOR Truth Table

使用事实table推导出以下属性是微不足道的：

A ^ 0 = A （输出跟随变量输入）
A ^ 1 = A' （输出是变量输入的负数）
A ^ A = 0 （输出始终为零，因为两个输入相等）
(A^B)^C=A^(B^C)(关联属性)
A ^ B = B ^ A （交流属性）

现在谈谈 XOR 的重要性，即这些属性如何让人们做出有用的东西。要注意的第一个计算层是硬件层。 XOR 门是在许多基本逻辑电路中具有实用性的物理设备，该基本实用程序是 "odd occurrence detection"。部分未table 申请：

半加器：半加器 SUM 输出的真相 table 与 XOR 门相同。（为进位添加一个与门）。全加器也一样，使用 XOR 门和一些额外的支持门进行基本求和。
反相器：使用一个输入作为控制，另一个作为 "input"，异或门可用于反转输入信号。控制位也可用于传递输入，充当缓冲区。在软件中，您可以使用这些电路将 bits/bytes 从一种状态切换到另一种状态。 Val = Val ^ 1（回忆上面的第二个属性）。
比较器：当输入不同时，异或门的输出为 1，当输入相同时为 0。这是半加器的驱动逻辑。

除了这些电路之外，我们还可以在硬件级别使用异或来检查错误检测和纠正 (EDAC) 操作的字节奇偶校验，交换寄存器值（没有临时变量！），并恢复 corrupted/lost RAID 系统中硬盘驱动器的数据。

但是，软件迷并不关心这些电路，他们希望生活在抽象的土地上，提供一种以人类直观的方式使用此硬件的简单方法。让有代码。

XOR 如何帮助找到数列中数字的奇数出现？

虽然你的问题的第一条评论表明发帖者没有理解你的问题，但他们无意中正确地回答了问题，但我会进一步解释。

让我们分解一下您的 findOdd() 函数实际执行的操作。 for 循环实际上执行以下计算：

结果=0^12^12^14^90^14^14^14

回想一下 XOR 是可交换的，所以在稍微重新排序后计算变为：

结果=0^12^12^14^14^14^14^90

使用属性 A ^ A = 0 和结合律，12 和 12 的异或与 14 的异或一样下降到 0，留下：

结果=0^0^0^0^90=0^90=90

实际上，XOR 强制偶数出现变为零并且 A ^ 0 = A。希望 XOR 的这种详细描述有助于可视化引擎盖下发生的事情。

按位运算符 XOR

bitwise operator XOR

c

bit-manipulation

xor