前置知识

Java中异或是以二进制数据为基础进行运算的，即当使用到异或运算时，都会先将两个运算数转换成二进制数据后，再进行异或运算

• 运算规则：两个操作数的同位中，如果值相同（都是 0 或者都是 1）则为 0，不同（一个是 0，一个是 1）则为 1

异或运算的基本定理

1. 异或满足结合律：(a^b)^c = a^(b^c)
2. 异或满足交换律：a^b = b^a
3. 任意数与自身异或得：a^a = 0
4. 任意数异或0的到自身：a^0 = a

两数交换

需求：a = 2，b = 3，在不用中间变量的基础上进行交换a和b的值，使得 a = 3，b = 2

public class Test {
    public static void main(String[] args) {
        int a = 2;
        int b = 3;
        System.out.printf("交换前：a = %s,b = %s \n",a,b);//交换前：a = 2,b = 3 
        //使用异或的方式进行两数交换
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;

        System.out.printf("交换后：a = %s,b = %s",a,b);//交换后：a = 3,b = 2
    }
}

解析：

• 以二进制数据为基础进行运算解析
  • a = 2，则二进制数为 10。b = 3， ，则二进制数为 11
  • a = a ^ b = 10 ^ 11 = 01
  • b = a ^ b = 01 ^ 11 = 10 = 2
  • a = a ^ b = 01 ^ 10 = 11 = 3
•  异或运算的基本定理解析
  • a = a ^ b
  • b = a ^ b = a ^ b ^ b = a = 2
  • a = a ^ b = a ^ a ^ b = b = 3

 解码异或后的数组

未知 整数数组 arr 由 n 个非负整数组成。经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1]

例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]），请解码返回原数组 arr (可以证明答案存在并且是唯一的)

示例 1：

输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 ^ 0, 0 ^ 2, 2 ^ 1] = [1,2,3]

示例 2：

输入：encoded = [6,2,7,3], first = 4
输出：[4,2,0,7,4]

解题思路：a^b = c ， a^b^b = a， 即 c^b=a 同理 c^a =b

public int[] decode(int[] encoded, int first) {

    if(encoded == null || encoded.length == 0){
        return null;
    }

    int[] ans = new int[encoded.length + 1];
    ans[0] = first;
    for(int i = 1; i < ans.length; i++){
        ans[i] = encoded[i - 1] ^ ans[i - 1];
    }

    return ans;
}