定义

无进位相加：相同为0，不同为1。

性质

0 ^ N = N N ^ N =0 交换律 结合律

做题

  1. 如何不用额外变量交换两个数 ```java // 需要额外变量的写法 public static void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

// 不需要额外变量 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]; }

  2. 2. 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数 。
  3. ```java
  4. public static void printOddTimesNum1(int[] arr){
  5.     int eor = 0;
  6.     for (int i = 0; i < arr.length; i++) {
  7.         eor ^= arr[i];
  8.     }
  9.     System.out.println(eor);
  10. }

解读：性质里提到过 N ^ N =0。所以出现偶数次的数，进行异或，那结果一定是0，而且 交换律+结合律的性质，无论数组里的数是如何排序的，都不影响最后的结果。

  1. 怎么把一个int 类型的数，提取出 最右侧的1来。

    public static void findRithtOne(int N){
 int rightOne = N & ((~N)+1);
}

    解读：6 对应的二进制位 0000 0110,那么取出来的应该是0000 0010。如何思考呢？将原数取反，也就是rightOne 右侧的0会全部变成1。然后操作 +1，会产生右侧进位到 原数第1个非0位。这样再与原数 &与操作，就只剩rightOne了。
    image.png

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

    /**
* 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数 
* @param arr
* 思路：eor = a ^ b
* 找到 eor 最右侧的 1，说明 该位置上 a 和 b 一定不一样（一个是0，一个是1）
* 把数组arr中所有数，按该位置是0或1分两类，这时候 a和b 肯定各在一个分类组里
* 定义 eor1 = 分类组1的数据异或，所以 eor1 = a
* 所以 吧= eor ^ eor1
*/
public static void printOddTimesNum2(int[] arr){
 int eor = 0;
 for (int i = 0; i < arr.length; i++) {
     eor ^= arr[i];
 }
 int rightOne = eor & (-eor);
 int eor1 = 0;
 for (int i = 0; i < arr.length; i++) {
     if ((arr[i] & rightOne) !=0){
         eor1 ^= arr[i];
     }
 }
 System.out.println("一个"+eor1);
 System.out.println("另一个"+(eor ^ eor1));
}

  3. 在一个数组中，只有一种数出现了K次，其他数都出现了M次，M>1,K<M，找到出现K次的数是几？要求：额外空间复杂度O(1)，时间复杂度O(N)。

    public class Code03_KM {
 public static int kmTest(int[] arr, int k, int m){
     // 定义32位的数组t；
     // 遍历arr数组的数，每个数二进制表示，各个位置上有1，则累加到数组t位置上
     // 如果t数组该位置上的sum % m !=0,整除m不为0，说明出现K次的数，在这个位置有1
     // 这样找出 t数组上 整除后，!=0的位。
     int[] t = new int[32];
     for (int num : arr) {
         for (int i = 0; i < 32; i++) {
             /*if (((num << 1) & 1 ) !=0){
                 t[i] += 1;
             }*/
             t[i] += (num >>i) & 1;
         }
     }

     int ans =0;
     for (int i = 0; i < 32; i++) {
         if (t[i] % m !=0){
             ans |= (1 << i);
         }
     }
     return ans;        
 }

 public static void main(String[] args) {
     int[] arr = {2,4,5,4,5,4,2,5};
     System.out.println(kmTest(arr,2,3));
 }
}

    