Bitwise AND of Numbers Range

Problem

Given two integers left and right with left <= right, return the bitwise AND of every integer in the inclusive range [left, right] — that is, left & (left + 1) & ... & right.

Examples

• left = 5, right = 7 → 4 — 101 & 110 & 111 = 100 = 4.
• left = 0, right = 0 → 0 — a single number ANDed with nothing else is itself.
• left = 1, right = 2147483647 → 0 — the range is wide enough that no bit is set in every number.

Constraints

• 0 <= left <= right <= 2^31 - 1

The range can contain billions of numbers, so iterating over it is infeasible. The AND must be found structurally, in about O(log n) steps.

Think about it first

TL;DR

The AND over [left, right] is the common binary prefix of left and right. Find it in O(log n) time, O(1) space; iterating the range does not scale.

Approach 1 — Brute force: AND the whole range

Start from left and AND in every successive number up to right.

def rangeBitwiseAnd(left: int, right: int) -> int:
    result = left
    for num in range(left + 1, right + 1):
        result &= num
        if result == 0:      # can only shrink; 0 is absorbing
            break
    return result

Complexity: O(right - left) time, O(1) space.

Why it fails the constraints: with left = 1, right = 2^31 - 1 the loop runs ~2 billion iterations. Even with the early break, ranges that stay nonzero (e.g. [2^30, 2^30 + 10^9]) run far past any time limit.

Approach 2 — Common prefix by shifting

The insight: a bit survives the AND only if it is 1 in every number of the range. Across a contiguous run of integers, every bit below the highest position where left and right differ takes on both values 0 and 1 somewhere in the range (that’s just counting), so each such bit is ANDed to 0. Only the high bits that left and right already agree on (their common binary prefix) can remain 1. Find that prefix by right-shifting both numbers until they coincide, tracking how far you shifted, then shift the shared value back into place and let the vacated low bits be 0.

def rangeBitwiseAnd(left: int, right: int) -> int:
    shift = 0
    while left < right:
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift        # common prefix, zero-padded

Walkthrough on left = 5, right = 7:

left == right == 1, so the loop stops. Return 1 << 2 = 100 = 4. The shared prefix is 1, and the two low bits (which varied across 5, 6, 7) are zeroed.

Complexity: O(log n) time (at most ~31 shifts), O(1) space.

Approach 3 — Brian Kernighan: clear low bits of right

The insight: instead of shrinking both numbers, repeatedly strip the lowest set bit from right with right & (right - 1). Each stripped bit is a low bit that varies within the range and therefore cannot appear in the answer. Keep going until right drops to left or below; at that point every bit that differed has been cleared and right holds exactly the common prefix. (n & (n - 1) clears the lowest set bit — the standard Kernighan idiom.)

def rangeBitwiseAnd(left: int, right: int) -> int:
    while left < right:
        right &= right - 1      # clear right's lowest set bit
    return right

Walkthrough on left = 5, right = 7:

Return right = 4.

Complexity: O(number of set bits cleared) ≤ O(log n) time, O(1) space.

Common pitfalls

• Trying to loop the range. The range size is up to 2^31; any per-number loop times out. This must be structural.
• left <= right vs left < right in the loop. Use strict <; when they’re already equal the answer is that value with no shifting.
• Forgetting to shift back. In Approach 2 the count of shifts must be reapplied (left << shift), or you return the prefix at the wrong magnitude.
• left == 0. If left is 0, the answer is 0 (the range includes 0, which ANDs everything away) — both approaches handle it naturally, but it’s the classic edge case to check.

Pattern takeaway

Bitwise AND over a contiguous integer range collapses to the numbers’ common high prefix: low bits churn through both values and die, only shared leading bits live. Recognize “AND over a range” as a common-prefix problem (solvable by shifting to the shared prefix or by Kernighan-clearing the low bits), never by iterating the range.