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){intshift=0;// 找到公共前缀while(left<right){left>>=1;right>>=1;shift++;}// 公共前缀左移补 0returnleft<<shift;}}

复杂度

· 时间：O(log n)，最多循环 32 次
· 空间：O(1)

---

解法二：Brian Kernighan 算法

利用 right & (right - 1) 清除 right 最低位的 1，直到 right <= left。

classSolution{publicintrangeBitwiseAnd(intleft,intright){while(left<right){// 清除 right 最低位的 1right=right&(right-1);}returnright;}}

复杂度

· 时间：O(log n)，最多清除 32 次
· 空间：O(1)

---

示例验证

输入:left=5,right=7输出:4输入:left=0,right=0输出:0输入:left=1,right=2147483647输出:0

---

易错点

1. left == right 时直接返回 left，循环条件 left < right 天然处理。
2. 使用 int 即可，因为题目范围在 [0, 2^31 - 1]。
3. 位移法注意先右移再左移，shift 记录移动位数。

面试建议

· 首选位移法，逻辑直观，容易解释公共前缀思想。
· 若面试官追问优化，可提 Brian Kernighan，它直接跳过末尾的 1，效率略高。
· 可画二进制图辅助说明：连续数字的按位与，高位不变，低位必然出现 0。