标签: 位运算
难度: Easy
给定一个正整数 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 <= 109运行时间: 24 ms
内存: 0.0 MB
class Solution:
def binaryGap(self, N: int) -> int:
d = -32
res = 0
while N:
if N & 1 == 1:
res = max(res, d)
d = 0
d+= 1
N //= 2
return res
本题解采用位操作和循环的方法来求解最大的二进制间距。首先初始化间距d为一个较小的值(-32)，这是因为n的最大值为10^9，其二进制表示最多有30位，初始化为-32可以保证第一个1之前不会误计算间距。变量res用来记录遇到的最大间距。通过不断右移n（N //= 2），使用位与操作（N & 1）判断最低位是否为1。如果为1，则更新res为当前的d（即上一个1之后经过的位数），并重置d为0。如果最低位不是1，则d递增，表示1之间的距离增加。这个过程一直持续到n变为0。
时间复杂度: O(log n)
空间复杂度: O(1)
# 定义Solution类
class Solution:
def binaryGap(self, N: int) -> int:
d = -32 # 初始化d为-32，确保第一个1之前不会误计算间距
res = 0 # 用于记录最大间距
while N: # 循环直到N为0
if N & 1 == 1: # 如果当前最低位是1
res = max(res, d) # 更新最大间距
d = 0 # 重置d
d += 1 # 每次循环增加间距计数
N //= 2 # 右移N，去掉已处理的最低位
return res # 返回最大间距
在算法中，d变量用于计算两个相邻1的间隔。初始间隔d设置为-32是为了确保在找到第一个1之前不会错误地计算间隔。因为n的最大值为10^9，其二进制表示最多有30位，设置为-32可以确保在遇到第一个1之前，d的值不会被错误地使用。这样，在算法中遇到第一个1时，d被重置为0，从而开始正确计算后续1之间的间隔。
如果n的值为0，算法也会正确地返回0。这是因为当N为0时，while循环不会执行，因此直接返回初始化的res值，即0。这种方式确保了即使在输入为0的边界情况下，算法也能正确处理并返回期望的结果。
使用 `N & 1 == 1` 来判断最低位是否为1是一种非常可靠的方法。这种位与运算确保只有当N的最低位是1时，结果才为1。位与运算直接对二进制位进行操作，不受其他因素影响，因此在所有条件下都是可靠的。
在算法中，d每次循环增加1的逻辑用于记录自上一个1之后经过的位数。每次循环中，N通过右移操作（N //= 2）丢弃最低位，因此每次循环确实代表了n的二进制中移过一个位置。这样，每当遇到1时，d就表示了自上一个1后经过的位数，从而可以计算出两个1之间的间隔。