对异或印象最深刻的记忆还是大一下的数字逻辑课，可那时仅仅知道不同为1，最近又学到了异或运算，故作此文。

下面列出几个异或的常见性质

  1. 异或可以理解为无进位相加
  2. 满足交换律和结合律
  3. a^a = 0 ,a^0 = a
  4. 如果a^b = c ① ,那么 b = a^c ② a = b^c
    以下是第四条性质的证明
    ① 两边同时异或 a,即可得到②（难以想象我当时为什么想了那么久）

交换两个数

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

交换逻辑是上述第三点性质，值得注意的是，交换的两个值应该是内存中两块不一样的内存，所以在数组中，不能出现同一个值用这种方法比较

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//返回一个数的符号位
    public static int sign(int n){
       return flip(n << 31);
    }
    //0变1，1变0
    public static int flip(int n){
        return n ^ 1;
    }
    //有溢出风险
    public static int getMax1(int a,int b){
        int c = a - b;
        //c 非负 returnA -> 1 returnB -> 0
        //c  负 returnA -> 0 returnB -> 1
        int returnA = sign(c);
        int returnB = flip(returnA);
        return a * returnA +  b * returnB;
    }
    public static int getMax2(int a,int b){
        int c = a - b;
        int sa = sign(a);
        int sb = sign(b);
        int sc = sign(c);
        int diffAB = sa ^ sb;//a b符号位不同，diffAB -> 1
        int sameAB = flip(diffAB);
        /*
           返回a的条件
           ab符号位不同，且a为正数
           ab符号位相同，且c为正数
         */
        int returnA = diffAB * sa + sameAB * sc;
        int returnB = flip(returnA);
        return a * returnA +  b * returnB;
    }

找到缺失的数字

268. 丢失的数字
依据上面提到的第四条性质解答

1
2
3
4
5
6
7
8
9
10
11
12
public int missingNumber(int[] nums) {
        //eorAll,0-n所有数字的异或
        //eorHas,数组中所有元素的异或
        //二者异或即可找到缺失的数字
        int eorAll = 0,eorHas = 0;
        for(int i = 0;i < nums.length  ;i++ ){
            eorAll ^= i;
            eorHas ^= nums[i];
        }
        eorAll ^= nums.length;
        return eorAll ^ eorHas;
    }

数组中1个数出现了奇数次，而其他数都出现了偶数次，返回出现了奇数次的数

只出现一次的数字
本解法适用于一个数出现偶数次，其他数出现奇数次的情况

1
2
3
4
5
6
7
public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i = 0 ;i < nums.length ; i++){
            ans ^= nums[i];
        }
        return ans;
    }

数组中2个数出现了奇数次，而其他数都出现了偶数次，返回这两个出现了奇数次的数

260. 只出现一次的数字 III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] singleNumber(int[] nums) {
        int eor1 = 0,eor2 = 0;
        for(int i = 0;i < nums.length;i++){
            //eor1 出现奇数次的两个数的异或
            eor1 ^= nums[i];
        }
        //提取出一个数最右侧的1
        int rightone = eor1 & (-eor1);
        //将所有数分为在这个位置上是1和不是1的两部分，那两个出现奇数次的数必定在不同的两部分
        for(int num : nums){
            //注意比较运算符 == 的优先级高于 位与运算符 &
            if((num & rightone) == 0){
                eor2 ^= num;
            }
        }
        return new int[] {eor2,(eor1 ^ eor2)};
    }

数组中只有一个数的出现次数小于m次，其他数出现次数都等于m次，返回这个出现次数小于m次的数

137. 只出现一次的数字 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int singleNumber(int[] nums) {
        return find(nums,3);
    }
    public int find(int[] nums ,int m){
        //cnts 存储每个位置上有多少个1
        //cnts[0] 0位置上有多少个1
        int[] cnts = new int[32];
        for(int num : nums){
            for(int i = 0;i < 32;i++){
                cnts[i] += (num >> i) & 1;
            }
        } 
        int ans = 0;
        for(int i = 0;i < 32;i++){
        //如果有一个位置的1不是m的整数倍，那在这个位置小于m次的数的值必定为1
            if((cnts[i] % m) != 0 ){
               ans |= (1 << i);
            }
        }
        return ans;
    }