题解 | #牛的编号异或问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param left int整型
     * @param right int整型
     * @return int整型
     */
    public int rangeBitwiseXor(int left, int right) {
        return xorRange(right) ^ xorRange(left - 1);
    }

// 辅助函数，用于计算从 1 到 n 的数值的异或结果
    // 连续数字的异或遵循以下模式：
    // 若 n % 4 = 0，则 XOR(1, 2, 3, ..., n) = 0
    // 若 n % 4 = 1，则 XOR(1, 2, 3, ..., n) = n
    // 若 n % 4 = 2，则 XOR(1, 2, 3, ..., n) = 1
    // 若 n % 4 = 3，则 XOR(1, 2, 3, ..., n) = n + 1
    private int xorRange(int n) {
        if (n % 4 == 0) {
            return n;
        } else if (n % 4 == 1) {
            return 1;
        } else if (n % 4 == 2) {
            return n + 1;
        } else {
            return 0;
        }
    }
}

1. 将整数按照余数0、1、2、3分组,每组内的数异或为0。
2. 因此只需关注每组的一个代表元素:余0:代表元素为left，余1:代表元素为1，余2:代表元素为left+1，余3:代表元素为0
3. 右端点right根据其余数,决定取哪个代表元素进行异或运算
4. 最终根据left的余数取代表元素,与right对应的代表元素异或,就得到了整个区间的异或结果