二进制间距（Binary Gap）解法详解：从遍历到位运算的相邻 1 距离问题

• 教程
• 文档
• 知识库

本篇题解以《算法通关手册》仓库中 binary-gap.md 的完整题解为主体，围绕 LeetCode 0868「二进制间距」展开。文章先梳理题目约束与两个官方示例，再逐行剖析「遍历二进制字符串」的核心解法及其复杂度，最后结合仓库中 位运算专题 的底层原理，给出不依赖字符串转换的纯位运算写法，帮助读者在掌握本题的同时理解二进制相邻 1 距离的本质。读完本文，你将能独立分析"相邻 1 的最大间距"这一类位运算问题，并随手写出 O(log n) 的解法。

题目概览

• 题号：LeetCode 0868 Binary Gap
• 标签：位运算
• 难度：简单
• 题解出处：docs/solutions/0800-0899/binary-gap.md

该题同时收录在仓库的 LeetCode 题解总表 与 位运算题目列表 中，是位运算入门阶段的一个典型练习。

题目大意

给定一个正整数 $n$（数据范围 $1 \le n \le 10^9$），要求找到并返回 $n$ 的二进制表示中两个相邻 $1$ 之间的最长距离。如果不存在两个相邻的 $1$，返回 $0$。

这里"两个相邻的 1"指的是二进制串中相邻出现的两个1（即按顺序看，前一个1和后一个1之间没有其他1），距离定义为它们在二进制串中的位置下标之差。题目只要求相邻 1 的距离，非相邻的 1（中间还隔着其他 1）之间的距离不在统计范围内。

官方示例

示例 1：

输入：n = 22 输出：2 解释：22 的二进制是 "10110"。 在 22 的二进制表示中，有三个 1，组成两对相邻的 1。 第一对相邻的 1 中，两个 1 之间的距离为 2。 第二对相邻的 1 中，两个 1 之间的距离为 1。 答案取两个距离之中最大的，也就是 2。

以 $22$ 的二进制串10110为例（从右往左数，下标从 0 开始）：下标 1、2、4 处各有一个1。相邻的 1 共有两对：下标 1 与 2 之间的距离为 $1$，下标 2 与 4 之间的距离为 $2$。取最大值为 $2$。

示例 2：

输入：n = 8 输出：0 解释：8 的二进制是 "1000"。 在 8 的二进制表示中没有相邻的两个 1，所以返回 0。

$8$ 的二进制是1000，只含一个1，不存在两个相邻的 1，直接返回 $0$。这也是边界条件的关键——二进制表示中只有 0 个或 1 个1时，答案恒为 0。

思路 1：遍历二进制字符串

算法步骤

1. 使用 Python 内置函数bin(n)将正整数 $n$ 转为二进制字符串bin_n。注意bin(n)返回的字符串带有0b前缀，例如bin(22)的结果是'0b10110'。
2. 设置两个变量：
   • pre：记录上一个1所在的位置（下标）；
   • ans：记录当前已发现的两个相邻 1 之间的最长距离。
3. 从下标2开始遍历字符串（跳过0b前缀），遇到字符'1'时：
   • 用i - pre计算当前1与上一个1之间的距离；
   • 用max(ans, i - pre)更新最长距离；
   • 将pre更新为当前下标i。
4. 遍历结束后返回ans。

关键细节：为什么pre初始化为 2

由于bin(n)的结果形如'0b10110'，前两个字符是0b，真正的二进制数字从下标 2 开始。将pre初始化为2，相当于把前缀末尾的下标 2 当作"虚拟的上一个 1 的位置"，这样在第一次遇到1时执行i - pre不会产生错误距离：

• 第一个遇到的1位于下标 2（即'0b1...'情形）时，i - pre = 0，此时ans = max(0, 0) = 0，不影响结果；
• 若第一个1出现在更靠后的位置，i - pre得到的是第一个1相对起点 $2$ 的偏移量，同样不会误入答案，因为ans的初始值为 $0$，而真正有效的相邻距离只会从第二个1开始被更新。

这一初始化的思路，与仓库 位运算专题 中反复强调的"二进制位下标从 0 开始、前缀属于元数据"的视角一致。

参考代码

以下为原题解给出的完整实现：

class Solution: def binaryGap(self, n: int) -> int: bin_n = bin(n) pre, ans = 2, 0 for i in range(2, len(bin_n)): if bin_n[i] == '1': ans = max(ans, i - pre) pre = i return ans

