LeetCode 868. 二进制间距
题目描述
给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离。如果不存在两个相邻的 1，返回 0。
- 距离定义为两个 1 的索引差值的绝对值（索引从最低位（0）开始向右增加）。
- 示例：
- 输入：
n = 22(二进制10110)，输出：2 - 解释：22 的二进制是
10110，1 的位置为 1、2、4，相邻的 1 之间的距离分别为 1 和 2，最大为 2。
- 输入：
解法一：遍历每一位 + 记录上一个 1 的位置（最直观）
思路
从低位到高位依次检查 n 的每一位，用变量 last 记录上一个 1 出现的索引。当遇到一个新的 1 时，若 last 不是初始值 -1，则计算当前索引 i 与 last 的差值，更新最大距离 res。最后返回 res。
代码
class Solution {
public:
int binaryGap(int n) {
int res = 0, last = -1; // n 最大 10^9 < 2^30，检查 30 位即可
for (int i = 0; i < 30; ++i) {
if ((n >> i) & 1) { // 当前位为 1
if (last != -1) {
res = max(res, i - last);
}
last = i; // 更新上一个 1 的位置
}
}
return res;
}
};
举例分析
以 n = 22（二进制 10110）为例，索引从低位到高位：
| i |
|---|
