异或运算
两个二进制数做异或运算，“不同为1，相同为0”，就是异或运算的结果。还可以从其他方面来理解异或运算
异或运输的性质
性质2
而0 ^ n，也即n+0，最后结果为0；而n ^ n，每一位必是偶数个1，因此最后结果为0。
性质4
题目一：交换两个数
我们可通过如下操作实现交换两个数a和b
int a = -2323;
int b = 10;
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println(a);
System.out.println(b);
图解
但是当我们想通过这种方法来实现交换数组中两个数据时，会出现一点问题
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
出错情况
第一步，自己与自己异或时，arr[0]=0，之后下面的操作，均是让arr[0]=arr[0]^0，因此最后的结果就是0。因为两个下标指向的是同一个空间，故第一步修改arr[i]时，arr[j]的值也改变了，导致了后续的错误。如果不是同一个空间，如
int b = 10;
a = a ^ b;
b = a ^ b;
a = a ^ b;
结果就不会出错。
题目二：不使用判断语句，返回a和b的最大值
直接看代码
public class Code02_GetMaxWithoutJudge {
// 必须保证n一定是0或者1
// 0变1，1变0
public static int flip(int n) {
return n ^ 1;
}
// 非负数返回1
// 负数返回0
public static int sign(int n) {
return flip(n >>> 31);
}
// 有溢出风险的实现
public static int getMax1(int a, int b) {
int c = a - b;
// c非负，returnA -> 1
// c非负，returnB -> 0
// c负数，returnA -> 0
// c负数，returnB -> 1
int returnA = sign(c);
int returnB = flip(returnA);
// 无论任何情况，returnA和returnB只有一个为1
return a * returnA + b * returnB;
}
// 没有任何问题的实现
public static int getMax2(int a, int b) {
// c可能是溢出的
int c = a - b;
// a的符号
int sa = sign(a);
// b的符号
int sb = sign(b);
// c的符号
int sc = sign(c);
// 判断A和B，符号是不是不一样，如果不一样diffAB=1，如果一样diffAB=0
int diffAB = sa ^ sb;
// 判断A和B，符号是不是一样，如果一样sameAB=1，如果不一样sameAB=0
int sameAB = flip(diffAB);
// 如果AB符号不一样且A为正数
// 或者AB符号一样且差为正数
// returnA=1
int returnA = diffAB * sa + sameAB * sc;
// 否则returnB=1
int returnB = flip(returnA);
// returnA和returnB仅有一个为1
return a * returnA + b * returnB;
}
public static void main(String[] args) {
int a = Integer.MIN_VALUE;
int b = Integer.MAX_VALUE;
// getMax1方法会错误，因为溢出
System.out.println(getMax1(a, b));
// getMax2方法永远正确
System.out.println(getMax2(a, b));
}
}
题目三：找到缺失的数字
先看题目
找到缺失的数字
一个数组的中数字的范围是[0,n]，给出了一个长度为n的数组，找到其中缺失的那个数。
本题就可以用到异或运算的性质4
public static int missingNumber(int[] nums) {
// [0,n]异或和 数组中数字的异或和
int eorAll = 0, eorHas = 0;
for (int i = 0; i < nums.length; i++) {
eorAll ^= i;
eorHas ^= nums[i];
}
eorAll ^= nums.length;
return eorAll ^ eorHas;
}
题目四：只出现奇数次的数字
只出现奇数次的数字
该方法可以用于数组中某个元素只出现奇数次，其余元素均出现偶数次的情况。
我们可以用到异或的性质2和3，所有元素求异或和，最终结果就是只出现奇数次的元素
public static int singleNumber(int[] nums) {
int eor = 0;
for (int num : nums) {
eor ^= num;
}
return eor;
}
题目五：只出现奇数次的数字II
只出现奇数次的数字II
该方法可以用于数组中恰好有两个元素只出现奇数次，而其余所有元素均出现偶数次。
n&(~n+1)
可以看到（ ~ n+1）的结果就是n的相反数，即-n。
然后就是主要算法，基于上面的题目四我们可知，在该题目情况下整个数组元素求异或和为a^b，而异或和一定是一个非0数，因此其最右边的那个1所在的位，a和b的该位就不相同，因此可根据此位，将数组元素划分为此位为0和此位为1的两类，其中一类的异或和就是a，而另一类的异或和就是b。
public static int[] singleNumber(int[] nums) {
int eor1 = 0;
for (int num : nums) {
// nums中有2种数a、b出现了奇数次，其他的数都出现了偶数次
eor1 ^= num;
}
// eor1 : a ^ b
// Brian Kernighan算法
// 提取出二进制里最右侧的1
int rightOne = eor1 & (-eor1);
int eor2 = 0;
for (int num : nums) {
if ((num & rightOne) == 0) {
eor2 ^= num;
}
}
return new int[] { eor2, eor1 ^ eor2 };
}
题目六：出现少于m次的数
出现少于m次的数
该方法可以解决数组中某个数出现次数少于m次，其余元素均出现m次的情况。
首先，若某个元素出现了m次，那么该元素某一位如果为1，那么这位的1就一定出现了m次；如果某一位为0，那么这位的0就一定出现了m次。因此，我们只需要统计数组中所有元素的32位中，每一位1的个数和，如果是m的整数倍，说明出现次数少于m次的数该位就为0；反之则为1。
public static int find(int[] arr, int m) {
// cnts[0] : 0位上有多少个1
// cnts[i] : i位上有多少个1
// cnts[31] : 31位上有多少个1
int[] cnts = new int[32];
for (int num : arr) {
for (int i = 0; i < 32; i++) {
cnts[i] += (num >> i) & 1;
}
}
int ans = 0;
for (int i = 0; i < 32; i++) {
if (cnts[i] % m != 0) {
ans |= 1 << i;
}
}
return ans;
}
