异或理解与应用

异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。

简单理解就是不进位加法，如1+1=0，,0+0=0,1+0=1。

性质

1、交换律

2、结合律（即(a^b)^c == a^(b^c)）

3、对于任何数x，都有x^x=0，x^0=x

4、自反性 A XOR B XOR B = A xor  0 = A

异或运算最常见于多项式除法，不过它最重要的性质还是自反性：A XOR B XOR B = A，即对给定的数A，用同样的运算因子（B）作两次异或运算后仍得到A本身。这是一个神奇的性质，利用这个性质，可以获得许多有趣的应用。 例如，所有的程序教科书都会向初学者指出，要交换两个变量的值，必须要引入一个中间变量。但如果使用异或，就可以节约一个变量的存储空间： 设有A,B两个变量，存储的值分别为a，b，则以下三行表达式将互换他们的值 表达式 （值） ：

 A=A XOR B (a XOR b)

 B=B XOR A (b XOR a XOR b = a) 

 A=A XOR B (a XOR b XOR 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的结果进行异或，得到的结果就是重复数。

当然有人会说，1+2+...+1000的结果有高斯定律可以快速计算，但实际上1^2^...^1000的结果也是有规律的，算法比高斯定律还该简单的多。

 

google面试题的变形：一个数组存放若干整数，一个数出现奇数次，其余数均出现偶数次，找出这个出现奇数次的数？

 

解法有很多，但是最好的和上面一样，就是把所有数异或，最后结构就是要找的，原理同上！！

转载自http://longzxr.i.sohu.com/blog/view/190676432.htm

奇数个异或是本身，偶数个是0；0^a=a；异或有交换律

 

参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。

即：

      0^0 = 0，

      1^0 = 1，

      0^1 = 1，

      1^1 = 0

例如：10100001^00010001=10110000

按位异或的3个特点:

(1) 0^0=0,0^1=1  0异或任何数＝任何数

(2) 1^0=1,1^1=0  1异或任何数－任何数取反

(3)              任何数异或自己＝把自己置0

                

按位异或的几个常见用途:

(1) 使某些特定的位翻转

    例如对数10100001的第2位和第3位翻转，则可以将该数与00000110进行按位异或运算。

　　　　　  10100001^00000110 = 10100111

(2) 实现两个值的交换，而不必使用临时变量。

    例如交换两个整数a=10100001，b=00000110的值，可通过下列语句实现：

　　　　a = a^b； 　　//a=10100111

　　　　b = b^a； 　　//b=10100001

　　　　a = a^b； 　　//a=00000110

 

////////////////////////////////////////////////////////////

两个变量交换值的方法【http://blog.sina.com.cn/s/blog_676015470100izpg.html】

第一种方法，大家会借助第三个变量来实现：

如：C=A;A=B;B=C;

这种方法需要借助第三变量来实现；

第二种方法是利用加减法实现两个变量的交换，

如：A=A+B;B=A-B;A=A-B;

第三种方法是得用位异或运算来实现，也是效率最高的一种，在大量数据交换的时候，效率明显优于前两种方法，

如：A=A^B;B=A^B;A=A^B;

原理：利用一个数异或本身等于０和异或运算符合交换率。

PS:还有一篇更为深刻的文章对换值进行了探讨，作者的研究精神值得学习：

http://rednaxelafx.javaeye.com/blog/134002

/////////////////////////////////////////////////////////////

(3) 在汇编语言中经常用于将变量置零：
    xor   a，a

(4) 快速判断两个值是否相等
    举例1: 判断两个整数a，b是否相等，则可通过下列语句实现：
        return ((a ^ b) == 0)
   
    举例2: Linux中最初的ipv6_addr_equal()函数的实现如下:
    static inline int ipv6_addr_equal(const struct in6_addr *a1, const struct in6_addr *a2)
    {
        return (a1->s6_addr32[0] == a2->s6_addr32[0] &&
            a1->s6_addr32[1] == a2->s6_addr32[1] &&
            a1->s6_addr32[2] == a2->s6_addr32[2] &&
            a1->s6_addr32[3] == a2->s6_addr32[3]);
    }
   
    可以利用按位异或实现快速比较, 最新的实现已经修改为:
    static inline int ipv6_addr_equal(const struct in6_addr *a1, const struct in6_addr *a2)
    {
    return (((a1->s6_addr32[0] ^ a2->s6_addr32[0]) |
        (a1->s6_addr32[1] ^ a2->s6_addr32[1]) |
        (a1->s6_addr32[2] ^ a2->s6_addr32[2]) |
        (a1->s6_addr32[3] ^ a2->s6_addr32[3])) == 0);
    }