数组异或操作

力扣 1486. 数组异或操作

题目说明

给你两个整数，n 和 start 。

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

请返回 nums 中所有元素按位异或（XOR）后得到的结果。
提示：
- 1 <= n <= 1000
- 0 <= start <= 1000
- n == nums.length

示例

例 1：

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

例 2：

1
2
3

输入：n = 4, start = 3
输出：8
解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.

例 3：

1 2	输入：n = 1, start = 7 输出：7

例 4：

1 2	输入：n = 10, start = 5 输出：2

笔者理解

此题是一道位运算算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题直接求解，也可以通过异或的性质将本题化解成时间空间都是O(1)的高效解法，让我们来看看具体如何实现的吧。

实现

class Solution {
    public int xorOperation(int n, int start) {
        // 结果的最低位
        // 当n和start的最低位都为1时，lowestOrder=1，否则为0
        int lowestOrder = n & start & 1;
        
        // start ^ (start+2) ^ (start+4) ^ …… ^(start + 2*(n-1))
        //  =(令s=start/2)
        // (s ^ (s+1) ^ (s+2) ^ …… ^ (s+n-1)) * 2 + lowestOrder
        // 此处lowestOrder是为了补全start/2时丢失的1
        int s = start / 2;
        
        // 而n到m(n<m)的异或等于1到n-1的异或 异或 1到m的异或
        // 原因：a^a = 0   0^a = a
        int result = computeXOR(s - 1) ^ computeXOR(s + n - 1);
        
        return result * 2 + lowestOrder;
    }

    int computeXOR(int n) {
        // 前n个数异或的结果是有规律的
        // 例如：   二进制数   异或结果    return
        //      1    0001    0001        1
        //      2    0010    0011       n+1
        //      3    0011    0000        0
        //      4    0100    0100        n
        //      5    0101    0001        1
        //      6    0110    0111       n+1
        //      ……   ……      ……
        switch(n % 4)
        {
            case 0:
                return n;
            case 1:
                return 1;
            case 2:
                return n + 1;
            // case3
            default:
                return 0;
        }
    }
}