异或运算的性质#

异或运算就是无进位相加
异或运算满足交换律、结合律，也就是同一批数字，不管异或顺序是什么，最终结果都是一样的
0 ^ n = n，n ^ n = 0
整体异或和如果是 x，整体中某个部分的异或和如果是 y，那么剩下部分的异或和是 x ^ y

这些结论里最重要的是第 1 条，其他结论都可以由它推导得到。
其中第 4 条相关题目最多，核心在于利用区间上异或和的性质。

1. 不用任何判断语句和比较操作，返回两个数的最大值#

1
// 必须保证n一定是0或者1
2
// 0变1，1变0
3
public static int flip(int n) {
4
    return n ^ 1;
5
}
6

7
// 非负数返回1
8
// 负数返回0
9
public static int sign(int n) {
10
    return flip(n >>> 31);
11
}
12

13
// 有溢出风险的实现
14
public static int getMax1(int a, int b) {
15
    int c = a - b;
16
    // c非负，returnA -> 1
17
    // c非负，returnB -> 0
18
    // c负数，returnA -> 0
19
    // c负数，returnB -> 1
20
    int returnA = sign(c);
21
    int returnB = flip(returnA);
22
    return a * returnA + b * returnB;
23
}
24

25
// 没有任何问题的实现
26
public static int getMax2(int a, int b) {
27
    // c可能是溢出的
28
    int c = a - b;
29
    // a的符号
30
    int sa = sign(a);
31
    // b的符号
32
    int sb = sign(b);
33
    // c的符号
34
    int sc = sign(c);
35
    // 判断A和B，符号是不是不一样，如果不一样diffAB=1，如果一样diffAB=0
36
    int diffAB = sa ^ sb;
37
    // 判断A和B，符号是不是一样，如果一样sameAB=1，如果不一样sameAB=0
38
    int sameAB = flip(diffAB);
39
    int returnA = diffAB * sa + sameAB * sc;
40
    int returnB = flip(returnA);
41
    return a * returnA + b * returnB;
42
}

2. 找到缺失的数字#

题目链接：https://leetcode.cn/problems/missing-number/

1
public static int missingNumber(int[] nums) {
2
    int eorAll = 0, eorHas = 0;
3
    for (int i = 0; i < nums.length; i++) {
4
        eorAll ^= i;
5
        eorHas ^= nums[i];
6
    }
7
    eorAll ^= nums.length;
8
    return eorAll ^ eorHas;
9
}

3. 数组中有 2 种数出现了奇数次，其他的数都出现了偶数次，返回这 2 种出现了奇数次的数#

题目链接：https://leetcode.cn/problems/single-number-iii/

1
public static int[] singleNumber(int[] nums) {
2
    int eor1 = 0;
3
    for (int num : nums) {
4
        // nums中有2种数a、b出现了奇数次，其他的数都出现了偶数次
5
        eor1 ^= num;
6
    }
7
    // eor1 : a ^ b
8

9
    // Brian Kernighan算法
10
    // 提取出二进制里最右侧的1
11
    int rightOne = eor1 & (-eor1);
12

13
    int eor2 = 0;
14
    for (int num : nums) {
15
        if ((num & rightOne) == 0) {
16
            eor2 ^= num;
17
        }
18
    }
19
    return new int[] { eor2, eor1 ^ eor2 };
20
}

4. 数组中只有 1 种数出现次数少于 m 次，其他数都出现了 m 次，返回出现次数小于 m 次的那种数#

题目链接：https://leetcode.cn/problems/single-number-ii/

1
public static int singleNumber(int[] nums) {
2
    return find(nums, 3);
3
}
4

5
// 更通用的方法
6
// 已知数组中只有1种数出现次数少于m次，其他数都出现了m次
7
// 返回出现次数小于m次的那种数
8
public static int find(int[] arr, int m) {
9
    // cnts[0] : 0位上有多少个1
10
    // cnts[i] : i位上有多少个1
11
    // cnts[31] : 31位上有多少个1
12
    int[] cnts = new int[32];
13
    for (int num : arr) {
14
        for (int i = 0; i < 32; i++) {
15
            cnts[i] += (num >> i) & 1;
16
        }
17
    }
18
    int ans = 0;
19
    for (int i = 0; i < 32; i++) {
20
        if (cnts[i] % m != 0) {
21
            ans |= 1 << i;
22
        }
23
    }
24
    return ans;
25
}