0868. 二进制间距【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 逐位检查

1. 📝 题目描述

• leetcode

给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离。如果不存在两个相邻的 1，返回 0。

如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，"1001" 中的两个 1 的距离为 3。

---

示例 1：

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

示例 2：

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

示例 3：

输入：n = 5
输出：2
解释：5 的二进制是 "101"。

---

提示：

• 1 <= n <= 10^9

2. 🎯 s.1 - 逐位检查

js

/**
 * @param {number} n
 * @return {number}
 */
var binaryGap = function (n) {
  let maxDistance = 0 // 记录最大距离
  let lastPosition = -1 // 记录上一个1的位置

  // 遍历n的二进制表示中的每一位
  for (let i = 0; n > 0; i++) {
    // 检查当前最低位是否为1
    if (n & 1) {
      // 如果之前已经遇到过1，则计算距离
      if (lastPosition !== -1) {
        maxDistance = Math.max(maxDistance, i - lastPosition)
      }
      // 更新上一个1的位置
      lastPosition = i
    }
    // 右移一位继续检查下一位
    n >>= 1
  }

  return maxDistance
}

• 时间复杂度：$O(\log n)$，需要遍历 n 的所有二进制位
• 空间复杂度：$O(1)$，只使用了常数额外空间
• 算法思路：
  1. 位运算遍历：通过 n & 1 检查当前最低位是否为 1，然后通过 n >>= 1 右移继续检查下一位
  2. 记录位置：使用 lastPosition 记录上一个 1 出现的位置，初始值为 -1 表示尚未遇到 1
  3. 计算距离：当遇到新的 1 时，计算与上一个 1 之间的距离 i - lastPosition
  4. 更新最大值：使用 Math.max 更新最大距离