Binary Gap: Finding the Longest Distance Between 1-Bits

LeetCode Binary Gap (Problem 868) asks you to find the longest distance between any two adjacent 1-bits in the binary representation of a positive integer. Two 1-bits are "adjacent" if there are no other 1-bits between them (only 0-bits or nothing separating them).

For example, given n = 22, the binary representation is 10110. The 1-bits sit at positions 4, 2, and 1. The distances between consecutive pairs are 2 (positions 4 to 2) and 1 (positions 2 to 1). The longest gap is 2.

If the number has fewer than two 1-bits, there is no gap, so you return 0.

Why this problem matters

Binary Gap looks simple on the surface, but it teaches you a pattern you will use over and over: tracking the previous occurrence of something while scanning left to right (or right to left). This "remember the last position" technique shows up in string problems, array problems, and many other bit manipulation questions.

The problem also reinforces how to extract individual bits from an integer, which is foundational for every bit manipulation problem you will encounter.

The approach

The idea is to scan through every bit of the number, keeping track of the position of the most recent 1-bit you have seen. Each time you find another 1-bit, you compute the distance from the previous one and update your maximum.

Here is the plan:

1. Start with a position counter at 0 and no previous 1-bit recorded.
2. Extract the least significant bit using n & 1.
3. If it is a 1-bit and you have seen a previous 1-bit, compute the distance and update the max gap.
4. If it is a 1-bit, record the current position as the new previous position.
5. Right-shift n by 1 and increment the position counter.
6. Repeat until n is 0.

This processes every bit exactly once from right to left.

Step-by-step walkthrough

Let's trace through n = 22 (binary 10110). We scan from the least significant bit to the most significant bit, tracking where we last saw a 1.

The key moment is step 5. When we hit the 1-bit at position 4, we look back at the previous 1-bit at position 2, compute the distance of 2, and that becomes our answer.

The code

def binaryGap(n):
    best = 0
    prev = -1
    pos = 0
    while n:
        if n & 1:
            if prev >= 0:
                best = max(best, pos - prev)
            prev = pos
        pos += 1
        n >>= 1
    return best

Each iteration checks one bit, updates tracking variables, and shifts the number right. When n reaches 0, all bits have been processed.

Complexity analysis

The number of bits in n is floor(log2(n)) + 1. For a 32-bit integer, this is at most 32 iterations. No extra data structures are needed.

Building blocks

Track previous occurrence

The pattern of remembering where you last saw a particular value while scanning through data is extremely common. In this problem, you track the last 1-bit position. The same idea applies to finding the closest pair of equal elements in an array, computing distances between events in a stream, or tracking the last time a character appeared in a string.

if condition_met:
    if prev >= 0:
        distance = current - prev
    prev = current

Bit extraction with right shift

Extracting bits one at a time using n & 1 followed by n >>= 1 is the standard way to iterate through all bits of an integer. You will use this exact loop structure in Number of 1 Bits, Reverse Bits, and many other bit problems. Once this loop feels automatic, you can focus on what to do with each bit instead of how to get it.

Max tracking during iteration

Maintaining a running maximum (or minimum) while iterating is a fundamental pattern. Instead of collecting all values and then finding the max, you update the answer as you go. This keeps space at O(1) and means you only need a single pass.

Edge cases

Only one 1-bit (powers of two like n = 8 = 1000): There is only one 1-bit, so there are no consecutive pairs. The prev variable gets set once but the gap calculation never triggers a second time. The function correctly returns 0.

Two adjacent 1-bits (n = 6 = 110): The 1-bits are at positions 1 and 2. The gap is 1. This is the smallest possible non-zero gap.

All 1-bits (n = 15 = 1111): Every consecutive pair has a gap of 1. The function returns 1 because no pair is farther apart.

Large gap (n = 5 = 101): The 1-bits are at positions 0 and 2. The gap is 2. Even though the number is small, the gap spans across a 0-bit.

n = 1: Binary 1. Only one set bit. Return 0.

Common mistakes

Forgetting to handle the "no previous 1-bit" case. If you compute pos - prev before seeing any 1-bit, you will get a wrong distance. Always check that prev has been set before computing the gap.

Counting from the wrong direction. It does not matter whether you scan left to right or right to left, as long as you are consistent. The gaps are the same either way. But mixing directions will produce incorrect distances.

Returning the gap between the first and last 1-bit instead of the max gap between consecutive 1-bits. The problem asks for the longest gap between adjacent 1-bits, not the total span. For n = 22 (10110), the span from bit 4 to bit 1 is 3, but the correct answer is 2 (the largest gap between consecutive 1s).

From understanding to recall

The mental model for Binary Gap is "scan bits, remember the last 1, measure the distance." That is a single sentence you can hold in your head during an interview.

The recall anchor: "extract each bit, track prev position, update max gap." If that phrase comes back without effort, the code writes itself. The loop is always the same (while n, n & 1, n >>= 1). The only variable part is what you do when you find a 1-bit.

Practice writing this solution from scratch a few times. The first attempt might take a couple of minutes. By the third rep, you should be done in under 60 seconds. That is when the pattern has moved from understanding to recall.

Related posts

• Number of 1 Bits - Same bit extraction loop, different goal: counting instead of measuring gaps
• Hamming Distance - XOR marks differing bits, then you count them using similar bit scanning
• Counting Bits - Systematic bit counting across a range of numbers
• Reverse Bits - Another problem built on the extract-and-shift bit loop
• Power of Two - Uses bit properties to detect single set bits