Date: 2026-06-06
Time: 15:22
binary-gap/solution.pyThis file solves LeetCode 868 — Binary Gap. It finds the longest distance between any two adjacent 1 bits in the binary representation of a positive integer. It's a standalone solution module following the repo's convention of one problem per directory.
binary_gap(n: int) -> int — the sole exported function. Contract:
n where 1 <= n <= 10^91 bits, or 0 if fewer than two 1 bits existThree local variables drive the logic:
max_gap: running maximum distance seen so farlast_one: bit position of the most recently seen 1 bit (-1 as sentinel for "haven't seen one yet")pos: current bit position being examined (0-indexed from LSB)Bit-scanning via right-shift loop. Rather than converting to a string with bin(), the code examines one bit at a time by masking with & 1 and shifting n >>= 1. This is the idiomatic low-level approach — O(log n) iterations, no string allocation.
Sentinel-based tracking. lastone = -1 distinguishes "no 1 seen yet" from "first 1 was at position 0." The if lastone >= 0 guard ensures we only compute a gap after seeing at least two 1 bits.
Imports: None — pure computation with no standard library or project imports.
Imported by: binary-gap/testsolution.py directly. The "Imported By" list in the prompt shows hundreds of test files, which is an artifact of the repo's shared test infrastructure — those files don't actually call binarygap, they import the test runner or shared fixtures.
1. Initialize maxgap = 0, lastone = -1, pos = 0.
2. Loop while n > 0 (bits remain):
1: if we've seen a previous 1 (lastone >= 0), update maxgap with the distance pos - lastone. Then record this position as lastone.pos, right-shift n by one.3. Return max_gap.
For n = 22 (binary 10110): positions of 1 bits are 1, 2, 4. Gaps are 2-1=1 and 4-2=2. Returns 2.
last_one is always the position of the most recent 1 bit, or -1. This ensures gaps are measured between *adjacent* 1 bits, not between arbitrary ones.n >>= 1 on a positive integer guarantees n reaches 0.maxgap is non-negative. Since pos strictly increases and lastone is always a previously visited pos, the difference is always positive.None. The function assumes valid input per the LeetCode constraint (1 <= n <= 10^9). Passing 0 would skip the loop entirely and return 0 — harmless but outside spec. Negative integers would loop indefinitely in CPython (arbitrary-precision integers never reach 0 via >>= 1 when negative), but the docstring constrains the domain.
binary-gap/test_solution.py — See what edge cases are covered (single bit, all bits set, power of two)hamming-distance/solution.py:hamming_distance — Another bit-manipulation solution using XOR; compare the scanning patternnumber-of-1-bits/solution.py — Uses the same right-shift loop to count set bits rather than measure gapsbit-scan-vs-string-conversion — Compare performance and readability of n & 1 / n >>= 1 loops vs. bin(n) string indexing across solutions in this repobinary-number-with-alternating-bits/solution.py — Related bit-pattern analysis problem; likely uses similar scanningbinary-gap-returns-zero-for-single-set-bit — When n is a power of two (exactly one 1 bit), binarygap returns 0 because lastone >= 0 is true only once and no gap is ever computed.binary-gap-measures-adjacent-ones-only — The gap is always between consecutive 1 bits in the binary representation, not between the first and last; last_one is updated on every 1 bit encountered.binary-gap-no-dependencies — The module has zero imports; it uses only built-in integer operations.binary-gap-negative-input-infinite-loop — Passing a negative integer causes an infinite loop because Python's arbitrary-precision right-shift of a negative number never reaches 0.