数组异或操作

题目：

给你两个整数，n 和 start 。

数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。

请返回 nums 中所有元素按位异或（XOR）后得到的结果

示例 ：

输入：n = 5, start = 0
输出：8
解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
     "^" 为按位异或 XOR 运算符。

题目来源：力扣1486

题解：

暴力法：

枚举 i=0,1,2,…,n−1，计算 start+2i 的异或和。（过于简单，重点讲解数学法）

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

数学法：

背景知识：

记 ⊕ 为异或运算，异或运算有以下性质：

1.x⊕x=0
2.x⊕y=y⊕x
3.(x⊕y)⊕z=x⊕(y⊕z)
4.x⊕y⊕y=x
5.对于任意的 i 属于整数，有 2i⊕(2i+1)⊕(2i+2)⊕(2i+3)=0

关于第五条的解释：

当 i 为偶数时：由于 2i 和 2i+1 只有最低位不同，所以 2i ⊕ (2i+1) = 00001₍₂₎ = 1，然后利用结合律（第三条）将原式化为 (2i⊕(2i+1)) ⊕ ((2i+2)⊕(2i+3)) = 1 ⊕ 1 = 0。

start是偶数：

如果start是偶数，那么nums[i]也为偶数，例如 n=5, start=0，即 0，2，4，6，8

由于这些数二进制最低位都为0，所以可以将这些数右移一位（除以2），然后计算异或和，再把异或和左移一位（乘以2）就得到了答案：

0⊕2⊕4⊕6⊕8=(0⊕1⊕2⊕3⊕4)⋅2=4⋅2=8

start是奇数：

如果start是奇数，那么nums[i]也为奇数，例如 n=5, start=3，即3，5，7，9，11。

分两部分计算答案：

最低位：因为所有数最低为都为 1 ，所以答案最低位取决于有多少个 1 ，如果有奇数个 1 那么异或和是 1，偶数个 1 那么异或和为 0。

除最低位的其余位：先把这些数右移一位（除以2），然后计算异或和，再把异或和左移一位（乘以2），最后加上最低位就得到最后的答案：

3⊕5⊕7⊕9⊕11=(1⊕2⊕3⊕4⊕5)⋅2+1=1⋅2+1=3

合二为一：

无论 start 是偶数还是奇数，都可以用同一个规则计算。

设 a=⌊2/start​⌋，b 为异或和的最低位。只有 n 和 start 都为奇数时 b=1，其余情况 b=0。那么异或和等于

start⊕(start + 2*1)⊕(start + 2*2)⊕(start + 2*3)⊕···⊕(start + 2*(n-1))右移一位得(start/2)⊕(start/2 + 1)⊕(start/2 + 2)⊕(start/2 + 3)⊕···⊕(start/2 + (n-1))，再左移加上最低位得(start/2)⊕(start/2 + 1)⊕(start/2 + 2)⊕(start/2 + 3)⊕···⊕(start/2 + (n-1)) *2 + b = a⊕(a + 1)⊕(a + 2)⊕(a + 3)⊕···⊕(a + (n-1)) + b

由第四条定律得a⊕(a + 1)⊕(a + 2)⊕(a + 3)⊕···⊕(a + (n-1)) = (0⊕1⊕2⊕···⊕(a-1)) ⊕ (0⊕1⊕2⊕··· ⊕ (a-1)⊕a⊕(a+1)⊕(a+2) ⊕ ··· ⊕ (a+(n-1))

按照 n 模 4 的结果分类，去计算 0 到 n 的异或和：

• 当 n = 4k + 1 (例如1，5，9)时，两个数一组一共有(4k + 1 + 1) / 2 =2k + 1组，所以有奇数个1，答案为1。
• 当 n = 4k + 2 (例如2，6，10)，答案为(0⊕1⊕2⊕···⊕4k+1)⊕4k + 2 = 1 ⊕ (4k + 2) = 4k + 2 + 1 = 4k + 3 = n + 1。
• 当 n = 4k + 3 (例如3，7，11)，两个为一组一共有(4k+3+1)/2 = 2k + 2组，有偶数个1，答案为0。
• 当 n = 4k + 4 (例如4，8，12)时，答案为(0⊕1⊕2⊕···⊕4k+3) ⊕ 4k + 4 = 0 ⊕ 4k + 4 = 4k + 4 = n。

综上所述：

class Solution {
    int xor_n(int n) {
        switch (n % 4) {
            case 0: return n;
            case 1: return 1;
            case 2: return n + 1;
            default: return 0;
        }
    }
}

public:
    int xorOperation(int n, int start) {
        int a = start / 2;
        int b = n & start & 1; // 都为奇数才是 1
        return (xor_n(a + n - 1) ^ xor_n(a - 1)) * 2 + b;
    }
};

复杂度分析

• 时间复杂度：O(1)。
• 空间复杂度：O(1)。