异或的用途

约定不等于承诺〃 2021-09-27 05:28 499阅读 0赞

> 正式进入高深的算法之前，我们先来学些小技巧。本章拿异或开刀，你会发现一些很有趣的东西。

# 异或的性质 #

异或是一种基于二进制的位运算，用符号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，同自己求异或为0，同0求异或为自己

4、自反性 A ^ B ^ B = A ^ 0 = A ，连续和同一个因子做异或运算，最终结果为自己

# 例一：不引入第三个变量，交换两个变量(整数)的值 #

`// 假设存在 a b 两个整数`

`a = a^b`

`b = a^b`

`a = a^b`

是不是很神奇，如果不理解，请仔细推算，推算完后脑洞会开一点吧。

# 例二：判断奇偶数更简单高效的做法 #

奇数二进制的最低位一定是1，偶数二进制的最低位一定是0，所以 `a^1==1?偶数:奇数` ，代码就不写了吧。。。脑洞再开

和0做与运算也是可以的`a&0==0?偶数:奇数`

# 例三：找出那个唯一成对的数 #

1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现 一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空 间，能否设计一个算法实现？

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

解法二、异或就没有这个问题，并且性能更好。

将所有的数全部异或(1^2^…^1000^k,k为重复数)，得到的结果与(1^2^3^…^1000)的结果进行异或，得到的结果就是重复数。 即`(1^2^...^1000^k)^(1^2^3^...^1000)`，由于有结合律、交换律存在，我们可以这么调整为`(1^1^2^2^...^1000^1000^k)`那结果当然就是k了，哈哈哈

# 例四：上例变形，找出出现奇数次的数 #

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

`结果=a[0]^a[1]^...^a[n-1]`

因为奇数个数字连续异或之后是自己，偶数个数连续异或后为0，自己和0异或还是自己。。。真的很神奇

# 例五：再变形——找出那个唯一落单的数 #

> 一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

套路是一样的，所有元素连续求异或，得到的结果为只出现一次的数字。

# 例六：突然变难，找出数组中落单的两个数 #

> 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

## 开脑洞 ##

先试试之前的套路：`a[1]^a[2]...^a[n] = a[x]^a[y]`，a\[x\]和a\[y\]就是这两个数，因为其他数出现偶数次，在异或过程中被自己干掉了（^\_^），但是我们得到的结果是`a[x]^a[y]`，怎么把他俩分开呢？

继续在结果上分析，既然a\[x\]和a\[y\]不同，他俩一定在某一个位（记为N）上其中一个是0，其中一个是1（读者仔细想想！），异或值在该位为1，如果找不到这样的差别，二者岂不是相同了？

既然这样，我们可以根据这个性质把数组区分为两个子数组，其中一个子数组（s1）的所有元素在N二进制位上为1，另一个子数组（s2）的所有元素在N二进制位上为0，这样s1必然包含a\[x\]和a\[y\]中的一个而s2则包含另一个且s1和s2的元素一定不同（即不会把成对的数分割），分别对两个子数组实施上面的套路（依次连续异或）就会得到两个结果，这两个结果就是最终结果。

伪代码：

`xorOfResult = a[1]^a[2]...^a[n]`

`N = 0`

`while(true){`

`if(xorOfResult & (1<<N++) == 1)`

`break`

`}`

`/*这个得出N位为整数的第一个非0（即1）位的方法很巧妙：和1做按位与运算，如果位上为1结果为1，N求出；`

`如果位上为0则结果为0，将1移动到下一位继续判断*/`

`N-- // 循环最后多加了1`

`s1 = new Array(),s2 = new Array()`

`for i=1 to n`