异或运算

无进位相加

异或运算属于位运算，需要将数转换为二进制进行运算，常见口诀：

异或运算：相同为0，不同为1。

同或运算：相同为1，不同为0。

异或运算口诀容易与同或运算口诀记法混淆，建议将异或运算记成无进位相加！

异或运算的性质

• 0 ^ N == N
• N ^ N == 0
• 异或运算满足交换律和结合律

使用无进为相加来理解就会很容易理解上述的性质。

异或运算性质考题

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

   注意，如果两个变量指向的内存是一样的，这种做法是不可行的，例如对数组元素进行互换，如果位置相等则不可以使用异或运算进行互换操作，否则值会变成0。也就是说，异或运算交换的前提要保证操作的是不同内存的数据。

   int a = 1, b = 2;
   a = a ^ b;
   b = a ^ b;
   a = a ^ b;
   

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

   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

   int n =  n & (~n + 1) 
   
   

4. 统计一个int类型整数的二进制有几个1

   public static int bit1counts(int n) {
     int count = 0;
     while(n != 0) {
       int rightOne = n & (~n + 1);
       count++;
       n ^= rightOne;
     }
     return count;
   }
   

5. 一个数组中有两种数出现了奇数次，其他数都出现了偶数次 ，怎么找到并打印这两种数

public static void printOddTimesNum2(int[] arr) {
  int eor = 0;
  for (int i = 0; i < arr.length; i++) {
    eor ^= arr[i];
  }
  // eor = a ^ b 并且 eor != 0
  // 提取eor最右侧的1出来
  int rightOne = eor & (-eor); 
  // eor'，即 onlyOne = a 或 b
  int onlyOne = 0; 
  for (int i = 0 ; i < arr.length;i++) {
    if ((arr[i] & rightOne) != 0) {
      onlyOne ^= arr[i];
    }
  }
  System.out.println(onlyOne + " " + (eor ^ onlyOne));
}