题解 | #牛的编号异或问题#
牛的编号异或问题
https://www.nowcoder.com/practice/b8139d2af0f64e6489f69cb173f170c1
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param left int整型 * @param right int整型 * @return int整型 */ function rangeBitwiseXor(left, right) { let result = 0; // 利用异或的性质,相同的数异 或 结果为0,将相同的数剔除 // 1^2^3^...^n = ((1^2)^(3^4)^...^(n-1)^n) 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; } // 对区间内的数按照奇偶性进行分组 const group = [right, 1, right + 1, 0]; return result ^ group[right % 4]; } const left = 3; const right = 7; const result = rangeBitwiseXor(left, right); console.log("结果为:" + result); module.exports = { rangeBitwiseXor: rangeBitwiseXor, };
- 题目考察的知识点
异或运算
- 题目解答方法的文字分析
这段代码首先根据区间左端点 left 的奇偶性计算出第一个数的异或结果,然后根据区间右端点 right 的奇偶性从预定义的数组 group 中 ,取出对应位置的数与第一个数进行异或。通过利用异或的性质,相同的数异或结果为0,可以得到区间内所有数字按位异或的结果。该算法的时间复杂度为O(1)。
- 本题解析所用的编程语言
JavaScript
- 完整且正确的编程代码
见上面代码