1486. 数组异或操作
题目描述
给你两个整数，n 和 start 。
数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。
请返回 nums 中所有元素按位异或（XOR）后得到的结果。
示例
示例 1：
输入：n = 5, start = 0
输出：8
解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
"^" 为按位异或 XOR 运算符。
示例 2：
输入：n = 4, start = 3
输出：8
解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.
示例 3：
输入：n = 1, start = 7
输出：7
示例 4：
输入：n = 10, start = 5
输出：2
数据范围
1 <= n <= 1000
0 <= start <= 1000
n == nums.length
分析
第一种解法
第一种解法是模拟，直接用for循环遍历模拟异或操作
public int xorOperation(int n, int start) {
int ans = 0;
for (int i = 0; i < n; i++) {
ans ^= (start + 2 * i);
}
return ans;
}
第二种解法 数学
第一种解法中在当前题目所给的数据范围是可以的，一旦数据范围出到108，大概率会发生TLE超时，事实上，本题存在数据规律解法。
异或运算满足以下性质：
- \[{x⊕x = 0} \]
- \[{x⊕y = y⊕x} \]
- \[{(x⊕y)⊕z = x⊕(y⊕z)} \]
- \[{x⊕y⊕y = x} \]
- \[{∀i∈Z，有 4i⊕(4i+1)⊕(4i+2)⊕(4i+3)=0} \]
在本题中，我们需要计算的式子为：
\[start⊕(start + 2)⊕(start + 4)⊕...⊕(start + 2(n - 1)) \]观察原式，可以发现，每一个数列中的数奇偶性都是一样的，那么可以得知，数列中的每一个数的最低位或者都为0，或者都为1，由此可以把数列里每一个数的二进制位的最低位都单独拎出来处理，可以得到以下几种情况：
- n为奇数，start为偶数：偶数个奇数做异或，计算结果二进制最低位为0
- n为奇数，start为奇数：start-1个奇数做异或，计算结果二进制最低位为0，在和奇数做异或，最终结果的二进制最低位为1
- n为偶数，start为偶数：偶数个偶数做异或，计算结果二进制最低位为0
- n为偶数，start为奇数：start-1个偶数做异或，计算结果二进制最低位为0，在和偶数做异或，最终结果的二进制最低位为0
可以得到，当且仅当start和n都为奇数时，计算结果二进制的最低为才为1，即
\[最低位运算结果 = n⊕start⊕1 \]继续观察该式子可以发现，式子的差值为2，第五条性质需要数是连续的，结合数列的奇偶性，考虑把计算式子除以2（右移一位），即
\[\frac{1}{2}start⊕(\frac{1}{2}start + 1)⊕(\frac{1}{2}start + 2)⊕...⊕(\frac{1}{2}start + n - 1) \]l令$${s = \frac{1}{2}start}$$，可得一个连续的数列
\[s⊕(s + 1)⊕(s + 2)⊕...⊕(s + n - 1) \]综上，最终所求式子需要在连续数列的基础上乘以2（左移一位）并把单独处理的最低位结果加回去，e表示最低位
\[(s⊕(s + 1)⊕(s + 2)⊕...⊕(s + n - 1)) * 2 + e \]这里需要注意：
异或运算中每一位都是单独运算，右移不会影响移动部分的计算结果
对一串连续的整数数列，如$${}$$$${0⊕1⊕2⊕...⊕x}$$，根据第五条性质，可以得到
- 当x = 4k时，数列长度为x+1，即4k+1，根据性质5可得每四个数字的异或计算结果为0，所以只剩下一个x，即$${}$$$${0⊕x = x}$$；
- 当x = 4k + 1时，根据性质5，此时还剩下两位，即$${x⊕(x-1)⊕0}$$，即$${(4k + 1)⊕4k}$$，观察可以看出两个数仅仅是最后一位不同，例如4和5、8和9，异或结果为1；
- 当x = 4k + 2时，即$${x⊕(x-1)⊕(x - 2)⊕0 ==> x⊕1 ==> (4k + 2)⊕1 ==> 4k + 2 + 1 ==> x+1}$$，从另一个角度看，x%4 == 2说明x一定是个偶数，偶数的最低位是0，因为$${4k⊕(4k+1) = 1}$$，并且n^1 = n+1，所以$${x⊕(x-1)⊕(x - 2)⊕0 ==> x⊕1 ==> x + 1}$$；
- 当x = 4k + 3时，即$${x⊕(x-1)⊕(x - 2)⊕(x - 3)⊕0}$$，由以上推断可以得知$${(x-1)⊕(x - 2)⊕(x - 3) = x + 1}$$，x+1刚好等于当前的x，即$${x⊕x = 0}$$，所以结果为0。
综上，可得表示$${0⊕1⊕2⊕...⊕x}$$的函数$${sumXor(x)}$$
\[sumXor(x) = \begin{cases} x, &x = 4k,k∈Z\\ (x−1)⊕x, &x = 4k + 1,k∈Z\\ (x−2)⊕(x−1)⊕x, &x = 4k + 2,k∈Z\\ (x−3)⊕(x−2)⊕(x−1)⊕x, &x = 4k + 3,k∈Z\\ \end{cases} \]进一步化简，可得
\[sumXor(x) = \begin{cases} x, &x = 4k,k∈Z\\ 1, &x = 4k + 1,k∈Z\\ x+1, &x = 4k + 2,k∈Z\\ 0, &x = 4k + 3,k∈Z\\ \end{cases} \]根据异或运算第四条性质$${x⊕y⊕y = x}$$，假设$${y = sumXor(s-1)}$$，表示数列从0到s-1的异或结果，x是我们需要的结果，即数列从s到s+n-1的异或结果
显然，$${x⊕y = sumXor(s + n - 1)}$$，所以$${x⊕y⊕y = sumXor(s + n - 1)⊕sumXor(s-1)}$$
这样最后的结果可以表示为
\[(sumXor(s + n - 1)⊕sumXor(s-1)) * 2 + e \]代码
public class Solution {
public int xorOperation(int n, int start) {
int s = start >> 1;
int e = n & start & 1;
int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
s
return ret << 1 | e;
}
public int sumXor(int x) {
if (x % 4 == 0) {
return x;
} else if (x % 4 == 1){
return 1;
} else if (x % 4 == 2) {
return x + 1;
} else {
return 0;
}
}
}