认识异或运算

异或运算：相同为0，不同为1
同或运算：相同为1，不同为0
所以异或运算就可以记为无进位相加

image.png

异或运算的性质

1. 0^N==N ，N^N==0
2. 异或运算满足交换律和结合律

异或运算实例运用

1. 如何不用额外变量交换两个数

三行代码解决问题，前提是两个数指向的内存区域必须是两个不同区域，如果是同一区域交换之后，最终交换完会变成两个0

  int a = 100;
  int b = 200;
  a = a^b;
  b = a^b;
  a = a^b;

2. 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，如何找到并打印这种数

结合异或运算的两个性质，直接可以把所有的数进行异或，那出现偶数次的数异或完的最终结果都是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);
    }

3. 如何把int类型的数，提取出最右侧的1来

整形的数N转化成二进制数之后变成0110 1011 1000那么提取出最右侧的1，就是除了最右侧的1其余的二级制都转变成0. N取反+1再与上N就可以提取出最右侧的1来。int onlyOne = N & (~N+1）

4. 一个数组中有两种数出现了奇数次，其余数都出现了偶数次，如何找到打印出这两种数？

假设出现奇数次的两种数是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));
    }