2016年4月

异或的性质与应用

异或的性质与应用


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

定义

  异或是一种基于二进制的位运算,用符号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的结果进行异或,得到的结果就是重复数。

本文部分内容参考网络