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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param left int整型
     * @param right int整型
     * @return int整型
     */
    public int rangeBitwiseXor (int left, int right) {
      int result = 0;
        if (left % 4 == 0) {
            result = left;
        } else if (left % 4 == 1) {
            result = 1;
        } else if (left % 4 == 2) {
            result = left + 1;
        } else if (left % 4 == 3) {
            result = 0;
        }
 
        // 对区间内的数按照奇偶性进行分组
        int group[] = new int[]{right, 1, right + 1, 0};
        return result ^ group[right % 4];
    }
}

本题知识点分析：

1.位运算的异或

2.数学规律

本题解题思路分析：

1.根据 left 对4取模的结果来确定结果的起始值。如果 left % 4 == 0，说明 left 是4的倍数，结果起始值就是 left；其他同理

2.一个数与自身异或的结果是0，所以对于包含 left 和 right 的区间，将其分为若干个相邻的长度为4的子区间。对于每个子区间，根据子区间中的最大数对4取模的结果，可以得到一个预先计算好的结果表 group[]。group[]中的元素依次对应最大数为0、1、2、3时的异或结果。

3.计算结果是起始值 result 与 group[right % 4]

本题使用编程语言: Java