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, m1, ..., 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)为例m ! n各自右移 1 位m 2 (10)、n 3 (11)count 1m ! n各自右移 1 位m 1 (1)、n 1 (1)count 2m n停止。公共前缀为1左移 2 位得100即 4。与题目输出一致。再验证[0, 1]m 0 (0)、n 1 (1)右移一次后m 0、n 0count 1公共前缀 0 左移 1 位仍为 0。符合示例 2 的输出。关键点解析n 个连续数字求与的时候前 m 位都是 1其余位出现过 0结果为 0等价地区间按位与 区间两端点的公共前缀保留共同高位低位清零可以用递归实现个人认为比较难想到bit 运算右移、左移、与。代码实现语言支持JavaScriptPython3JavaScript Code/* * lc appleetcode id201 langjavascript * * [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 Codeclass 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 的二进制表示的位数。由于题目限定位数不超过 31n 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.mdn (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不用乘除取模实现除法同样把问题规模折半与本题递归写法的规模减半思路呼应。小结本题的解题主线是朴素逐位求与会超时必须利用位运算性质连续整数求与时只有两端点m、n的公共前缀能保留 1其余低位因出现过 0 而全部清零实现上只需同时右移m、n直到相等再把公共前缀左移还原即可得到答案该解法时间复杂度取决于二进制位数本题目下近似O(1)空间复杂度O(1)是面试中非常典型的一道位运算 规律发现题目。掌握了区间按位与 公共前缀这个结论不仅本题可以一行思路秒解也能加深对整数二进制表示、进位与位清零机制的直观理解为后续处理更复杂的位运算题目打下基础。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 201 数字范围按位与（Bitwise AND of Numbers Range）题解：公共前缀法剖析
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, m1, ..., 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)为例m ! n各自右移 1 位m 2 (10)、n 3 (11)count 1m ! n各自右移 1 位m 1 (1)、n 1 (1)count 2m n停止。公共前缀为1左移 2 位得100即 4。与题目输出一致。再验证[0, 1]m 0 (0)、n 1 (1)右移一次后m 0、n 0count 1公共前缀 0 左移 1 位仍为 0。符合示例 2 的输出。关键点解析n 个连续数字求与的时候前 m 位都是 1其余位出现过 0结果为 0等价地区间按位与 区间两端点的公共前缀保留共同高位低位清零可以用递归实现个人认为比较难想到bit 运算右移、左移、与。代码实现语言支持JavaScriptPython3JavaScript Code/* * lc appleetcode id201 langjavascript * * [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 Codeclass 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 的二进制表示的位数。由于题目限定位数不超过 31n 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.mdn (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不用乘除取模实现除法同样把问题规模折半与本题递归写法的规模减半思路呼应。小结本题的解题主线是朴素逐位求与会超时必须利用位运算性质连续整数求与时只有两端点m、n的公共前缀能保留 1其余低位因出现过 0 而全部清零实现上只需同时右移m、n直到相等再把公共前缀左移还原即可得到答案该解法时间复杂度取决于二进制位数本题目下近似O(1)空间复杂度O(1)是面试中非常典型的一道位运算 规律发现题目。掌握了区间按位与 公共前缀这个结论不仅本题可以一行思路秒解也能加深对整数二进制表示、进位与位清零机制的直观理解为后续处理更复杂的位运算题目打下基础。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考