Bitwise AND of Numbers Range

Difficulty: Medium Source: NeetCode

Problem

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1: Input: left = 5, right = 7 Output: 4

Example 2: Input: left = 0, right = 0 Output: 0

Example 3: Input: left = 1, right = 2147483647 Output: 0

Constraints:

• 0 <= left <= right <= 2³¹ - 1

Prerequisites

Before attempting this problem, you should be comfortable with:

• Bitwise AND (&) — a bit is 1 only if it is 1 in both operands
• Right shift (>>) — removes the least significant bit
• Common binary prefix — the shared leading bits of two numbers

1. Brute Force

Intuition

AND every number in the range together. Since AND can only turn bits off (never on), the result gets smaller with every additional number. This is correct but extremely slow for large ranges — a range like [1, 2147483647] has over 2 billion numbers to AND together.

Algorithm

1. Initialize result = left.
2. For each number from left + 1 to right, AND it into result.
3. Return result.

Solution

def rangeBitwiseAnd(left, right):
    result = left
    for num in range(left + 1, right + 1):
        result &= num
        if result == 0:  # Early exit: once 0, it stays 0
            return 0
    return result


# Only test with small ranges — large ranges will be very slow
print(rangeBitwiseAnd(5, 7))  # 4
print(rangeBitwiseAnd(0, 0))  # 0
print(rangeBitwiseAnd(1, 10)) # 0

Complexity

• Time: O(right - left) — potentially 2³¹ iterations
• Space: O(1)

2. Common Prefix (Right Shift)

Intuition

Here’s the key insight: when you AND a range of consecutive numbers, any bit that changes at any point in the range becomes 0 in the result. A bit can only survive if it stays the same across every number in [left, right].

Which bits stay the same? Only the common prefix — the leading bits that left and right share before their binary representations diverge.

Consider left = 5 = 101 and right = 7 = 111:

5 = 101
6 = 110
7 = 111
AND = 100 = 4

The numbers 5, 6, 7 all start with 1 in the 4’s place, but the lower two bits vary. So only the leading 1 survives → result is 100 = 4.

Now consider left = 12 = 1100 and right = 15 = 1111:

12 = 1100
13 = 1101
14 = 1110
15 = 1111
AND = 1100 = 12

Both share the prefix 11, so the result is 1100 = 12.

Algorithm: Keep right-shifting both left and right until they are equal — at that point we’ve stripped away all the bits that differed. Count how many shifts we made (shift), then left-shift the common prefix back by shift to restore its position.

For left = 5 (101), right = 7 (111):

shift 1: left = 10 (2),  right = 11 (3)
shift 2: left = 01 (1),  right = 01 (1)   →  equal!
shift count = 2
result = 1 << 2 = 4 = 100  ✓

Algorithm

1. Initialize shift = 0.
2. While left != right:
   • Right-shift both: left >>= 1, right >>= 1.
   • Increment shift.
3. Return left << shift.

Solution

def rangeBitwiseAnd(left, right):
    shift = 0
    while left != right:
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift


print(rangeBitwiseAnd(5, 7))           # 4
print(rangeBitwiseAnd(0, 0))           # 0
print(rangeBitwiseAnd(1, 2147483647))  # 0
print(rangeBitwiseAnd(12, 15))         # 12
print(rangeBitwiseAnd(6, 7))           # 6

Complexity

• Time: O(log n) — at most 32 right-shift iterations
• Space: O(1)

Common Pitfalls

Thinking the result equals left & right. It’s tempting to just AND the two endpoints, but that misses all the numbers in between. 5 & 7 = 5 = 101, but the actual answer is 4 = 100 because 6 = 110 kills the last bit.

Why do the intermediate numbers flip bits? In a consecutive range [left, right], if the lower bits of left and right differ (i.e., left != right), there must be some number in between that has a 0 in the position where right has a 1 and vice versa — ANDing those together wipes that bit.

Off-by-one thinking. Even a range of just two consecutive numbers can wipe bits. 6 = 110 and 7 = 111 AND to 110 = 6, but 4 = 100 and 5 = 101 AND to 100 = 4. Always find the common prefix, not just AND the endpoints.