刷到这道题的时候我的第一反应是二进制间距这题名听着就直白翻译成人话就是“把一个正整数的二进制写出来找相邻的两个1之间最远的距离”。但真动手写代码才发现LeetCode 868 的坑点比想象中要多它表面上是在考一道简单题实际上是在考你对位运算基本功的掌握程度。位运算这个方向很多人要么觉得太底层用不上要么觉得都是些奇技淫巧但当你真正刷到这类题会发现它考查的是对二进制表示、位移、与运算和边界条件的综合理解。这篇就把这道题从题目理解、核心思路、多种实现、边界陷阱到扩展思考一次性讲透你会知道为什么这题值得好好做也能学到几个可以平移到其他位运算题的通用技巧。1. 题目解读与核心思路1.1 这个题到底在问什么要解这道题第一步是先精准理解“二进制间距”的定义。给定一个正整数 n比如 n 5它的二进制是 101位下标从0开始从右往左数那么位置0是1位置1是0位置2是1两个1之间的间距就是 2 - 0 2。这里的“间距”指的是两个1所在二进制位的下标之差而不是两个1中间隔着几个0。如果按“中间有几个0”来理解101 中间只有一个0你会得到错误答案1但题目要求的正确答案是2。还有一点特别容易误读“相邻的两个1”指的是二进制展开中连续出现的两个1它们中间可以有任意多个0但中间不能再出现其他1。举个例子n 21二进制是 101011出现在位置0、2、4那么相邻的1对分别是(0,2)和(2,4)间距分别是2和2所以答案是2。很多人第一次做会把位置0到位置4的距离4也算进去这就不符合“相邻”的定义了。题目本身的输入范围是正整数二进制位最多31位按int算所以从复杂度上来说是很好做的。但正因为题面太短边界情况反而更容易被忽略。比如 n 1 时二进制只有一个1不存在相邻的1对答案是0n 8 时二进制是1000同样只有一个1答案也是0。这些极端输入如果不提前想清楚写出来的代码很容易挂在某个角落。理解了“相邻”和“下标差”这两个关键点这道题才算真正入门了。1.2 为什么我坚持用位运算而不是字符串我第一次做这道题时下意识想用字符串处理把 n 转成二进制字符串遍历字符记录每个1的位置再两两求差。代码写起来确实快也能AC但我很快就意识到这种解法完全浪费了这道题的训练价值。字符串解法的时间复杂度是 O(位数)也就是 O(log n)虽然这个复杂度本身不算高但它不够“纯粹”而且空间上还要额外存一个字符串和位置数组。用位运算解法整个算法只需要几个额外变量一个记录上一个1的位置一个记录答案一个记录当前位下标。循环一次右移一位每轮通过 n 1 判断最低位是不是1整个过程不产生任何新容器空间复杂度是 O(1)。在位运算里整数本身就是二进制表示的载体我们直接对着二进制位操作不需要任何转换这是最贴合题目本质的方式。更重要的是做位运算题的核心目的是培养“二进制直觉”。你在实际工程中做状态压缩、权限位标记、哈希散列优化时经常会用到类似能力。所以我的态度是像868这种题位运算不是选项之一而是必选项。你可以知道字符串解法但最终提交的版本建议至少有一个是纯位运算的。2. 位运算的核心拆解从“怎么看位”到“怎么算间距”2.1 逐位扫描的组合拳与1取位再右移位运算里处理二进制位最常用的组合拳就是两个操作n 1 和 n 1。n 1 的作用是取出当前最低位的值如果结果是1说明这一位是1如果结果是0说明这一位是0。n 1 的作用是把所有二进制位向右移动一位最低位被丢弃高位补0。两个操作配合起来就可以像用指针扫描数组一样从低位到高位逐位查看整个二进制展开。为什么从低位开始而不是从高位因为右移操作天然朝着低位方向进行从低位到高位不需要事先知道数的长度。如果非要从高位开始你得先通过类似 31 - Integer.numberOfLeadingZeros(n) 的方式求出最高位的位置然后再一步步往低位找代码绕一圈收益却很低。所以扫描方向选低位起步就好。这里有一个特别容易踩的坑很多初学者会在判断时写 n 1 1。但很多语言中 的优先级高于 这行代码会被解析成 n (1 1)也就是 n 1然后拿这个结果去当 if 条件最后结果全错。正确写法是 (n 1) 1括号必须加。这个细节看似简单我见过不止一个人在这一行代码上反复调试最后才发现是优先级问题。2.2 记录上一个1的位置动态维护最大值核心逻辑可以用一个状态转移过程来描述。我们需要两个关键变量last 表示最近一次遇到的1所在的下标ans 表示当前找到的最大间距。初始时last 应该设为一个特殊值比如 -1表示“还没有遇到过1”。然后从低位开始扫描每遇到一个1先看 last 是不是 -1如果不是说明当前1和之前那个1构成了一对相邻1间距就是当前下标 i 减去 last拿这个差值和 ans 比较并更新不管有没有计算差值最后都要把 last 更新为当前的 i。这个逻辑本质上很像“双指针”但两个指针中间可以隔着任意多个0我们只关心两个1之间的距离。假设 n 41二进制是1010011在位置0、3、5。扫描到位置0的1时last是-1只更新last为0扫描到位置3的1时last是0计算间距3更新last为3扫描到位置5的1时last是3计算间距2最后ans取3和2中的最大值3。整个过程一目了然。初始值选 -1 而不是0是因为0本身是一个合法的位下标。如果 last 初始为0第一个1恰好出现在位置0时代码会把“从−1到0”这种根本不存在的间距算进去等于凭空多了一个假答案。这是整道题最容易翻车的地方没有之一。2.3 一个容易忽略的循环终止条件写循环的时候最常见的写法是 while (n ! 0)每轮把 n 右移一位。对这种写法有一个隐含假设是输入是正整数因为负数右移在某些语言里是算术右移高位补1可能导致循环永不终止。题目限制了输入范围所以这个坑不会真踩到但如果你以后在工程代码里复用这个模式就要特别注意 和 的区别。更稳妥的做法是固定扫描位数。int 类型是32位直接写 for (int i 0; i 32; i)每轮用 n 1 判断最低位然后 n 1。当 n 右移变成0之后剩下的循环都是在判断0不影响结果。这种写法的好处是循环次数确定不会因为右移和负数边界产生意外代码也更直白。缺点是如果输入类型从 int 变成 long就得把32改成64或者用 while(n ! 0) 更通用。我个人更推荐固定位数循环尤其在面试场景下它能让面试官一眼看出来你对 int 位宽有明确认知。并且无论你选哪种终止方式都要记住一个前提n 只有1个1时循环结束时 ans 应该保持为0这一逻辑要靠 last 初值和更新顺序共同保证。3. 三类实现方案对比与选型心得3.1 方案一逐位遍历加状态记录这是最自然的解法也是我最推荐优先掌握的。直接看 Python 实现class Solution: def binaryGap(self, n: int) - int: last -1 ans 0 i 0 while n: if n 1: if last ! -1: ans max(ans, i - last) last i n 1 i 1 return ans这里有一个容易忽略的设计细节我用了一个单独的变量 i 来记录当前位下标而不是直接用循环轮次。因为 n 每轮都在右移如果用循环轮次去代表位置当 n 右移后高位补0轮次和真正的位下标虽然也能对应上但逻辑语义不够清晰。单独维护一个 ilast 存的就是上次1的绝对下标相减得到间距代码可读性一下提高很多。这个方案的时间复杂度是 O(log n)因为最多循环二进制位数次空间复杂度是 O(1)只用了几个变量。它不需要任何语言内置函数也不依赖位运算高级技巧是理解整道题的最佳入口。如果面试让你现场写这个版本最稳妥不容易写错。3.2 方案二lowbit跳跃跳过所有0如果你觉得逐位扫描还是太老实可以试试另一个经典技巧lowbit。所谓 lowbit指的是 n (-n)作用是只保留二进制中最低位的那个1其他位全部清零。为什么这条式子能做到因为在补码表示中-n 等于 n 取反加1两者做与运算时低位的0不会干扰唯一的1会保留下来。举个例子n 12二进制是1100-n 的补码是0100两者与运算得到0100也就是4正好是12最低位的1所在的位置2对应的权值。利用 lowbit 可以跳过中间所有的0每次只处理一个1。拿到 lowbit 之后通过统计它末尾0的个数就能得到当前1的下标处理完之后用 n - lowbit 把这个1去掉继续下一轮。整个循环次数等于二进制中1的个数而不是二进制位数。Java 实现如下class Solution { public int binaryGap(int n) { int last -1; int ans 0; while (n ! 0) { int low n -n; int pos Integer.numberOfTrailingZeros(low); if (last ! -1) { ans Math.max(ans, pos - last); } last pos; n - low; } return ans; } }在 Python 中lowbit 位置的获取可以用 low.bit_length() - 1因为一个 2 的幂的 bit_length 正好是它的位数。这个方案适合二进制中1比较稀疏的数字比如 2^30 这种经典大数能少循环很多次但如果输入本身是 7 这种全1数字它和逐位扫描的循环次数差不多。顺便说一句Integer.numberOfTrailingZeros 是 Java 内置的统计末尾0个数的函数如果不想依赖它也可以自己写个 while 循环计数本质相同。lowbit 是一种通用武器在“只对二进制中的1感兴趣”的题目里特别好用比如统计1的个数、判断2的幂、枚举子集都会用到这个操作。所以即使这道题用不到也值得单独把这个技巧练熟。3.3 方案三字符串解法能说但不推荐虽然没有必要但知道字符串解法长什么样也没坏处万一被问到至少能讲清楚它的问题。思路其实很直白先用语言自带的二进制转换函数把 n 转成字符串比如 Python 的 bin(n)[2:]再遍历字符串记录每一个1出现的位置最后相邻位置两两求差取最大值。代码很短但它有一个问题每次转换都会产生额外的字符串对象和位置数组空间是 O(位数)时间也比位运算多一个转换开销。在算法题里这个开销可以忽略但它在面试中几乎没有展示价值。面试官看到你用字符串解这题第一反应就是你位运算基础没到位。所以我的建议是这题位运算解法一点不难别偷懒。我也见过一种折中思路先用字符串解法讲清楚“这题在做什么”然后话锋一转说“但如果用位运算可以做到空间O(1)下面我写一个”这种由浅入深的表达方式在面试里反而加分前提是你真的能把位运算版本写对。也就是说字符串解法可以作为思考的第一步但不要让它成为最后一步。3.4 三种方案横向对比维度逐位遍历lowbit跳跃字符串解法核心操作n 1 右移n -n 末尾0统计进制转换 字符遍历时间复杂度O(log n)O(1的个数)O(位数)空间复杂度O(1)O(1)O(位数)代码量中中少位运算训练价值强强无推荐场景面试首选1稀疏时效率高快速演示思路不推荐提交横向对比之后我的选型建议很明确第一遍刷题先写逐位遍历确认自己对“相邻1”“间距”的理解是正确的第二遍再写 lowbit感受一下如何只针对1做操作最后可以顺手写一版字符串解法体会一下为什么位运算版本更优雅。这个“由简到繁再回到简”的过程比单纯抄一份答案有价值得多。4. 边界条件、常见错误与测试用例设计4.1 五个必踩的坑第一个坑last 的初始值。我见过不少人把 last 初始化为0结果第一个1出现在位置0时程序会认为它和“前一个1”的间距是0然后算出一些奇怪的答案。必须用 -1 或任何不可能成为合法下标的负数来做初始标记。第二个坑更新顺序。必须“先算间距再更新 last”顺序颠倒的话每个1都会拿自己和自己的位置求差答案永远是0。这个错误用正常的例子很难发现用 n 5101立刻暴露两个1位置0和2如果先更新lastans永远算不出来2。第三个坑运算符优先级。前面已经强调过n 1 1 会被解析成 n (1 1)结果变成 n 1导致判断失效if 分支不执行代码跑完 ans 永远是0。解决方式是给位运算加括号写成 (n 1) 1。第四个坑答案初始值。如果整个二进制只有一个1正确答案是0。所以 ans 初始化为0是合理的可不能初始化成1否则 n1 时你会返回1直接错。也别想着用 Math.MIN_VALUE 之类的值来偷懒没必要。第五个坑循环条件。写成 while (n 0) 时n 每轮右移最终变成0后退出这是OK的。但如果某天你把输入类型从 int 换成 long又忘了调整循环边界代码会提前退出逻辑就错了。固定位数循环时也要注意位数是否匹配。4.2 针对性的测试用例刷题不能只测样例我整理了一份针对边界情况的测试用例表建议提交前都跑一遍输入二进制展开期望输出测试目的110只有1个1无相邻对21002的幂特例3111两个1紧挨着51012中间隔一个071111连续多个1时最大间距是121101012多个1对间距都为2221011021在位置1、2、4最大间距是2不是310737418241000...00很大的2的幂只有1个1其中 22 这个用例特别狡猾二进制是101101在位置1、2、4很多同学会随手算出来3因为位置4减位置1等于3但位置2还有一个1它会阻断位置1和位置4的“相邻”关系所以正确答案是max(2-1, 4-2)2。这个用例能精准检测你是否有理解“相邻”的定义。还有一类用例值得加输入接近 int 最大值的数字比如 2147483647它虽然是全1但正常位运算应该在一瞬间结束不会溢出。这类大数测试主要是防止你用字符串转换时空间出问题位运算版本基本不会翻车。4.3 手工推演验证过程以 n 22 为例手推一遍逐位扫描的全过程。22 的二进制是10110低位在右所以从右往左读是0、1、1、0、1位下标对应i0到i4。初始 last-1ans0。i0最低位是0不处理i1最低位是1last为-1所以只更新last1i2最低位是1last1计算间距 i-last1ans变成1再更新last2i3最低位是0跳过i4最低位是1last2计算间距2ans更新为2更新last4。循环结束返回2。这个手动过程走一遍你会发现所有关键逻辑都被覆盖了第一个1不做间距计算、后续1能正确求差、跨多个1的最大间距不会算错。养成“随手手推样例”的习惯对做位运算题特别有用。5. 位运算刷题的一点个人心得5.1 做题时的三个习惯第一个习惯是拿到位运算题先在草稿纸上把几个关键数字的二进制展开写出来再自己算一遍答案。因为位运算题通常题面很短但语义容易模糊比如“相邻”“间距”“最低位”这些词都有严格的精确定义。手推几个数之后你会发现很多隐藏的边界情况自己就冒出来了。第二个习惯是把常用位操作整理成模板。我做题时脑子里会常备一组“公式”n 1 取最低位n 1 右移一位n (n-1) 去掉最低位的1n (-n) 只保留最低位的1numberOfTrailingZeros 统计末尾0个数。这些模板就像乘法口诀用多了就能形成条件反射看到新题立刻就想到它们怎么组合。第三个习惯是写完代码以后刻意问自己几个问题如果 n 是0结果对不对如果 n 是2的幂结果对不对如果 n 是 int 最大值会不会溢出如果循环里用到了右移负数会不会出问题这些问题看着简单但真能提前拦截一半以上的隐藏bug。我刷题时有过惨痛教训就是少问了这一句导致一个低级错误花了一整晚才定位。5.2 几个可以用来巩固的进阶题二进制间距只是位运算的入门菜刷完这一道我建议顺着以下几个题目巩固一下二进制中1的个数也就是汉明重量它可以让 n (n-1) 这个操作深入骨髓判断一个数是不是2的幂它本质上是检查二进制是否只有一个1和刚才的 lowbit 完美契合两个整数的汉明距离它会用到异或运算来快速找出不同位还有交替位二进制数核心是检查相邻位是否总在变化又回到了 n 1 和右移的组合。这几个题目都会反复使用我今天讲到的位操作技巧而且每道题都可以用逐位扫描和 lowbit 两种思路各写一遍。练完之后你会发现自己再看到位运算题第一反应不再是字符串转换而是直接动手写二进制运算。这种直觉的建立才是 LeetCode 868 这道看似简单的题真正想送给你的礼物。
