DeepSeek LeetCode 201. 数字范围按位与 Java实现

LeetCode 201. 数字范围按位与题目描述给你两个整数 left 和 right表示区间 [left, right]返回此区间内所有数字按位与的结果包含 left、right 端点。核心思路范围内数字连续按位与的结果就是 left 和 right 的二进制公共前缀后面全部补 0。例如left 5 (101), right 7 (111)5: 101 6: 110 7: 111 : 100 → 4公共前缀是 1后面补两个 0得到 100。解法一位移法推荐不断将 left 和 right 右移直到两者相等记录移动次数再左移回来。classSolution{publicintrangeBitwiseAnd(intleft,intright){intshift0;// 找到公共前缀while(leftright){left1;right1;shift;}// 公共前缀左移补 0returnleftshift;}}复杂度· 时间O(log n)最多循环 32 次· 空间O(1)解法二Brian Kernighan 算法利用 right (right - 1) 清除 right 最低位的 1直到 right left。classSolution{publicintrangeBitwiseAnd(intleft,intright){while(leftright){// 清除 right 最低位的 1rightright(right-1);}returnright;}}复杂度· 时间O(log n)最多清除 32 次· 空间O(1)示例验证输入:left5,right7输出:4输入:left0,right0输出:0输入:left1,right2147483647输出:0易错点left right 时直接返回 left循环条件 left right 天然处理。使用 int 即可因为题目范围在 [0, 2^31 - 1]。位移法注意先右移再左移shift 记录移动位数。面试建议· 首选位移法逻辑直观容易解释公共前缀思想。· 若面试官追问优化可提 Brian Kernighan它直接跳过末尾的 1效率略高。· 可画二进制图辅助说明连续数字的按位与高位不变低位必然出现 0。