企业官网建设流程全解析

LeetCode 201 数字范围按位与（Bitwise AND of Numbers Range）题解：公共前缀法剖析

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本文基于 leetcode 题解仓库中的 problems/201.bitwise-and-of-numbers-range.md 展开，深入讲解区间[m, n]全部整数按位与的数学性质与两种高效实现（迭代右移、递归折半）。读完你将掌握"连续整数按位与等价于求公共前缀"这一位运算套路，并理解其与二分思想的关联，能够从容应对数据范围达2^31 - 1的大区间用例。

题目描述

给定范围[m, n]，其中0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含m, n两端点）。

示例 1：

输入: [5,7] 输出: 4

示例 2：

输入: [0,1] 输出: 0

所谓"所有数字的按位与"，即对m, m+1, ..., n逐一对每一位执行&运算：某一位上只要出现过一个0，最终结果的该位就是0。

前置知识

• 位运算（&、|、^、~、<<、>>）

仓库中 thinkings/bit.md 系统整理了位运算专题（异或性质、消除最低位 1 等套路），并与 problems/191.number-of-1-bits.md（位 1 的个数）、problems/371.sum-of-two-integers.md（不用加减法求和）等题互为补充，适合一起练习。

公司

• 阿里
• 腾讯
• 百度
• 字节

思路一：朴素解法（从 m 到 n 逐个求与）

一个显而易见的解法是，从m到n依次进行求与的操作：

let res = m; for (let i = m + 1; i <= n; i++) { res = res & i; } return res;

然而，把这个 solution 直接提交显然不会通过——会超时。

原因在于区间长度可能高达n - m，而n最大可取2147483647（约 21 亿），O(n - m)的线性扫描在最坏情况下会执行数十亿次位运算。因此必须寻找位运算级别的 trick 将复杂度压到与二进制位数相关的级别。

思路二：核心 trick——连续数字按位与等于公共前缀

我们利用的性质是：n 个连续数字求与的时候，前 m 位都是 1。

先看题目给出的例子：[5, 7]共 5、6、7 三个数字，二进制表示分别为101、110、111。这三个数字的特点是最高位（第一位）都是 1，而后面几位各不相同，按位与的结果一定是 0——因为只要某一位上出现过 0，该位结果就是 0。

再看一个更明显的例子：[20, 24]，共 20、21、22、23、24 五个数字，二进制表示如下：

0001 0100 0001 0101 0001 0110 0001 0111 0001 1000

这五个数字的特点是高 5 位（0001 0）完全相同，而低 3 位100、101、110、111、000中每一位都出现过 0，因此低 3 位求与一定是 0。所以整个区间的按位与结果就是公共前缀0001 0000，即十进制 16。

由此得到核心结论：一个区间内所有整数的按位与，等于这些整数二进制表示中公共前缀对应的数值——公共前缀保持不变，其余位全部清零。

为什么成立：进位意味着低位归零

直觉上，从m递增到n的过程中，每跨越一次2^k的倍数，第k位及其更低位的取值就必然遍历到 0。特别是：

• 只要n - m >= 2^k，第k位必定出现过 0（因为在这段区间内第k位一定发生了从 1 到 0 或多次翻转，而按位与要求"全 1 才为 1"）；
• 因此最终结果中，凡是"发生过翻转"的位全部为 0，只保留m与n从最高位向最低位完全一致的公共前缀。

换一个等价说法：m和n同时右移（丢弃最低位），直到两者相等时，剩下的数字就是公共前缀；此前右移的次数count就是要被清零的低位个数，最后把公共前缀左移count位还原即可。

正确性验证（[5,7] 手工推演）

以m = 5 (101)、n = 7 (111)为例：

1. m != n，各自右移 1 位：m = 2 (10)、n = 3 (11)，count = 1；
2. m != n，各自右移 1 位：m = 1 (1)、n = 1 (1)，count = 2；
3. m == n，停止。公共前缀为1，左移 2 位得100，即 4。与题目输出一致。

再验证[0, 1]：m = 0 (0)、n = 1 (1)，右移一次后m = 0、n = 0，count = 1，公共前缀 0 左移 1 位仍为 0。符合示例 2 的输出。

关键点解析

• n 个连续数字求与的时候，前 m 位都是 1（其余位出现过 0，结果为 0）；
• 等价地：区间按位与 = 区间两端点的公共前缀（保留共同高位，低位清零）；
• 可以用递归实现，个人认为比较难想到；
• bit 运算（右移、左移、与）。

代码实现

语言支持：JavaScript，Python3

JavaScript Code

/* * @lc app=leetcode id=201 lang=javascript * * [201] Bitwise AND of Numbers Range * */ /** * @param {number} m * @param {number} n * @return {number} */ var rangeBitwiseAnd = function (m, n) { let count = 0; while (m !== n) { m = m >> 1; n = n >> 1; count++; } return n << count; };

