异或运算：交换变量与经典题目
梳理异或运算的性质，并用它解决交换变量和数组统计等基础算法题。
1. 异或运算
异或运算的符号是^，运算规则是相同为0，不同为1。也就是说判断二者是否不相同，如果不相同则为1，其他情况都是0
异或运算还被称作无进位相加，也就是说在每一位上相加的结果不进位，这样更好理解，也就是：
0 0 1 1 0 1 1 0
0 1 0 1 1 1 0 1
------------------------------------
0 1 1 0 1 0 1 1
异或运算有一些性质可以运用：
- 交换律：
a ^ b == b ^ a - 结合律 ：
(a ^ b) ^ c == a ^ (b ^ c) - 与自身异或得到0：
a ^ a == 0 - 与0异或得到自身：
a ^ 0 == a
牢记这些性质对算法题有很大的帮助
2. 异或运算常见题目
2.1 不申请三方变量交换两个值
描述：给定两个变量a和b，请你在不申请第三个变量的基础上交换二者的数值
思路：我们可以用异或运算的性质来解决这道题
- 先让 a = a ^ b
- 再让 b = a ^ b，此时b实际上是 (a ^ b) ^ b，根据异或运算的交换律和结合律，b就是a ^ (b ^ b)，又知道b ^ b的结果实际上是0，所以此时是a ^ 0，就等于a，所以b此刻就等于a
- 最后让 a = a ^ b，此时就是 (a ^ b) ^ a，再根据刚刚的分析就等于b
至此a和b就完成了交换
public static void swap (int[] arr, int a, int b) {
arr[a] = arr[a] ^ arr[b];
arr[b] = arr[a] ^ arr[b];
arr[a] = arr[a] ^ arr[b];
}注意！这种交换方式只适用于a和b是两块内存空间的情况，如果a和b指向同一个内存空间，那么异或最开始就是自己和自己异或，会被刷成0
2.2 只有一种数出现奇数次
题目：给定一个数组arr，其中只有一个数num出现了奇数次，其他所有数都出现偶数次，请找出出现这个奇数次的数
思路：这道题同样可以运用异或运算的性质来解答，即用一个变量eor = 0来依次与数组中每一个数进行异或，也就是eor ^ arr[0] ^ .....arr[i]
由交换律和结合律我们知道，eor与整个数组的数依次异或可以变为eor先与所有出现次数为偶数的数异或，再与出现次数为奇数的数异或（先异或偶次，再异或奇次）
由异或的性质我们知道，这些偶数次的数可以先异或，eor与出现偶数次的数异或的结果都为0，最后与奇数次的数异或的结果就是该奇数次的数
例如：eor ^ ( 3 ^ 3 ^ 3 ^ 3 ) ^ ( 6 ^ 6) ^ (4 ^ 4 ^ 4) = eor ^ 0 ^ 0 ^ 4 = 0 ^ 4 = 4
我的代码实现：
public static int findSoleOdd(int[] arr){
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
return eor;
}
2.3 提取一个数最右侧的1
题目：在Java里面，int类型的数是32位二进制存储的，给定一个int类型的数num，找到该数的二进制的最右侧的那个1，例如：...0000101101101100 提取成为 --> 000...000000100
思路：
这道题实际上让这个数与上自己的相反数就可以了
即rst = num & (-num)
我们来举个例子：
11010110 取反 --> 00101001 加上1 --> 00101010
接下来将二者做与运算：
11010110 00101010
可以见到，二者除了最右边的那个1相等之外，其他的都相反，与运算后只能保留最右边的那个1
2.4 有两种数出现奇数次
题目：给定一个数组arr，其中只有两个数a, b出现了奇数次，其他所有数都出现偶数次，请找出这两个出现奇数次的数
思路：
这道题是2.2的拓展，我们同样可以用到异或运算，根据2.2的分析，我们用eor = 0来异或一遍这个数组后，得到的结果应该是 eor = a ^ b
接下来我们将a和b想办法提取出来：
由于a和b一定是两个不同的数，所以a ^ b一定有一位是1，即a和b至少有一位不相同。
我们将最右边位的1提取出来（方法参见2.3），得到rightOne，假设是x位上是1，那么我们可以知道，a和b一定在x位上不同，一个是0一个是1！
依据这个我们可以把整个数组在逻辑上分为两组，x位上是1的、x位上是0的
我们用eor2 = 0对数组进行第二次异或，这次我们只让eor2异或其中x位上是1的那些数
由于数组里面那些偶数次的数对结果根本没有影响，所以eor2的结果一定是a或者b
得到了其中一个，由于eor = a ^ b，因此我们想要得到另一个只需要让eor ^ eor2就可以了
我的代码：
public static int[] findTwoOdd(int[] arr){
// 第一次异或，得到 eor = a ^ b
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
// 找到a和b在哪一位上不相同
int rightOne = eor & (-eor);
int eor2 = 0;
for (int i = 0; i < arr.length; i++) {
if ((arr[i] & rightOne) != 0) {
eor2 ^= arr[i];
}
}
// 结果数组，存储a和b
int[] rst = {eor2, eor ^ eor2};
return rst;
}其中(arr[i] & rightOne) != 0，是在判断如果该数在x位上为1，则和eor2异或
因为rightOne得到的是在x位上为1，其余位都是0的数，所以和一个数与的结果能代表该数的x位是否为1
2.5 拓展题
题目：数组中所有的数都出现了M次，只有一种数a出现了K次，1 <= K < M，返回这种数
思路分析：
我们创建一个长度为32的数组count，遍历数组，数组中的每个数转化为32进制数后，假设其在x位上为1，我们将count[x] + 1
这样一来这个数组就能记录各个位上出现了多少个1
- 例如：一个数位9，二进制是0000....01001，可见0位和3位上是1，我们就将count[0]和count[3]都加1
我们依次遍历count数组里面的每一个数，也就是32位数的每一位
-
如果x位上的计数是M的倍数，那么a在x位上肯定不为1，因为在x位上为1的其他数都计数了，而其他数都出现了M次，导致x位是M的倍数
-
如果x位上的计数不是M的倍数，那么a在x位上一定是1，只有这样才导致x位上增加了额外K次
因此代码如下：
public static int findK(int arr[], int k, int m) {
int[] count = new int[32];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < 32; j++) {
count[j] += (arr[i] >>> j) & 1;
}
}
int rst = 0;
for (int i = 0; i < count.length; i++) {
if (count[i] % m != 0) {
rst |= 1 << i;
}
}
return rst;
}解释一下其中的一些点：
count[j] += (arr[i] >>> j) & 1;，外循环遍历数组中的每一个数，拿到arr[i]，内循环遍历arr[i]的每一位，看是否为1。判断的方法是将arr[i]右移j位，再与1，这样能判断j位置是否是1，比如： 01010 右移0位后&1的结果是0，右移1位： 00101 &1后得到1，则第1位是1 00001 00001- 这里用
>>>无符号右移，使得能判断负数 rst |= 1 << i;rst是0，即32位都是0，count数组里面哪位不是m的倍数，就是出现了k次的数在该位置为1，我们用或运算把ans的该位置变成1