认识异或运算
异或运算：相同为0，不同为1
同或运算：相同为1，不同为0
所以异或运算就可以记为无进位相加
image.png
异或运算的性质
- 0^N==N ，N^N==0
- 异或运算满足交换律和结合律
异或运算实例运用
- 如何不用额外变量交换两个数
三行代码解决问题，前提是两个数指向的内存区域必须是两个不同区域，如果是同一区域交换之后，最终交换完会变成两个0
int a = 100;
int b = 200;
a = a^b;
b = a^b;
a = a^b;
- 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，如何找到并打印这种数
结合异或运算的两个性质，直接可以把所有的数进行异或，那出现偶数次的数异或完的最终结果都是0，0和出现奇数次的那个数进行异或就可以得到出现奇数次的那个数。
//数组arr中，只有一种数出现了奇数次，其余的数都出现了偶数次
public static void printOddTimesNum1(int[] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
System.out.println(eor);
}
- 如何把int类型的数，提取出最右侧的1来
整形的数N转化成二进制数之后变成0110 1011 1000那么提取出最右侧的1，就是除了最右侧的1其余的二级制都转变成0. N取反+1再与上N就可以提取出最右侧的1来。int onlyOne = N & (~N+1）
- 一个数组中有两种数出现了奇数次，其余数都出现了偶数次，如何找到打印出这两种数？
假设出现奇数次的两种数是a，b，那么还是根据异或运算的性质，首先数组所有的数异或的结果等价于a^b；
然后把异或完的结果“取出最右侧的1来”得到结果c（假设最右侧的1所在的二进制位是第6位），那么整个数组中的数就可以分成两组，第6位是1的数是一组，第6位是0的数是另外一组，那么a，b必定是分开在两组中
其中一组的所有数进行异或就可以得到a，或者b；
//数组arr中有两种数a，b出现了奇数次，其余的数都是出现了偶数次
public static void printOddTimesNum2(int[] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++) {
//所有的数异或的结果，等价于a^b；
//异或完的结果必定不等于0 ，eor!=0;
//那么eor的二进制数中必定至少有一个位为1，
eor ^= arr[i];
}
//提取出eor最右侧的1
int rightOne = eor & (~eor + 1);
int eor1 = 0;
for (int i = 0; i < arr.length; i++) {
if ((rightOne & arr[i]) != 0) {
eor1 ^= arr[i];
}
}
System.out.println("两种数分别是：" + eor1 + " 和：" + (eor ^ eor1));
}
