异或运算在算法中的神奇应用

1. 什么是异或

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

示例：6^7=?

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

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

2. 异或运算的特性

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

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

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

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