Bitwise AND of Numbers Range — Solution

Problem

Given two non-negative integers left and right, return the bitwise AND of every integer in the inclusive range [left, right]. Even a modest range can zero out many bits, because consecutive integers constantly flip their low-order bits back and forth.

• Input: left = 5, right = 7
• Output: 4
• Explanation: 5 & 6 & 7 = 101 & 110 & 111 = 100 in binary = 4

Counter-example: left = 1, right = 2 gives 0, because 1 (01) & 2 (10) = 0 — as soon as two adjacent numbers straddle a bit boundary, that bit is gone.

Intuition

When two consecutive numbers differ at bit position k, ANDing the full range will force that bit to 0 — because the range contains both a number with a 0 there and one with a 1. So the only bits that can survive are the ones that stay constant across the entire range, which is exactly the shared binary prefix of left and right. Once left and right differ at even a single bit position, everything below that position washes out.

Solution — Shift to Common Prefix

Keep right-shifting both left and right until they are equal. Each shift peels off one low-order bit; when the values converge, we've isolated their common binary prefix. We count the shifts and left-shift the result back to restore its original magnitude.

1. Initialize a shift counter to zero.
2. While left and right differ, right-shift both by one bit and increment the counter.
3. When equal, left (or equivalently right) holds the common prefix.
4. Left-shift the prefix back by shift_count to restore its position.
5. Return the result.

1def rangeBitwiseAnd(left: int, right: int) -> int:
2    shift_count = 0
3    # Right-shift until both values share the same bit pattern (common prefix)
4    while left != right:
5        left >>= 1
6        right >>= 1
7        shift_count += 1
8    # Shift the common prefix back to its original bit position
9    return left << shift_count

Time: O(log n) — at most 32 iterations for 32-bit integers; each iteration discards one bit.

Space: O(1) — only a constant number of integers regardless of the input range.

Complexity Summary

Common Mistakes

• Iterating through every number in the range: result = left; for i in range(left+1, right+1): result &= i looks correct and is, but it times out completely when right - left is in the billions — this must be solved in O(log n).
• Using left < right instead of left != right as the loop condition: The loop must run until both sides are strictly identical. Using < can exit one iteration too early and leave the prefix shifted by one too few positions.
• Forgetting that left == right is already handled: When the range is a single number, the while loop never runs and left << 0 = left — the answer is the number itself with no extra code needed.
• Confusing the direction of the restore shift: After the loop you right-shifted shift_count times, so restoring requires a left-shift — not another right-shift — by that same count.
• Using unsigned vs signed shifts in Java: Java's >> is arithmetic (sign-bit-extending), which is fine here since both inputs are non-negative. Mixing >> (arithmetic) and >>> (logical) in the same bit problem can introduce subtle sign-extension bugs if you later adapt this to signed contexts.

Related Problems

• number-of-1-bits — foundational bit counting; builds the habit of iterating over individual bits
• counting-bits — explores how bit patterns evolve across consecutive integers, the same intuition that drives this problem
• reverse-bits — works through all 32 bit positions with shifts, same structural pattern
• single-number — uses XOR as a bitwise identity trick; same category of "non-obvious bit operation that collapses a large problem"
• power-of-two — uses n & (n-1) to clear the lowest set bit, a complementary masking technique to the shift-until-equal approach here