教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文是《算法通关手册》AlgoNote题解系列的一篇精讲聚焦 LeetCode 0201「数字范围按位与」深入剖析如何借助 Brian Kernighan 位运算技巧n (n - 1)在 $O(\log n)$ 时间内求出区间 $[left, right]$ 内所有整数的按位与结果。读完本文你将掌握求二进制公共前缀 → 后缀补零这一经典位运算建模思路理解枚举法为何在大区间下必然超时并能把同一技巧迁移到统计二进制中 1 的个数、判断 2 的幂等系列问题中。一、题目回顾问题定义与数据范围本道题对应仓库题解文档 bitwise-and-of-numbers-range.md标签为「位运算」难度为「中等」。题目描述给定两个整数 $left$ 和 $right$表示区间 $[left, right]$。要求返回此区间内所有数字按位与AND的结果且结果包含 $left$、$right$ 两个端点。约束说明$0 \le left \le right \le 2^{31} - 1$。也就是说区间内的数字最多可达 $2^{31}$ 个当 $left 0$、$right 2147483647$ 时这就意味着任何逐个数做与运算的枚举方案在最坏情况下都是不可接受的。官方示例# 示例 1 输入left 5, right 7 输出4 # 验证5 6 7 101 110 111 100(2) 4 # 示例 2 输入left 1, right 2147483647 输出0二、为什么枚举法不可行最容易想到的做法是遍历区间def range_bitwise_and_enum(left: int, right: int) - int: res left for x in range(left 1, right 1): res x return res直观、正确但复杂度为 $O(right - left)$。当区间长度为 $10^9$ 量级时如示例 2单次运算就需要遍历数十亿个整数在 LeetCode 的时间限制下必然超时。因此正确解法必须跳出逐个数计算的思维从位运算本身的数学性质出发寻找规律。三、核心思路从按位与的规则到公共前缀3.1 按位与运算的四条基本规则按位与的规则只有四条可参考仓库位运算基础教程 07_06_bit_operation.md 中 2.1 节0 0 00 1 01 0 01 1 1由此得出关键结论只有对应二进制位上都为 $1$ 时按位与结果才能得到 $1$只要某个位置出现过一次 $0$该位置的最终与结果就一定为 $0$。3.2 问题转化为求二进制公共前缀假设区间内所有数字的二进制表示存在长度为 $x$ 的公共前缀即所有数字的高位完全相同。那么公共前缀部分每一位在所有数字中的取值完全相同按位与结果与每一位的取值相同可直接保留。公共前缀之后的剩余部分由于区间跨越了 $left$ 到 $right$ 之间的所有整数这部分位必然经历了从 $0$ 到 $1$ 的全过程最终与结果一定为 $0$。于是原问题被转化为求出 $[left, right]$ 范围内所有数的二进制公共前缀然后在公共前缀之后的剩余位上补 $0$。对剩余部分分两种情况讨论$x 31$说明 $left right$此时按位与结果就是 $left$ 本身。$0 \le x 31$因为 $left right$则 $left$ 的第 $x 1$ 位必然为 $0$$right$ 的第 $x 1$ 位必然为 $1$。注意这里不存在两种意外$left$、$right$ 第 $x 1$ 位不可能同为 $0$ 或同为 $1$否则它们就都属于公共前缀了也不可能出现 $left$ 第 $x 1$ 位为 $1$、$right$ 第 $x 1$ 位为 $0$否则就有 $left right$与题意矛盾。3.3 一个关键观察区间必然路过 $1000...$从第 $x 1$ 位起从 $left$ 走到 $right$二进制计数必然经过形如10000...的位置即 $2^{31-x-1}$ 及其倍数点这使得公共前缀之外的剩余 $31 - x$ 位中必然出现全 $0$ 的数位组合剩余部分的按位与结果一定为 $0$。举例若 $x 27$剩余部分长度为 $4$区间内该部分的取值会从0XXX一路递增到1XXX途中必然经过1000于是剩余 4 位的与结果为0000。这也验证了示例 2$left 1, right 2147483647$两者公共前缀长度为 $0$剩余 31 位在区间内必然出现全 $0$结果自然为 $0$。四、求解公共前缀Brian Kernighan 的n (n - 1)技巧4.1 公式含义与原理n (n - 1)是位运算中的经典技巧对 $n$ 与 $n - 1$ 做按位与后$n$ 二进制表示中最右侧的那个 $1$ 会被变成 $0$其余位保持不变。例如 $n 10110100_{(2)}$执行n (n - 1)后得到 $10110000_{(2)}$最右侧的 $1$ 被清除。该技巧在仓库中的出处有两处位运算基础教程 07_06_bit_operation.md 的3.6 节「将二进制最右侧为 1 的二进位改为 0」给出的例子是X 01101100(2)X (X - 1) 01101100 01101011 01101000位运算基础教程3.7 节还利用它统计二进制中 1 的个数并在3.8 节用它判断某数是否为 2 的幂X (X - 1) 0且 $X 0$。4.2 如何用它求区间公共前缀既然要消除公共前缀之后的 $1$而right (right - 1)恰好能把最右侧的 $1$ 清零我们就可以不断对 $right$ 执行该操作直到 $right \le left$对给定的区间 $[left, right]$迭代执行right right (right - 1)当 $right \le left$ 时停止——此时区间内非公共前缀部分的 $1$ 均已变为 $0$剩下的 $right$ 恰好保留了公共前缀输出 $right$ 作为最终答案。为什么这个迭代是正确的因为每一次right (right - 1)都会把 $right$ 拉低到跳过下一个包含最右侧 $1$ 的断点而区间 $[left, right]$ 中任何一处的公共前缀正是 $left$ 与 $right$ 逐步逼近后的最高公共位。当 $right$ 被消减到不大于 $left$ 时所有会破坏公共前缀的低位 $1$ 都已被清除此时 $right$ 与 $left$ 的公共前缀即为最终答案。4.3 完整代码实现原题解见 bitwise-and-of-numbers-range.md 思路 1 代码如下class Solution: def rangeBitwiseAnd(self, left: int, right: int) - int: while left right: right right (right - 1) return right逐步推演示例以left 5, right 7为例初始left 101(2)right 111(2)满足left right迭代right 111 110 110(2) 6仍满足left right迭代right 110 101 100(2) 4此时left(5) right(4)循环终止返回4与示例 1 输出一致。若区间两端相等如left right 5循环一次都不执行直接返回5对应公共前缀长度为 31结果就是 left 本身的情况。4.4 复杂度分析时间复杂度$O(\log n)$。每次right (right - 1)清除一个最右侧的 $1$而 $right \le 2^{31} - 1$最多迭代 31 次迭代次数与二进制位数成正比。空间复杂度$O(1)$仅使用常数级额外空间。与之相比仓库中同一技巧的另一个经典应用——number-of-1-bits.mdLeetCode 0191「位 1 的个数」——也是通过不断执行n n (n - 1)直到 $n$ 变为 $0$用变换次数统计二进制中 $1$ 的个数时间复杂度同样为 $O(\log n)$。两者共享同一底层位运算只是停止条件与返回语义不同一个以left right为界返回右端点一个以n 0为界返回计数。五、相似解法的扩展视角除了 Brian Kernighan 迭代法这道题还有几个值得理解的相关思路未在原题解正文中展开但属于同一知识脉络位移法原地右移循环将left、right同时右移记录移位次数shift直到两者相等最后将相等的公共前缀左移shift位还原。本质与本文思路一致都是求公共前缀。n (n - 1)的其他应用判断 2 的幂见 power-of-two.mdLeetCode 0231 思路中n 0 and 1073741824 % n 0为数论方案而位运算方案即判断n (n - 1) 0、统计二进制中 1 的个数LeetCode 0191等。在《算法通关手册》中位运算知识体系集中在 07_06_bit_operation.md其中 3.63.8 节正是本解法所依赖的底层技巧位运算相关题目汇总见 00_06_categories_list.md 的「位运算题目」小节其中收录了本道 0201. 数字范围按位与 及 LeetCode 0190「颠倒二进制位」、0191「位 1 的个数」、0260「只出现一次的数字 III」等同主题题目适合作为练习清单一并刷完。六、总结枚举法对区间 $[left, right]$ 逐数做与运算正确但低效最坏情况下 $O(2^{31})$ 必然超时按位与的规则决定了某位出现过 $0$ 即结果为 $0$因此区间内所有数按位与的结果等于二进制公共前缀 后缀补零利用n (n - 1)每次清除最右侧的 $1$对right迭代直至right left即可在 $O(\log n)$ 时间内求出公共前缀代码仅需 3 行该技巧与 LeetCode 0191「位 1 的个数」、0231「2 的幂」等题目共享同一底层位运算值得一并对比掌握。本解法完整源码与题解文档位于仓库 docs/solutions/0200-0299/bitwise-and-of-numbers-range.md读者可直接对照阅读或结合位运算基础教程 07_06_bit_operation.md 逐节巩固。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐XLeRobot 多场景仿真指南在 ManiSkill 中切换 ReplicaCAD、AI2THOR、Robocasa 与 OpenCabinetDrawer 环境XLeRobot 多场景仿真指南在 ManiSkill 中切换 ReplicaCAD、AI2THOR、Robocasa 与 OpenCabinetDrawer教程文档知识库AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划 导读 本篇是 AlgoNote算法通关手册中 009教程文档知识库AlgoNote 算法通关手册LeetCode 0089 格雷编码Gray Code——位运算公式法全解析AlgoNote 算法通关手册LeetCode 0089 格雷编码Gray Code——位运算公式法全解析 格雷编码Gray Code是位运算与数学相教程文档知识库上一篇Android设备控制新体验Escrcpy图形化投屏工具快速上手指南下一篇两张图丢进去一次拿回四张试穿候选用 OOTDiffusion 做虚拟试穿创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考