异或的性质与应用

 &#8195今天有朋友问我异或最重要的性质是什么，一时只记得以前有老师讲过，于是上网查了一下，并整理如下。

定义

&#8195&#8195异或是一种基于二进制的位运算，用符号XOR或者 ^ 来表示。其运算法则是对运算符两侧的数的每一位二进制位，相同结果为0，不同结果为1。它与或运算的区别在于，当运算符两侧均为1时，或运算结果为1，而异或运算结果为0。
  异或运算又称之为 半加 ，半加的概念就是不进位的加法；数学上称异或为 按位模2加 ，按位模2加就是按位进行两数相加后除以2取余的运算。

  半加运算是不考虑进位的，也就是说它的进位会被舍弃。很显然它的运算法则如下：
0+1=0 0+1=1 1+0=1 1+1=0
  模2运算是一种二进制算法，与四则运算相同。模2运算包含模2加，模2减，模2乘，模2除四种运算。比如模2加，按其定义，1与0模2加，其结果就是1+0 = 1，然后1/2为0余1， 所以1与0模2运算结果为1；再如，1与1模2加，其结果1+1 = 10=2（D），2/2结果为1余0，所以1与1模2加运算结果为0。以此类推，按位模2加的运算结果与半加运算是相同的。

性质

  1、 交换律
  2、 结合律（即(A^B)^C=A^(B^C)）
  3、 对于任何数X，都有X^X = 0，X^0 = X
  4、 自反性 A^B^B = A^0 = A

  异或运算常见于多项式除法，但它最重要的性质是自反性，即A^B^B = A。即对于既定的数A，用同样的运算因子（B）与其做两次异或运算后得到的结果仍是A本身。这是一个神奇的性质，利用这个性质可以解决一些实际问题。例如：几乎所有的C语言教科书都会向初学者提出，要交换两个变量的值，必须引入一个中间变量。但我们知道异或后，我们有了一种新的办法，这种办法可以不使用中间变量。设有A,B两个变量，存储的值分别为a,b，则以下三行表达式可互换他们的值：
A = A^B // (A = a^b)
B = B^A // ( B = b^ (a^b) == a^b^b == a)
A = A^B // ( A = (a^b)^ a == b^a^a == b)
类似的，该运算还可应用于加密，数据传输，校验等许多领域。

应用举例

设1~1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它数只出现一次；设计算法，将这个数找出来，要求每个元素只能访问一次，不能使用辅助变量。

解法一：

  显然已经有人提出了一个比较精彩的解法，将所有数加起来，减去1+2+...+1000的和。这个算法已经足够完美了，相信出题者的标准答案也就是这个算法，唯一的问题是，如果数列过大，则可能会导致溢出。

解法二：

  异或就没有这个问题，并且性能更好。
  将所有的数全部异或，得到的结果与1^2^3^...^1000的结果进行异或，最终得到的结果就是重复的数。

  这个算法虽然看起来简单，但证明起来并不是一件容易的事情。这与异或运算的几个特性有关：
  首先是异或运算满足交换律、结合律。所以，1^2^...^n^...^n^...^1000，无论这两个n出现在什么位置，都可以转换成为1^2^...^1000^(n^n)的形式。
  其次，对于任何数x，都有x^x=0，x^0=x。

所以：
  1^2^...^n^...^n^...^1000 = 1^2^...^1000^(n^n)= 1^2^...^1000^0 = 1^2^...^1000（即序列中除了n的所有数的异或）。

  设，1^2^...^1000（该序列中不包含n）的结果为T
  则，1^2^...^1000（该序列中包含n）的结果就是T^n
  T^(T^n)=n
所以，将所有元素的值全部异或，得到的结果再与1^2^3^...^1000的结果进行异或，得到的结果就是重复数。

本文部分内容参考网络