实现要点：

• 循环条件m !== n：只要两个数还没收敛到同一个公共前缀，就继续同时右移；
• 右移丢弃的是"最终结果中必然为 0"的低位；
• 结束后count记录丢弃的低位个数，n << count（或m << count，此时二者相等）把公共前缀还原到正确的位置；
• 全程不依赖区间长度，只与二进制的位数（最多 31 位）相关。

Python Code

class Solution: def rangeBitwiseAnd(self, m: int, n: int) -> int: cnt = 0 while m != n: m >>= 1 n >>= 1 cnt += 1 return m << cnt

递归写法（源自原文档的思路）

原文档还给出了一种递归实现，代码极短：

n > m ? rangeBitwiseAnd(m / 2, n / 2) << 1 : m;

它的逻辑与迭代版本完全同构：每次递归都把m、n各自除以 2（等价于右移一位），并把子问题的答案左移一位还原；递归出口是m == n，直接返回m。

每次问题规模缩小一半，这是二分法吗？

需要指出：这里的"每次缩小一半"是指二进制位数减半（数值除以 2），而二分法通常指在一个有序搜索空间中每次排除一半的候选范围。从"每轮迭代把输入规模减半"的形式上看，它具备二分思想的影子，但本题的收敛路径是确定性的（不断右移直至相等），并不存在搜索空间的分支选择。仓库的 91/binary-search.md 对二分法（折半搜索算法）有专门讲解，其中也讨论了"广义的二分查找是将问题的规模缩小到原有的一半"，可对照理解本题递归的折半性质。

复杂度分析

• 时间复杂度：最坏情况我们需要循环 N 次，最好的情况是一次都不需要（当m == n），因此时间复杂度取决于我们移动的位数，具体移动次数取决于输入，平均来说时间复杂度为O(N)，其中 N 为 M 和 N 的二进制表示的位数。由于题目限定位数不超过 31（n <= 2147483647 < 2^31），可以认为这是一个近似常数（O(31)）的极快算法。
• 空间复杂度：O(1)（迭代版本无额外空间；递归版本的调用栈深度同样为O(N)，N 为二进制位数）。

边界情况与注意事项

• m == n：区间只有一个数，按位与结果就是它本身，循环一次都不执行，直接返回m。这对应原文档所说的"最好的情况是一次都不需要"。
• m == 0：公共前缀为 0，结果恒为 0，例如示例 2 的[0, 1]。
• 大区间：例如[1, 2147483647]，朴素解法必然超时，而右移解法最多循环 31 次即可收敛，这正是本题考察位运算的原因。
• 负数与符号位：题目约束0 <= m <= n，均为非负整数，因此无需处理有符号右移与补码带来的细节；对比 problems/371.sum-of-two-integers.md 中 Python 模拟 32 位有符号加法的处理，可以看到在涉及负数位运算时，Python 的无限长整数类型需要额外& 0xFFFFFFFF掩码来模拟 32 位语义，而本题的取值约束天然规避了这一问题。

仓库内的相关位运算题目

本题被收录在 collections/medium.md 的中等难度题单中（0201. 数字范围按位与）。若想系统训练位运算，可在仓库中找到以下配套题解：

• thinkings/bit.md：位运算专题讲义，讲解异或性质、分组异或等套路，覆盖 136/137/260/645 等题；
• problems/191.number-of-1-bits.md：n & (n - 1)消除最低位 1 的经典技巧；
• problems/342.power-of-four.md：利用n & (n - 1) == 0与掩码0x55555555判断 4 的幂，与本篇的"公共前缀 + 掩码"思想同源；
• problems/371.sum-of-two-integers.md：异或当无进位加法、与后左移当进位，递归实现加法；
• problems/29.divide-two-integers.md：不用乘除取模实现除法，同样把问题规模折半，与本题递归写法的"规模减半"思路呼应。

小结

本题的解题主线是：

1. 朴素逐位求与会超时，必须利用位运算性质；
2. 连续整数求与时，只有两端点m、n的公共前缀能保留 1，其余低位因出现过 0 而全部清零；
3. 实现上只需同时右移m、n直到相等，再把公共前缀左移还原，即可得到答案；
4. 该解法时间复杂度取决于二进制位数（本题目下近似O(1)），空间复杂度O(1)，是面试中非常典型的一道"位运算 + 规律发现"题目。

掌握了"区间按位与 = 公共前缀"这个结论，不仅本题可以一行思路秒解，也能加深对整数二进制表示、进位与位清零机制的直观理解，为后续处理更复杂的位运算题目打下基础。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode