Problem Description

You are given two integers left and right that define a range [left, right] (both inclusive). Your task is to find the bitwise AND of all numbers in this range.

The bitwise AND operation takes two numbers and performs AND on each corresponding bit position. For a range of numbers, you need to perform AND on all numbers sequentially: left & (left+1) & (left+2) & ... & right.

For example, if left = 5 and right = 7:

• 5 in binary: 101
• 6 in binary: 110
• 7 in binary: 111
• Result: 101 & 110 & 111 = 100 (which is 4 in decimal)

The solution leverages the observation that the bitwise AND of a range of numbers will preserve only the common prefix bits. The algorithm repeatedly removes the rightmost 1-bit from right using right & (right - 1) until right becomes less than or equal to left. This efficiently finds the longest common prefix of all numbers in the range when represented in binary.

The key insight is that as numbers increase from left to right, the changing bits (rightmost bits that differ) will eventually become 0 when AND-ed together, leaving only the common leftmost bits.

Intuition

When we look at consecutive numbers in binary representation, we notice a pattern. As numbers increment, the rightmost bits keep flipping while the leftmost bits remain stable for a while. For example, looking at numbers 5 to 7:

• 5: 101
• 6: 110
• 7: 111

The rightmost bit changes from 1→0→1, the middle bit changes from 0→1→1, but the leftmost bit stays at 1. When we AND all these numbers together, any bit position that changes even once will become 0 in the final result.

The key observation is that the result of AND-ing a range of numbers is essentially finding their common binary prefix. Once a bit position differs between any two numbers in the range, that bit and all bits to its right will become 0 in the final answer.

Instead of AND-ing all numbers one by one, we can directly find this common prefix. The trick is to recognize that right & (right - 1) removes the rightmost set bit from right. By repeatedly applying this operation, we're essentially removing the differing rightmost bits until right becomes small enough that it shares the same prefix with left.

Think of it this way: the numbers left and right differ in some rightmost bits. By continuously stripping away the rightmost 1-bits from right, we're moving towards the largest number that has the same prefix as left. Once right becomes less than or equal to left, we've found our common prefix, which is the answer to our bitwise AND operation.

This approach is efficient because instead of iterating through potentially millions of numbers in the range, we only need to remove a few bits (at most the number of bits in the binary representation).

Solution Approach

The implementation uses a simple yet elegant bit manipulation technique. Here's how the algorithm works:

def rangeBitwiseAnd(self, left: int, right: int) -> int:
    while left < right:
        right &= right - 1
    return right

The algorithm repeatedly applies the operation right &= right - 1 until right becomes less than or equal to left. Let's understand what this operation does:

1. The bit manipulation trick: right & (right - 1) removes the rightmost set bit (1-bit) from right. For example:

   • If right = 7 (binary: 111), then right - 1 = 6 (binary: 110)
   • 7 & 6 = 111 & 110 = 110 (which is 6)
   • The rightmost 1-bit has been removed

2. The loop condition: We continue this process while left < right. Each iteration makes right smaller by removing its rightmost 1-bit.

3. Why this works:

   • If left and right differ in some bit positions, those differing bits (and all bits to their right) will eventually become 0 in the AND result
   • By removing rightmost 1-bits from right, we're essentially finding the largest number that has the same binary prefix as both left and right
   • Once right becomes less than or equal to left, it means we've removed all the differing bits, and what remains is the common prefix

4. Example walkthrough with left = 5, right = 7:

   • Initial: left = 5 (101), right = 7 (111)
   • Iteration 1: right = 7 & 6 = 111 & 110 = 110 (which is 6)
   • Iteration 2: right = 6 & 5 = 110 & 101 = 100 (which is 4)
   • Now right (4) < left (5), so we stop and return 4

The time complexity is O(log n) where n is the value of right, as we can remove at most the number of bits in right. The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with left = 9 and right = 12 to illustrate how the algorithm finds the bitwise AND of all numbers in the range [9, 12].

