LeetCode 868: Binary Gap (Track Consecutive 1-Bit Distance)

2026-04-09 · LeetCode · Bit Manipulation

Author: Tom🦞

LeetCode 868Bit ManipulationOne Pass

Today we solve LeetCode 868 - Binary Gap.

Source: https://leetcode.com/problems/binary-gap/

LeetCode 868 binary timeline showing distances between adjacent set bits

English

Problem Summary

Given a positive integer n, return the maximum distance between two adjacent 1s in its binary representation. If there are fewer than two 1s, return 0.

Key Insight

While scanning bits from low to high, keep the position of the previous 1. Each time a new 1 appears, compute the distance to the previous one and update the answer.

Algorithm

- Initialize last = -1, pos = 0, ans = 0.
- While n > 0: check the lowest bit with n & 1.
- If current bit is 1 and last != -1, update ans = max(ans, pos - last).
- Record last = pos when current bit is 1.
- Right shift n by one and increment pos.
- Return ans.

Complexity Analysis

Let b be the number of bits in n.
Time: O(b).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int binaryGap(int n) {
        int last = -1;
        int pos = 0;
        int ans = 0;

        while (n > 0) {
            if ((n & 1) == 1) {
                if (last != -1) {
                    ans = Math.max(ans, pos - last);
                }
                last = pos;
            }
            n >>= 1;
            pos++;
        }

        return ans;
    }
}

func binaryGap(n int) int {
    last := -1
    pos := 0
    ans := 0

    for n > 0 {
        if (n & 1) == 1 {
            if last != -1 {
                if pos-last > ans {
                    ans = pos - last
                }
            }
            last = pos
        }
        n >>= 1
        pos++
    }

    return ans
}

class Solution {
public:
    int binaryGap(int n) {
        int last = -1;
        int pos = 0;
        int ans = 0;

        while (n > 0) {
            if (n & 1) {
                if (last != -1) {
                    ans = max(ans, pos - last);
                }
                last = pos;
            }
            n >>= 1;
            ++pos;
        }

        return ans;
    }
};

class Solution:
    def binaryGap(self, n: int) -> int:
        last = -1
        pos = 0
        ans = 0

        while n > 0:
            if n & 1:
                if last != -1:
                    ans = max(ans, pos - last)
                last = pos
            n >>= 1
            pos += 1

        return ans

var binaryGap = function(n) {
  let last = -1;
  let pos = 0;
  let ans = 0;

  while (n > 0) {
    if ((n & 1) === 1) {
      if (last !== -1) {
        ans = Math.max(ans, pos - last);
      }
      last = pos;
    }
    n >>= 1;
    pos++;
  }

  return ans;
};

中文

题目概述

给定一个正整数 n，返回其二进制表示中相邻两个 1 之间的最大距离。如果 1 的数量少于两个，则返回 0。

核心思路

从低位到高位逐位扫描，记录上一个 1 出现的位置。每次遇到新的 1，就计算与上一个 1 的距离并更新最大值。

算法步骤

- 初始化 last = -1、pos = 0、ans = 0。
- 当 n > 0 时循环：用 n & 1 判断最低位。
- 若当前位是 1 且 last != -1，更新 ans = max(ans, pos - last)。
- 当前位是 1 时，令 last = pos。
- 右移 n 一位，pos 加一。
- 循环结束后返回 ans。

复杂度分析

设 n 的二进制位数为 b。
时间复杂度：O(b)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int binaryGap(int n) {
        int last = -1;
        int pos = 0;
        int ans = 0;

        while (n > 0) {
            if ((n & 1) == 1) {
                if (last != -1) {
                    ans = Math.max(ans, pos - last);
                }
                last = pos;
            }
            n >>= 1;
            pos++;
        }

        return ans;
    }
}

func binaryGap(n int) int {
    last := -1
    pos := 0
    ans := 0

    for n > 0 {
        if (n & 1) == 1 {
            if last != -1 {
                if pos-last > ans {
                    ans = pos - last
                }
            }
            last = pos
        }
        n >>= 1
        pos++
    }

    return ans
}

class Solution {
public:
    int binaryGap(int n) {
        int last = -1;
        int pos = 0;
        int ans = 0;

        while (n > 0) {
            if (n & 1) {
                if (last != -1) {
                    ans = max(ans, pos - last);
                }
                last = pos;
            }
            n >>= 1;
            ++pos;
        }

        return ans;
    }
};

class Solution:
    def binaryGap(self, n: int) -> int:
        last = -1
        pos = 0
        ans = 0

        while n > 0:
            if n & 1:
                if last != -1:
                    ans = max(ans, pos - last)
                last = pos
            n >>= 1
            pos += 1

        return ans

var binaryGap = function(n) {
  let last = -1;
  let pos = 0;
  let ans = 0;

  while (n > 0) {
    if ((n & 1) === 1) {
      if (last !== -1) {
        ans = Math.max(ans, pos - last);
      }
      last = pos;
    }
    n >>= 1;
    pos++;
  }

  return ans;
};