夯实算法-数组异或操作

题目：LeetCode

给你两个整数，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

解题思路

利用按位异或的性质，可以使用 O(1) 的时间得到结果。

根据按位异或的性质，对于二进制表示中的特定位，如果该位出现奇数个 1 则按位异或的结果是 1，如果该位出现偶数个 1 则按位异或的结果是 0。

由于数组 nums 中的任意两个相邻元素之差都是 2，因此数组 nums 中的所有元素的奇偶性相同。

• 只有当 n 和 start 都是奇数时，按位异或的结果才是奇数，否则按位异或的结果是偶数。将一个奇数减 11 的效果是将该奇数的二进制表示的最低位 1 变成 0，其余位不变。
• 如果数组 nums 中的所有元素都是奇数，则数组 nums 中的所有元素按位异或的结果（「数组按位异或结果」）可以通过如下方式计算：将数组 nums 中的所有元素减 1，得到 n 个偶数，计算这 n 个偶数的按位异或结果，记为 x，如果 n 和 start 都是奇数则数组按位异或结果为 x+1，否则数组按位异或结果为 x。

代码实现

public int xorOperation(int n, int start) {
    int odd = n & start & 1;
    start -= start & 1;
    return getPrefixXor(start + 2 * (n - 1)) ^ getPrefixXor(start - 2) + odd;
}

public int getPrefixXor(int num) {
    if (num <= 0) {
        return 0;
    }
    int remainder = num % 8;
    if (remainder == 0) {
        return num;
    } else if (remainder == 2) {
        return 2;
    } else if (remainder == 4) {
        return num + 2;
    } else {
        return 0;
    }
}

复杂度分析

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