异或运算及其应用

忘是亡心i 2022-07-18 01:54 314阅读 0赞

异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，  
其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。  
它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。  
一、异或的性质  
交换律：a ^ b = b ^ a  
结合律：a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c  
d = a ^ b ^ c 可以推出 a = d ^ b ^ c  
自反性：a ^ b ^ a = b  
   
二、异或的应用  
交换两个数  
最常见的做法就是增加一个临时变量，代码如下：

public void switchValue(int a, int b) \{  
        System.out.println("Before switch:    a:" + a + "\\tb:" + b);  
        int temp = b;  
        b = a;  
        a = temp;  
        System.out.println("After switch:    a:" + a + "\\tb:" + b);  
    \}  
升级版，将两个数加减来实现，代码如下：

public void switchValue(int a, int b) \{  
        System.out.println("Before switch:    a:" + a + "\\tb:" + b);  
        a = a + b;  
        b = a - b;  
        a = a - b;  
        System.out.println("After switch:    a:" + a + "\\tb:" + b);  
    \}利用异或运算，也可以将两个数交换，例如：

public void switchValue(int a, int b) \{  
        System.out.println("Before switch:    a:" + a + "\\tb:" + b);  
        a = a^b;  
        b = a^b;  
        a = a^b;  
        System.out.println("After switch:    a:" + a + "\\tb:" + 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^...^n^..^1000（序列中包含一个n）的结果为T 则1^2^..^n^..^n^..^1000（序列中包含2个n）的结果就是T^n。 T^(T^n)=n。所以，将所有的数全部异或，得到的结果与1^2^3^...^1000的结果进行异或，得到的结果就是重复数。  
②一个数组存放若干整数，一个数出现奇数次，其余数均出现偶数次，找出这个出现奇数次的数？  
这个其实是①的一个变形题目，最直接的办法还是和上面一样，就是把所有数异或 (奇数个异或是本身，偶数个是0)

单片机串口通信中，用于通信帧的校验，这是一种简单又相对可靠的方法，比简单的奇偶校验更为可靠，比相对复杂的LRC校验简单。