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.