异或运算

Contents

1. 1. 运算法则
2. 2. 异或的规律
3. 3. 异或的用途
   1. 3.1. 交换变量的值
   2. 3.2. 加密解密
   3. 3.3. 求不重复的数
   4. 3.4. 求缺失的数

今天来聊一下二进制的异或运算。

运算法则

异或是一种神奇的位运算，运算符用^来表示，运算法则是二进制数值相同返回0，不同返回1：

1^1 = 0
1^0 = 1
0^0 = 0

异或的规律

异或运算有以下四种运算规律：

1. 一个数值与自身异或，其结果是0。 例如 1^1=0，2^2=0，12^12=0。
2. 数值与0进行异或，一定等于它自己。例如 1^0=1，2^0=2，12^0=12，198^0=198。
3. 交换定律，也是计算顺序无关定律。例如 1^2^3^4=1^4^3^2=2^1^4^3=3^1^4^2。
4. 自反律，这个其实第一个定律与第二个定律的组合。例如125^12^12=125^(12^12)=125^0=125。

异或的用途

根据异或运算规律，在计算机算法中会有很多的用途，如果我们去看一些公司的笔试或者面试的算法，会发现有很多和异或相关的算法题。

交换变量的值

最常见的一个应用是使用异或的自反律可以不需要额外的空间实现两个变量的数值交换。

int a = 123;
int b = 234;
a ^= b; //123 ^ 234
b ^= a; // 234 ^ 123 ^ 234 = 123 ^ 234 ^ 234 = 123 ^ 0 = 123
a ^= b; //123 ^ 234 ^ 123 = 234 ^ 123 ^ 123 = 234 ^ 0 = 234

加密解密

另一个常见的自反律的应用是对数值进行加密和解密：

1. 假设有一个原始数值是x
2. 设置一个加密的密钥，也是一个数值，设为y
3. 加密过程是x^y = z，输出的z是加密后的数值。
4. 解密过程是z^y = x^y^y = x^0=x;

有一个简单的的算法题：数组arr包含n个非负整数，经过异或加密后形成一个新的数组encoded，加密规则是encoded[i]=arr[i] ^ arr[i+1]。例如arr = [1,0,2,1]，加密后就变成了encoded=[1,2,3]。给出原始数组的第一位数，要求你通过加密后的数组反推出原始的数组。求解步骤如下：

1. encoded[i] = arr[i] ^ arr[i+1]
2. 两边都和arr[i]异或得到encoded[i] ^ arr[i] = arr[i] ^ arr[i+1] ^ arr[i]
3. 通过异或定律计算 encoded[i] ^ arr[i] = arr[i+1] ^ arr[i] ^ arr[i] = arr[i+1]
4. 也就是arr[i+1] = encoded[i] ^ arr[i]， 也就是arr[i] = encoded[i-1] & arr[i-1]
5. 我们已经知道了arr[0]，那么就可以依次计算出arr[1],arr[2]…

public int[] decode(int[] encoded, int first) {
    int[] arr = new int[encoded.length + 1];
    arr[0] = first;
    for(int i = 1; i< encoded.length; i++){
        arr[i] = arr[i-1] ^ encoded[i-1];
    }
    arr[arr.length - 1] = arr[arr.length - 2] ^ encoded[encoded.length - 1];
    return arr;
}

求不重复的数

一个简单的算法题，有一个数组，数组里面的元素出了n以外，都出现了两次 （只有n出现了一次），求出这个n。这是一个典型的异或算法题，把数组里面的数值做异或，出现两次的会因为异或规律1而被约掉，那么最后剩下的那个数值就是只出现了一次的数。

int[] input = {1,4,2,3,1,4,3};
int rs = input[0];
for(int i = 1; i< input.length; i++){
    rs ^= input[i];
}
// 1^4^2^3^1^4^3 = 1^1^2^3^3^4^4=0^2^0^0=2
return rs;

求缺失的数

一个数组的长度是n-1，其中的元素是1到n的不重复整数但是缺少一个，求缺少的数字。这个算法题目和上面的类似，为了求缺少的数，我们需要把存在的数通过异或定律约掉。例如，给出的数组是{1，3，4，5}，先求所有的元素的异或1^3^4^5，然后再和完整的1^2^3^4^5进行异或，剩下的数就是缺少的数。

1^3^4^5 ^ 1^2^3^4^5 = 1^1 ^ 2 ^ 3^3 ^ 4^4 ^ 5^5 = 0^2^0^0^0 = 2

int fun(int[] input){
    int rs = 0;
    for(int i : input){
        rs ^= i;
    }
    for(int i = 1; i <= n; i++){
        rs ^= i;
    }
    return rs;
}

这个算法有另外一个版本，就是数组长度为 n+1， 其中的仅有一个数值重复，需要求出这个数值。做法和上面的一样。