复杂度分析

• 时间复杂度：$O(\log n)$。整数 $n$ 的二进制串长度为 $\lfloor \log_2 n \rfloor + 1$，遍历一次即可得到答案。
• 空间复杂度：$O(1)$。除返回值外只使用了常数个变量（bin(n)产生的中间字符串不计入额外空间的严格分析时，可视为算法核心仅使用常数辅助空间）。

思路 2：纯位运算解法（不依赖字符串）

字符串遍历写法直观易懂，但题目标签是位运算。结合仓库 位运算专题 中给出的常用位操作表，我们完全可以只对整数本身操作，不产生任何中间字符串。用到的两个基础位操作是：

• n & (n - 1)：将二进制最右侧的 1 置为 0（专题第 3.6 节）；
• n >> 1：整体右移一位，去掉最后一位（专题常用操作表第 3 条）。

算法思路：每次用n & (n - 1)找到"当前最低位的 1"所在的位置（等价于逐个取出相邻的 1），再通过右移统计两个相邻 1 之间的位间隔。实现如下：

class Solution: def binaryGap(self, n: int) -> int: last = -1 # 上一个 1 所在的位置（最低位方向计数） ans = 0 pos = 0 # 当前扫描到的二进制位下标（从最低位 0 开始） while n: if n & 1: # 当前最低位是 1 if last != -1: ans = max(ans, pos - last) last = pos n >>= 1 # 右移一位，等价于去掉刚刚检查过的最低位 pos += 1 return ans

两种写法的核心思想完全一致：只统计相邻 1 的距离，忽略中间间隔的其他位。区别仅在于：思路 1 借助字符串下标计算距离，思路 2 借助右移计数计算距离。该写法与仓库中 0191. 位 1 的个数 的"循环按位计算"解法同源——那里用n & 1配合右移统计 1 的个数，这里进一步把相邻两个 1 的位置差记录为答案。

两种思路的复杂度一致：$O(\log n)$ 时间、$O(1)$ 空间。

边界情况与易错点

1. 只有一个 1：如 $n = 8$（二进制1000），只有一个 1，不存在"相邻的两个 1"，返回 $0$。字符串遍历写法中，ans从未被更新，天然保持 $0$。
2. 全是 1 的连续段：如 $n = 7$（二进制111），相邻 1 之间的距离均为 $1$，答案为 $1$。注意这里的"距离"是位置下标之差，不是二进制串中字符之间的间隔字符数，下标差 1 即为最近距离。
3. bin()前缀处理：忘记跳过0b前缀、或pre初始值设置不当，会导致第一次更新时算入前缀字符的位置，产生错误的距离。这是字符串写法中最常见的失误点。
4. n的上限：题目保证 $1 \le n \le 10^9$，因此二进制串最长约 30 位，任何 O(log n) 的遍历都不会有性能压力。

知识关联：本题在仓库位运算体系中的位置

本题是仓库 位运算专题 的典型配套练习，该专题完整讲解了二进制与十进制互转、六种基本位运算（按位与&、按位或|、按位异或^、取反~、左移<<、右移>>）以及常用操作速查表（如x & (x - 1)清除最低位 1、x >> 1去掉最后一位、(x >> (k - 1)) & 1取右数第 k 位等）。在做本题前，建议先通读该专题 1～3 节，建立起二进制位下标与位操作之间的映射直觉。

与本题类似的"统计/定位二进制中 1"的练习还包括：

• 0191. 位 1 的个数：用n & (n - 1)或循环右移统计 1 的个数；
• 0405. 数字转换为十六进制数：进制转换类位运算问题；
• 0268. 丢失的数字：利用异或性质求解缺失元素。

更多同主题题目可在 位运算题目列表 中继续检索。

总结

二进制间距问题的本质是：在二进制表示中，找出所有相邻 1 之间的最大下标差。无论采用"遍历字符串"还是"纯位运算"实现，核心都是维护"上一个 1 的位置"并逐对更新最大值。字符串写法胜在直观、适合讲解，位运算写法胜在无额外空间、贴近底层。本题在仓库中的完整题解见 binary-gap.md，配套理论见 位运算专题，建议结合二者对照学习，一次吃透"相邻 1"类位运算问题的通法。

• 教程
• 文档
• 知识库