算法学习笔记（二）异或运算^及应用

一. 基本概念与运算规则

(1) 异或运算符^：基本规则是将两个数转化为二进制的数进行比较，相同为0不同为1。按照左神的讲解，可以简单记作“无进位相加”，这样对运算规则的理解也有帮助。假设两个二进制数为“1011100”和“0111010”，那么经过异或运算后，得到“1100110”，和基本相加但是不考虑进位的结果相同。

(2) 运算规律：满足交换律和结合律。(后两个规律用无进位相加理解就变得容易了。)

a^b = b^a;

a ^ (b^c) = (a^b) ^c;

0^N = N;

N^N = 0;

二. 应用场景

(1) 假如有”int a = 甲; int b = 乙;” 如何在不申请任何新变量的情况下使得两个变量的数字交换呢？只需要执行以下三步：

1
2
3

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

执行完第一步： b = 乙； a = 甲^乙；

执行完第二步： a = 甲^乙； b = 甲^乙^乙 = 甲^(乙^乙) = 甲^0 = 甲；

执行完第三部： b = 甲； a = 甲^乙^甲 = （甲^甲）^ 乙 = 0^乙 = 乙；

这样就实现了两者的交换。

需要注意的是，异或运算比正常的加减乘除运算快，但是必须当a和b两者指向的是不同区域时才能使用。两者的值可以相等，但在内存上必须时独立的两块。

（2）假设在一个数组中，只有一种数出现了奇数次，其他所有的数都出现了偶数次，如何在保证时间复杂度为O(N)，空间复杂度为O(1)的情况下，找到这个出现了奇数次的数？

写一个实际的数组辅助理解： {1,2,1,4,1,3,1,3,2}，可以看出4出现了奇数次，其他数字都出现偶数次，要求找到的就是这个4。方法是设置一个变量，用这个变量从头异或到尾，结束后这个变量的值就是要找的数。

因为异或运算满足交换律，所以各个数的位置不会产生影响。如果一个数出现了偶数次，根据”N^N = 0“, 所有出现偶数次的数的运算结果为0；”0^N = N“，那么最后变量的值正是出现了奇数次的要找的值。

Java

public class Test {
    
    public static void oddTimesNum1(int[] arr) {
        int r = 0;
        for(int i=0; i<arr.length; i++) {
            r = r^arr[i];
        }
        System.out.println(r); 
    }
    
    public static void main(String[] args) {
        // 4出现奇数次，其余数字出现偶数次
        int[] a = {1,2,1,4,1,3,1,3,2};
        oddTimesNum1(a);
    }
    
}

JavaScript

var a =[1,2,1,4,1,3,1,3,2];
   oddTimesNum1(a);

   function oddTimesNum1(arr){
     var r = 0;
     for(var i=0; i<arr.length; i++){
       r = r^arr[i];
     }
     console.log(r);
   }

（3）假设在一个数组中，有两种数出现了奇数次，其他所有的数都出现了偶数次，如何在保证时间复杂度为O(N)，空间复杂度为O(1)的情况下，找到这两个出现了奇数次的数？

将数组中出现了奇数次的两个数记作a和b，同样设置一个变量，记作r，用这个变量从头异或到尾，那么结束后，这个变量的值就是： a^b。因为两种数出现了奇数次，所以a和b的值一定不相等，那么这个变量的值不会为0。假设这个变量在k位上的值位1，也就意味着a和b在k位上是不同的，根据这一点可以帮助区分开a和b。只需要找到一个k位即可，方便起见，就提取变量出现1的最右面一位为k位。

问题现在转化为如何提取这个变量中最右面的1的位置。这里还用到了位运算符的非（~）和与（&）。非（~）运算符表示按位取反每一位，0变为1，1变为0；与（&）运算符表示该位同时为1时取1，否则为0。假设这个变量r此时的二进制表示为：10101110000，那么~r的值为：01010001111，~r+1的值为01010010000， r&(~r+1)的值就是00000010000，这样就找到了最右面的1出现的位置。r&(~r+1)是常用的方式，可以记下来。

找到之后设置第二个变量，记作r2，只将k位为1的数异或到这个新变量上来。那么r2的值就是a和b的其中一个（其他k位可能为1的数出现了偶数次，又变成0）。然后计算r ^ r2，此时就也得到了另一个数。

Java

public class Test {
    
    public static void oddTimesNum2(int[] arr) {
        int r = 0, rHasOne = 0;
        for(int i:arr) {
            // 假设出现了奇数次的两个数是a b,此时r = a^b
            r ^= i;
        }
        int rightOne = r & (~r+1);
        for(int i:arr) {
            if((i & rightOne) != 0) {
                // rHasOne里面存有a或b
                rHasOne ^= i;
            }
        }
        int rOtherOne = r^rHasOne;
        System.out.println(rHasOne + " " + rOtherOne);
    }
    
    public static void main(String[] args) {
        // 2，3出现奇数次，其余数字出现偶数次
        int[] a = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 4};
        oddTimesNum2(a);
    }
    
}

JavaScript

var a =[4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 4];
   oddTimesNum2(a);

   function oddTimesNum2(arr){
     var r = 0, rHasOne = 0;
     for(var i=0; i<arr.length; i++){
       r ^= arr[i];
     }
     var rightOne = r & (~r + 1);
     for(var i=0; i<arr.length; i++){
       if((arr[i]&rightOne) != 0){
         rHasOne ^= arr[i];
       }
     }
     var rOtherOne = r ^ rHasOne;
     console.log(rHasOne + " " + rOtherOne);
   }