868. 二进制间距

🟢   🔖  位运算  🔗 力扣 LeetCode

题目

Given a positive integer n, find and return _thelongest distance between any two adjacent _1 _' s in the binary representation of _n . If there are no two adjacent1 _' s, return _0 .

Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.

Example 1:

Input: n = 22

Output: 2

Explanation: 22 in binary is "10110".

The first adjacent pair of 1's is "1 0 1 10" with a distance of 2.

The second adjacent pair of 1's is "10 11 0" with a distance of 1.

The answer is the largest of these two distances, which is 2.

Note that "1 01 1 0" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2:

Input: n = 8

Output: 0

Explanation: 8 in binary is "1000".

There are not any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Example 3:

Input: n = 5

Output: 2

Explanation: 5 in binary is "101".

Constraints:

• 1 <= n <= 10^9

题目大意

给定一个正整数 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

解题思路

1. 逐位遍历：

   • 通过位运算来检查 n 的每一位。具体来说，可以用 n >> i 将 n 右移 i 位，然后与 1 做按位与（& 运算），检查该位是否为 1。
   • 如果当前位是 1，记录当前位置 i，然后计算当前位置与上一个 1 的位置之间的距离。
   • 如果上一个 1 存在，更新最大间隔 res。

2. 记录上一个 1 的位置：

   • 使用一个变量 last 来记录上一个 1 出现的位置。
   • 每次遇到新的 1 时，计算与 last 的差值并更新最大间隔。

复杂度分析

• 时间复杂度：O(1)，对每一位（最多 32 位）进行一次检查，时间复杂度为 O(32)，即 O(1)。
• 空间复杂度：O(1)，只用了常量空间来存储变量。

代码

/**
 * @param {number} n
 * @return {number}
 */
var binaryGap = function (n) {
	let res = 0; // 记录最大间距
	let last = -1; // 记录上一个 `1` 出现的位置

	// 遍历 32 位（假设整数是 32 位整数）
	for (let i = 0; i < 32; i++) {
		// 检查第 i 位是否为 1，通过右移 i 位并与 1 做按位与
		if (((n >> i) & 1) > 0) {
			// 如果 last 已经记录了上一个 1 的位置
			if (last >= 0) {
				// 计算当前 1 与上一个 1 的距离
				res = Math.max(res, i - last);
			}
			// 更新 last 为当前位置 i
			last = i;
		}
	}
	return res; // 返回最大距离
};