Binary Gap

easy bit manipulation

Problem

Given a positive integer n, find the longest distance between any two adjacent 1's in its binary representation. The distance between bits at positions i and j is the absolute value of i − j. If there are not two adjacent 1's, return 0.

Inputn = 22

Output2

22 is 10110; the 1's sit at positions 1, 2, 4 — the largest gap is 4 − 2 = 2.

def binary_gap(n):
    last, best = -1, 0
    i = 0
    while n:
        if n & 1:
            if last != -1:
                best = max(best, i - last)
            last = i
        n >>= 1
        i += 1
    return best

function binaryGap(n) {
  let last = -1, best = 0, i = 0;
  while (n) {
    if (n & 1) {
      if (last !== -1) best = Math.max(best, i - last);
      last = i;
    }
    n >>= 1;
    i++;
  }
  return best;
}

int binaryGap(int n) {
    int last = -1, best = 0, i = 0;
    while (n != 0) {
        if ((n & 1) == 1) {
            if (last != -1) best = Math.max(best, i - last);
            last = i;
        }
        n >>= 1;
        i++;
    }
    return best;
}

int binaryGap(int n) {
    int last = -1, best = 0, i = 0;
    while (n) {
        if (n & 1) {
            if (last != -1) best = max(best, i - last);
            last = i;
        }
        n >>= 1;
        i++;
    }
    return best;
}

Explanation

We want the largest distance between two neighbouring 1 bits in the binary form of n. The simple idea is to walk the bits from the least-significant end and, whenever we hit a 1, measure how far it is from the previous 1 we saw.

We keep last = the position of the most recent 1 (starting at -1 meaning "none yet") and best = the biggest gap found so far. A counter i tracks the current bit position.

The loop peels off one bit at a time: n & 1 tests the lowest bit, and n >>= 1 shifts everything right so the next bit becomes the lowest. When the current bit is a 1 and we've seen a previous 1, we update best = max(best, i - last), then remember this position as the new last.

When n becomes 0 all bits are processed and best holds the answer. If there was at most one 1, best stays 0.

Example: n = 22 is 10110, with 1s at positions 1, 2, and 4. The gaps are 2-1 = 1 and 4-2 = 2, so the longest binary gap is 2.

Time: O(log n) Space: O(1)