数字范围按位与 图解题解

这道题到底在问什么

m, n

5, 7

计算

5 & 6 & 7

输出

4

先想最直接的笨办法

笨办法:从 m 与到 n。聪明办法:想清楚哪几位最后能是 1——而连续区间里,低位一定会翻动出 0,只有高位的公共前缀能全程不变。（动画第 3 步）

最优解：一步一步想明白

1. 3笨办法:从 m 与到 n。聪明办法:想清楚哪几位最后能是 1——而连续区间里,低位一定会翻动出 0,只有高位的公共前缀能全程不变。
2. 4所以问题变成:找 m 与 n 最左边相同的那段二进制前缀。下面用 8 位二进制,把 5 和 7 摆出来逐位看。
3. 55 = 0000 01018 个格子是 5 的二进制每一位,最左边是高位。5 = 4 + 1,所以第 5 位和第 7 位是 1。
4. 67 = 0000 0111再看 7 = 0000 0111。和 5 比一比:前面一长串都一样,只有末尾两位不同。公共前缀就在这。
5. 7从最高位开始对齐看先讲直觉法:把指针放到最高位,从左往右一位位比 m 和 n。相同就保留进前缀,一旦不同就停——后面全归 0。
6. 8保留进前缀第 0 位:m 是 0,n 也是 0,相同,标绿进前缀。指针右移看下一位。
7. 9保留进前缀第 1 位也都是 0,相同,继续进前缀。
8. 10保留进前缀第 2 位仍然都是 0,相同。这些高位的 0 会原样留在答案里。
9. 11保留进前缀第 3 位也相同。前缀越攒越长,但还没碰到分叉。
10. 12保留进前缀第 4 位还是相同。马上到 5、7 真正不同的低位了。
11. 13前缀的最后一位第 5 位:m 是 1,n 也是 1(就是那个数值 4),相同!这是公共前缀的最后一位。
12. 14分叉点,停第 6 位:m=0,n=1,不同了!说明区间内这一位翻过 0/1,按位与必为 0。从这位起到末尾全部归 0。
13. 150000 0100 = 4把绿色公共前缀照抄、分叉点之后全填 0,得到 0000 0100 = 4,正是答案。直觉法讲完。
14. 16逐位比要循环 32 次还得记位置。下面这招——右移到相等、记下移了几次、再左移回来——更短更快,是面试标准答案。
15. 17m=0000 0101 shift=0先看 m=5。指针点住最低位——右移时它会被挤掉。m≠n 说明还没对齐到公共前缀,准备同时右移。
16. 18n=0000 0111 m≠n再看 n=7,同样点住最低位。m=5≠n=7,所以进循环:把 m、n 同时右移一位,shift 计一次。
17. 19m: 5 → 2m 右移一位:最低位的 1 被挤掉,5 变成 2(0000 0010)。每个 1 都往右挪了一格。
18. 20n: 7 → 3,m=2 n=3 仍不同n 同样右移一位:7 变成 3(0000 0011)。现在 m=2、n=3,还是不等,继续右移。
19. 21m: 2 → 1再右移:m 从 2 变 1(0000 0001)。shift 累计到 2 次。
20. 22n: 3 → 1,m=n=1 相等!n 从 3 变 1(0000 0001)。这下 m=n=1 相等了!这个 1 就是公共前缀。停止右移,记住一共移了 shift=2 次。
21. 231 << 2 = 0000 0100把相等的值 1 左移回 shift=2 位,末尾补回 2 个 0,得到 0000 0100 = 4。和直觉法答案完全一致。
22. 24答案 = 4 ✓整套动作:同时右移到相等(找前缀)→ 左移回相同位数(补 0)。只需几次移位,无论区间多大都 O(1) 量级。
23. 28只返回 m=1 → 错!假如出循环后忘了 << shift,直接返回此刻的 m=1,就少了末尾两个 0,答案错成 1。右移几次必须左移几次还回去。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def rangeBitwiseAnd(self, m, n):
        shift = 0
        while m < n:            # 还没对齐到公共前缀
            m >>= 1             # m、n 同时右移
            n >>= 1
            shift += 1          # 记下移了几位
        return m << shift       # 左移回去补 0

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {         // 还没对齐
            m >>= 1;            // 同时右移
            n >>= 1;
            shift++;
        }
        return m << shift;      // 左移补 0
    }
};

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {         // 还没对齐
            m >>= 1;            // 同时右移
            n >>= 1;
            shift++;
        }
        return m << shift;      // 左移补 0
    }
}

复杂度

面试官可能追问