数字范围按位与

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

所以问题变成:找 m 与 n 最左边相同的那段二进制前缀。下面用 8 位二进制,把 5 和 7 摆出来逐位看。

摆出 m = 5 的二进制：8 个格子是 5 的二进制每一位,最左边是高位。5 = 4 + 1,所以第 5 位和第 7 位是 1。

摆出 n = 7 的二进制：再看 7 = 0000 0111。和 5 比一比:前面一长串都一样,只有末尾两位不同。公共前缀就在这。

思路一 · 逐位找公共前缀：先讲直觉法:把指针放到最高位,从左往右一位位比 m 和 n。相同就保留进前缀,一旦不同就停——后面全归 0。

第 0 位 · m=0 n=0 相同：第 0 位:m 是 0,n 也是 0,相同,标绿进前缀。指针右移看下一位。

第 1 位 · m=0 n=0 相同：第 1 位也都是 0,相同,继续进前缀。

第 2 位 · 相同：第 2 位仍然都是 0,相同。这些高位的 0 会原样留在答案里。

第 3 位 · 相同：第 3 位也相同。前缀越攒越长,但还没碰到分叉。

第 4 位 · 相同：第 4 位还是相同。马上到 5、7 真正不同的低位了。

第 5 位 · m=1 n=1 相同：第 5 位:m 是 1,n 也是 1(就是那个数值 4),相同!这是公共前缀的最后一位。

第 6 位 · m=0 n=1 不同!：第 6 位:m=0,n=1,不同了!说明区间内这一位翻过 0/1,按位与必为 0。从这位起到末尾全部归 0。

答案 = 公共前缀 + 补 0：把绿色公共前缀照抄、分叉点之后全填 0,得到 0000 0100 = 4,正是答案。直觉法讲完。

逐位比要循环 32 次还得记位置。下面这招——右移到相等、记下移了几次、再左移回来——更短更快,是面试标准答案。

右移法 · 起步(看 m)：先看 m=5。指针点住最低位——右移时它会被挤掉。m≠n 说明还没对齐到公共前缀,准备同时右移。

右移法 · 起步(看 n)：再看 n=7,同样点住最低位。m=5≠n=7,所以进循环:把 m、n 同时右移一位,shift 计一次。

右移第 1 次 · m 右移：m 右移一位:最低位的 1 被挤掉,5 变成 2(0000 0010)。每个 1 都往右挪了一格。

右移第 1 次 · n 右移：n 同样右移一位:7 变成 3(0000 0011)。现在 m=2、n=3,还是不等,继续右移。

右移第 2 次 · m 右移：再右移:m 从 2 变 1(0000 0001)。shift 累计到 2 次。

右移第 2 次 · n 右移：n 从 3 变 1(0000 0001)。这下 m=n=1 相等了!这个 1 就是公共前缀。停止右移,记住一共移了 shift=2 次。

左移回去 · 补回 2 个 0：把相等的值 1 左移回 shift=2 位,末尾补回 2 个 0,得到 0000 0100 = 4。和直觉法答案完全一致。

右移法 · 完成：整套动作:同时右移到相等(找前缀)→ 左移回相同位数(补 0)。只需几次移位,无论区间多大都 O(1) 量级。

雷区实演 · 忘了左移补 0：假如出循环后忘了 ,直接返回此刻的 m=1,就少了末尾两个 0,答案错成 1。右移几次必须左移几次还回去。

边界三连：先想三种边界:单点(m=n)直接返回、含 0 必为 0、超大区间也只是多移几位,代码就稳了。

面试追问：把「为何是公共前缀」和「O(log n)」讲清楚,再补一句 Brian Kernighan 写法,是这题的加分点。