异或运算在算法中的神奇应用-Toy模板网

这篇具有很好参考价值的文章主要介绍了异或运算在算法中的神奇应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 什么是异或

两个二进制数进行异或运算时，每一位上的数相同则结果为0，不同则结果为1。

示例：6^7=?

转化成二进制：
6=110
7=111
6^7=110^111=001=1

简单记：异或就是二进制的无进位相加。
还有个同或运算：相同为1，不同为0，和异或是反的。

2. 异或运算的特性

任何数与0异或，结果还是这个数：0^n=n
任何数与自身异或，结果都是0：n^n=0
异或运算满足交换律和结合律

这几个特性按照无进位相加的思路来理解，就很好想明白。

3. 异或运算的神奇应用

3.1 两数交换

两个数经过3次异或运算后，可以交换位置。这其实也是上面特性的一个应用。

a=1; b=3;
a=a^b; // a与b异或后，赋值给a：a=1^3 b=3
b=a^b; // 赋值后的a与b再次异或后，赋值给b：a=1^3 b=1^3^3=1（此时a初始的值已经赋给b了）
a=a^b; // 赋值后的a和b再次异或后，赋值给a：a=1^3^1=3 b=1（完成了交换）

以上交换的逻辑，只有在两个数指向不同的内存块时，才有效。如果两个数，指向同一个内存块，实际上就是1个数，此时异或后，会得到0。
算法题：https://leetcode.cn/problems/swap-numbers-lcci/description/

3.2 找到出现奇数次的那个数

有一组数，只有一个数出现了奇数次，其他数都出现了偶数次，如何快速找到这个数？

只要将所有数都做异或运算，得到的结果就是那个数。这是 n^n=0 & 0^n=n 的一个应用。

算法题：https://leetcode.cn/problems/single-number/description/

3.3 提取二进制数最右侧的1（与异或无关）

给定一个二进制的数，找到最右侧的1。例如，二进制数：11001000，最右侧的1对应的二进制数为：00001000。

通过公式：n & (～n + 1) 即可得到结果。

以 11001000 为例：
00110111 // 对n取反:~n
00111000 // 取反后加1:～n + 1
00001000 // 和n进行与运算:n & (～n + 1)

取反运算规则：将二进制的每一位逆转，1变成0，0变成1
与运算规则：仅1&1=1，其他都为0。

应用：找出一个二进制数n中一共有多少个1

rightOne = n & (～n + 1) // 找出最右侧的1
n ^= rightOne // n和rightOne异或后，再赋值给n，可以抹掉n最右侧的1
循环以上两步直到n=0，数出一共循环了多少次即可

算法题：https://leetcode.cn/problems/number-of-1-bits/description/

扩展：通过公式 n & (n - 1) 可以抹掉最右侧的1，也可以找出二进制数中有多少个1。

以 11001000 为例：
11000111 // n - 1
11000000 // n & (n - 1)

3.4 找到出现奇数次的那2个数

有一组数，大部分数都出现了偶数次，只有2个不同的数出现了奇数次，如何快速找到这2个数？

思路：
假设这两个数为a和b，将所有的数进行异或运算，得到的结果一定是：eor=a^b
eor一定不等于0（因为a!=b）,也就是说eor的二进制数在某一位上一定是1，且这个1一定来源于a和b其中一个数（因为只有1^0=1）
假设eor在第8位是1，根据第8位是1将数组分成两组，1组中数的第8位都是1，2组中数的第8位都是0，如果a在1组中，那么b一定在2组中
上面两组数中，除了a和b以外，其他数一定出现偶数次。1组所有数全部异或一定等于a，同理2组异或等于b
那么，只要得到eor最右侧的1对应的数eor'，再用eor'与最初的数组的每一个数进行与运算，结果等于1（或等于1）的全部保留下来进行异或运算，一定得到了a或b
再用eor异或上面的结果，就得到了另一个数，这样两个数都找到了。

以 [4, 4, 5, 5, 6, 7] 为例（对应的二进制数：[0100, 0100, 0101, 0101, 0110, 0111]）：
eor= 4^4 ^ 5^5 ^ 6^7 = 6^7 = 0110^0111 = 0001 // 将所有的数异或
eor'= 0001 // 找到eor最右侧的1对应的数（通过第3.3小节的公式可以得到）
array1= [0100, 0100, 0110] // 分成2组数，这一组和eor'进行与运算后都等于0，其他的数和eor'进行与运算后都不等于0
a= 0100 & 0100 & 0110 = 0110 = 6
b= a^eor = 0110 ^ 0001 = 0111 = 7