First, let's see what we're trying to compute:

• 9 in binary: 1001
• 10 in binary: 1010
• 11 in binary: 1011
• 12 in binary: 1100

If we manually AND all these numbers: 1001 & 1010 & 1011 & 1100 = 1000 (which is 8 in decimal)

Now let's trace through our algorithm:

Initial state:

• left = 9 (1001)
• right = 12 (1100)

Iteration 1:

• Check: left (9) < right (12) ✓ Continue
• Apply: right = right & (right - 1) = 12 & 11 = 1100 & 1011 = 1000
• Now right = 8 (1000)

Iteration 2:

• Check: left (9) < right (8) ✗ Stop
• Since right is now less than left, we exit the loop

Return: right = 8

Notice how the algorithm efficiently found that the common prefix of all numbers from 9 to 12 is 1000 (8 in decimal) by removing the rightmost differing bits from right. The rightmost two bits change across the range (from 01 to 00), so they become 0 in the final AND result. Only the leftmost bits 10 remain unchanged across all numbers in the range, giving us 1000.

This approach avoided having to AND all four numbers individually and instead found the answer in just one iteration by recognizing that we only need to preserve the common binary prefix.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n) where n is the value of right.

The algorithm uses the Brian Kernighan's algorithm principle where right &= right - 1 clears the rightmost set bit in each iteration. The loop continues while left < right, and in each iteration, we're removing the least significant bit from right. The maximum number of iterations is bounded by the number of bits in right, which is log₂(right). In the worst case, when left = 0 and right is a power of 2 minus 1 (like 2^k - 1), we might need to clear all bits, resulting in O(log n) iterations.

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space. We're modifying the input parameter right in place and not using any additional data structures that grow with the input size. The space usage remains constant regardless of the input values.

Common Pitfalls

1. Attempting Brute Force Approach

A common mistake is trying to compute the bitwise AND by iterating through all numbers in the range:

# WRONG: Time Limit Exceeded for large ranges
def rangeBitwiseAnd(self, left: int, right: int) -> int:
    result = left
    for num in range(left + 1, right + 1):
        result &= num
    return result

Why it fails: When the range is large (e.g., left = 1, right = 2147483647), this approach has O(n) time complexity where n is the range size, causing timeout.

Solution: Use the bit manipulation approach that runs in O(log n) time based on the number of bits, not the range size.

2. Modifying left Instead of right

Some might mistakenly try to increment left or apply bit operations on left:

# WRONG: Incorrect logic
def rangeBitwiseAnd(self, left: int, right: int) -> int:
    while left < right:
        left |= left + 1  # or other operations on left
    return left

Why it fails: The algorithm specifically requires removing rightmost bits from right to find the common prefix. Modifying left breaks this logic.

Solution: Always modify right using right &= right - 1 while keeping left unchanged.

3. Using Wrong Loop Termination Condition

Using <= instead of < in the while loop condition:

# WRONG: Infinite loop or incorrect result
def rangeBitwiseAnd(self, left: int, right: int) -> int:
    while left <= right:  # Should be left < right
        right &= right - 1
    return right

Why it fails: When left == right, the loop would continue unnecessarily, potentially making right smaller than needed or causing an infinite loop if right becomes 0.

Solution: Use while left < right to stop as soon as right becomes less than or equal to left.

4. Not Handling Edge Cases

Forgetting to consider special cases like when left == 0:

# Correct implementation handles all cases naturally
def rangeBitwiseAnd(self, left: int, right: int) -> int:
    while left < right:
        right &= right - 1
    return right

Potential confusion: When left = 0, any AND operation with 0 results in 0. The algorithm handles this correctly because right will eventually become less than 1 (i.e., 0).

Solution: The given algorithm naturally handles all edge cases including:

• left == right: Returns immediately without entering the loop
• left == 0: Eventually returns 0
• Powers of 2 boundaries: Correctly identifies common prefixes