位运算 -- 力扣

1486. 数组异或操作

1486. 数组异或操作
根据题意，使用参数 n 和 start 生成一个数组，最后返回数组中所有元素按位异或（XOR）后得到的结果。

首先，异或运算的规则是，当同一位的二进制数不同时结果为 1，否则为 0，比如 $101\oplus 111=010$。
它有以下相关的性质：

1. $x\oplus x=0$；
2. $x\oplus 0=x$；
3. $x\oplus y=y\oplus x$；
4. $(x\oplus y)\oplus z=x\oplus (y\oplus z)$；
5. $x\oplus y\oplus y=x$；
6. $\forall i\in Z$，$4i\oplus (4i+1)\oplus (4i+2)\oplus (4i+5)=0$；
7. 当一个奇数和一个偶数进行异或运算时，结果的最低位一定是 1，比如 2 和 3。

额外的，如果 x 是偶数，$x\oplus 1=x+1$；如果 x 是奇数，$x\oplus 1=x-1$。比如 $6\oplus 1=110\oplus 001=111=7$，$5\oplus 1=101\oplus 001=100=4$。

在本题中，我们需要计算 $$start\oplus (start+2)\oplus (start+4)\oplus \cdots \oplus (start+2(n-1))\text{\hspace{1em}(1)}$$
观察公式可以知道，这些数的奇偶性相同，因此它们的二进制表示中的最低位要么均为 1，要么均为 0。
于是我们可以把参与运算的数的二进制位的最低位提取出来单独处理。当且仅当 start 为奇数，且 n 也为奇数时，结果的二进制位的最低位才为 1，因此最低位 e 为 e = 1 & n & start。

当 n = 4 时，start = 2，nums=[2, 4, 6, 8]，最低位 e 为 0；
当 n = 4 时，start = 1，nums=[1, 3, 5, 7]，最低位 e 为 0，原因：两个奇数进行异或操作结果为 0，因此偶数个奇数的最低位为 0；
当 n = 3 时，start = 1，nums=[1, 3, 5]，最低位 e 为 1，原因：$0\oplus 1=1$。

此时我们可以将公式转化为 $$(s\oplus (s+1)\oplus (s+2)\oplus \cdots \oplus (s+n-1))\times 2+e\text{\hspace{1em}(2)}$$ 其中 $s=\lfloor \frac{start}{2}\rfloor$，$e$ 表示运算结果的最低位。舍去最低位后的数列恰成为一串连续的整数。

首先，将所有参与异或的元素都删除最后一位，即为右移一位，$\frac{start}{2}\oplus \frac{start+2}{2}\oplus \frac{start+4}{2}\oplus ...\oplus \frac{start+2(n-1)}{2}=\frac{start}{2}\oplus (\frac{start}{2}+1)\oplus (\frac{start}{2}+2)\oplus \cdots \oplus (\frac{start}{2}+n-1)$
然后，用上面得到的结果乘于 2，相当于左移一位，再加上最后一位值 e，使用 $s$ 代替 $\frac{start}{2}$，因此公式(1) 变为：$(s\oplus (s+1)\oplus (s+2)\oplus \cdots \oplus (s+n-1))\times 2+e$。

这样我们可以描述一个函数 $sumXor(x)$，表示 $0\oplus 1\oplus 2\oplus \cdots \oplus x$。利用异或运算的性质 6，我们可以将计算该函数的复杂度降低到 O(1)，因为以 $4i$ 为开头的连续四个整数异或的结果为 0，所以 $sumXor(x)$ 可以被表示为：

化简后的形式：

当 x = 4k 时，元素有 [0, 1, 2, …, 4k]，因为前面的 [0,1, 2, …, 4k-1] 的异或操作的结果为 0，最后只剩下元素 x=4k；
当 x = 4k+1 时，剩下的元素有 $(x-1)\oplus x$，根据上面性质7，这个化简后的结果为 1；
当 x = 4k+2 时，剩下的元素有 $(x-2)\oplus (x-1)\oplus x=1\oplus (4k+2)=x\oplus 1=x+1$，其中 $x$ 是偶数；
当 x = 4k+3 时，剩下的元素有 $(x-3)\oplus (x-2)\oplus (x-1)\oplus x$，其中 $(x-3)\oplus (x-2)=(x-1)\oplus x=0$，参考上面性质7。
…
“以 $4i$ 为开头的连续四个整数异或的结果为 0” ：连续四个整数的异或结果为 0，即为 $k\oplus (k+1)\oplus (k+2)\oplus (k+3)=0$，所以以 4 的倍数为起点（即 $k=4i$）的四个连续整数的异或结果也为 0。这个性质使得我们在处理长度为 4 的一组数时，不需要逐一计算它们的异或结果，而是直接知道它们的异或为 0，将问题的规模大幅缩小。

根据公式 (2)，我们需要计算出[s, s+1, …, s+n-1] 这个范围的异或结果，设这个结果为 $x$。
显然 $sumXor(s-1)\oplus x=sumXor(s+n-1)$。根据性质 3 和 5 可得出 $x=sumXor(s-1)\oplus sumXor(s+n-1)$，其中 $sumXor(s+n-1)$ 表示从 0 到 s+n−1 的所有元素的异或结果。

流程：
① 计算参与运算的数的二进制位的最低位的值 e；
② 计算 $s=\lfloor \frac{start}{2}\rfloor$；
③ 分别计算 $sumXor(s+n-1)$ 和 $sumXor(s-1)$，再对这两个结果进行异或操作得到 ret；
④ 计算 ret * 2 + e 。

class Solution {
public:
    int xor_n(int n) {
        switch (n % 4) {
            case 0: return n;
            case 1: return 1;
            case 2: return n+1;
            default: return 0;
        }
    }
    int xorOperation(int n, int start) {
        int e = 1 & n & start, s = start / 2;
        int ret = xor_n(s-1) ^ xor_n(s + n - 1);
        return ret * 2 + e;
    }
};

var xorOperation = function(n, start) {
    const xor_n = (num) => {
        switch(num % 4) {  
            case 0: return num;   // 4k % 4 = 0
            case 1: return 1;
            case 2: return num+1;
            default: return 0;
        }
    }
    const e = 1 & n & start, s = start >> 1;  
    const ret = xor_n(s-1) ^ xor_n(s+n-1);
    return ret * 2 + e;
};