题解 | #牛的编号异或问题# 前缀异或和

知识点

前缀异或和

思路

题目样例有问题，给出5,7要求的是6^7=1即[left+1, right]的区间异或和

我们可以把区间异或和转化为前缀异或和的差，所以只需要实现函数get（x）来求0到x的异或和

我们观察到结果是具有规律性的：

• 当x%4为0时结果是x
• 当x%4为1时结果是1
• 当x%4为2时结果是x+1
• 当x%4为3时结果是0

因此我们可以在时间内计算得到结果

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param left int整型 
     * @param right int整型 
     * @return int整型
     */
    int rangeBitwiseXor(int left, int right) {
        return get(right) ^ get(left);
    }
    int get(int x) {
        int t = x % 4;
        if (t == 0) return x;
        if (t == 1) return 1;
        if (t == 2) return x + 1;
        return 0;
    }
};