前言： 本章主要是针对异或运算相关问题总结的几个小题目，掌握了它们，在写一些算法题时或许有意想不到的惊喜！

1. 基础介绍

• 任何两个相同的数异或结果为0
• 一个数和0异或结果不变
• 多个数异或遵循交换律
• 可以通过 ans |= (1 << i) 将 ans 二进制的 i 位置设置为1

2. 题目

题一：如何不用额外变量交换两个数 a 和 b

方法模板：

a = a ^ b;
b = a ^ b;
a = a ^ b;

示例代码：

int a = 3;
int b = 5;
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println(a + " " + b);
// 结果为：5 3

注意：

交换数组中的两个值也可以使用异或，但是要注意数组的两个下标不能相同，否则交换后的值不正确

题二：一个数组中有一种数出现了奇数次，其它数都出现了偶数次，怎么找到并打印这种数

方法模板： 让所有的数一起异或，出现偶数次的值异或结果为0，出现奇数次的值结果为该值本身，任何一个值和0异或结果不变

public static void printOddTimesNum1(int[] arr) {
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    System.out.println(eor);
}

示例代码：

public static void main(String args[]) {
    int[] arr = {1, 1, 2, 3, 3, 4, 4};
    printOddTimesNum1(arr);
}
// 结果为：2

题三：怎么把一个 int 类型的数 a，提取出只保留其二进制中最右侧为1位置，其余位值都修改为0时的值（如 1110 -> 0010）

方法模板：

a = a & (~a + 1)
    
a = a & (-a)

示例代码：

int num = 10;	// 10 的二进制为 1010
int num1 = num & (~num + 1);
int num2 = num & (-num);
System.out.println(num1);
System.out.println(num2);
// 结果都为：2	（2 的二进制为 0010）

题四：一个数组中有两种数 a 和 b 出现了奇数次，其它数都出现了偶数次，怎么找到并打印这两种数

方法模板： 将该数组的所有数都进行异或，结果就为 a ^ b，由于 a 和 b 不相等，则异或结果肯定不为0，即结果的二进制的值肯定有一位为1，因此可以该结果二进制的某位置为1的位置作为分界，数组肯定有一些数该位置的值都为1，因此可以找出所有该位置都为1的数，对他们进行异或，假设异或结果为 a，则 a 再与 a ^ b 进行异或就能得到 b

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

示例代码：

public static void main(String args[]) {
    int[] arr = {1, 1, 2, 3, 3, 4, 4, 5};
    printOddTimesNum2(arr);
}
// 结果为：5 2

题五：一个数组中有一种数出现了 K 次，其它数都出现了 M 次（M > 1，K < M），找到出现了 K 次的数，要求额外空间复杂度为 O(1)，时间复杂度为 O(N)

模板方法： 可以申请一个数组长度为32的数组，该数组其实表示一个数组二进制的32位，用来计算原数组中所有数，在二进制的每个位置中1的总数。将申请的数组的每位的值都模上 M，如果结果为0，则表示出现次数为 K 的数的该位的值为0；如果结果不为0，则表示出现次数为 K 的数的该位的值为1。注意当出现次数为 K 的值为0，不满足上述条件，需要特殊处理

public static int onlyKTimes(int[] arr, int K, int M) {
    int[] bin = new int[32];
    for(int num : arr) {
        for(int i = 0; i < 32; i++) {
            bin[i] += (num >> i) & 1;
        }
    }
    int ans = 0;
    for(int i = 0; i < 32; i++) {
        if(bin[i] % M == 0) {
            continue;
        }
        // 模的值必须为 K 才满足条件，如果不满足就返回一个 -1
        if(bin[i] % M == K) {
            // 将 ans 的 i 位置设置为1
            ans |= (1 << i);
        }else {
            return -1;
        }
    }
    return ans;
}

示例代码：

public static void main(String args[]) {
    int[] arr = {1, 1, 1, 9, 9, 3, 3, 3, 4, 4, 4};
    System.out.println(onlyKTimes(arr,2,3));
}
// 结果为：9