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

import java.util.*;


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

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

Java代码

题目主要涉及到位运算和数学推导。

知识点：

1. 位运算
2. 数学规律：题目中指出了连续数字的异或有一定的模式。通过观察，可以发现这个模式与连续数字的个数与模 4 的余数有关。具体来说，当连续数字个数为 n 时，其按位异或的结果可以根据 n % 4 的值来确定。

代码解释：

1. 在 rangeBitwiseXor 方法中，首先判断 left 是否为 0，因为在计算异或范围时有特殊情况。
2. 对于非 0 的 left，通过计算 xorRange(right) ^ xorRange(left - 1) 来得到区间内所有牛的编号按位异或的结果。
3. 在 xorRange 方法中，使用一个数组 x 存储了四种情况下的异或结果。根据输入数字 n 对 4 取余，选择相应的结果。

例如，当区间为 [left, right] = [3, 6] 时，计算过程如下：

• xorRange(6) 会返回 6 ^ 7 = 1，因为 6 % 4 = 2，对应数组 x 中的值是 7。
• xorRange(2) 会返回 2 ^ 3 = 1，因为 2 % 4 = 2，对应数组 x 中的值是 3。
• 区间内所有牛的编号按位异或的结果是 xorRange(6) ^ xorRange(2) = 1 ^ 1 = 0。