LeetCode 201 - Bitwise AND of Numbers Range

The problem asks us to compute the bitwise AND of every integer in the inclusive range [left, right]. For example, if left = 5 and right = 7, the numbers in the range are: Applying bitwise AND across all values: So the answer is 4.

leetcodemediumbit-manipulation

LeetCode Problem 201

Difficulty: 🟡 Medium
Topics: Bit Manipulation

Solution

Problem Understanding

The problem asks us to compute the bitwise AND of every integer in the inclusive range [left, right].

For example, if left = 5 and right = 7, the numbers in the range are:

5 = 101
6 = 110
7 = 111

Applying bitwise AND across all values:

101
110
111
---
100 = 4

So the answer is 4.

The input consists of two non-negative integers:

  • left, the start of the range
  • right, the end of the range

The output is a single integer representing the cumulative bitwise AND of every number between them.

The constraints are important:

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

This means the range can be extremely large. A naive solution that iterates through every number could potentially process billions of integers, which is far too slow.

The key observation is that bitwise AND becomes smaller as more numbers are included. Any bit position that changes from 0 to 1 or 1 to 0 anywhere in the range will eventually become 0 in the final answer.

Several edge cases are important:

  • When left == right, the answer is simply that number.
  • When the range crosses a power of two boundary, many higher bits become zero.
  • When left = 0, the answer is always 0 because AND with zero produces zero.
  • Very large ranges often collapse to 0 quickly because many bits fluctuate across the range.

Approaches

Brute Force Approach

The most direct approach is to iterate from left to right and continuously apply bitwise AND.

We could initialize:

result = left

Then for every number from left + 1 to right:

result &= current_number

This works because bitwise AND is associative:

(a & b) & c == a & (b & c)

So processing the numbers sequentially produces the correct answer.

However, this approach is too slow for the problem constraints. If the range spans billions of numbers, the algorithm would require billions of operations.

Optimal Approach

The key insight is that the final result only preserves the common binary prefix shared by left and right.

Consider:

left  = 101101
right = 101111

The shared prefix is:

101

The remaining bits vary throughout the range. Any varying bit will eventually become 0 during the AND process.

Therefore, the answer is simply the common prefix followed by zeros.

One elegant way to find this common prefix is:

  • Repeatedly right shift both numbers until they become equal
  • Count how many shifts were performed
  • Shift the common value back left by the same amount

This removes differing suffix bits and keeps only the stable prefix.

Approach Time Complexity Space Complexity Notes
Brute Force O(right - left) O(1) Iterates through every number in the range
Optimal O(32) O(1) Finds the common binary prefix

Algorithm Walkthrough

  1. Initialize a counter called shift_count to 0.

This counter tracks how many bits we remove from the right side of both numbers. 2. Compare left and right.

If they are already equal, then they already share the same prefix and no more processing is needed. 3. While left != right, right shift both values by one bit.

Right shifting removes the least significant bit. We continue removing bits until both numbers become identical.

This works because differing suffix bits cannot survive the AND operation across the entire range. 4. Increment shift_count after each shift.

We need this information later so we can restore the shared prefix to its original position. 5. Once left == right, we have found the common prefix.

At this point, all differing bits have been discarded. 6. Left shift the common prefix back by shift_count.

This restores the prefix to its original location while filling the remaining bits with zeros. 7. Return the final value.

Why it works

The algorithm relies on a fundamental property of bitwise AND over ranges.

If any bit position changes within the range [left, right], then at least one number contains 0 in that position, causing the final AND result for that bit to become 0.

Only the bits that remain identical across the entire range survive. Those bits form the common binary prefix of left and right.

By removing differing suffix bits through right shifts and restoring the prefix afterward, the algorithm computes exactly the bits that remain stable throughout the range.

Python Solution

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shift_count = 0

        while left != right:
            left >>= 1
            right >>= 1
            shift_count += 1

        return left << shift_count

The implementation follows the algorithm directly.

The variable shift_count tracks how many times both numbers are shifted right.

The while loop continues until left and right become equal. Every iteration removes one differing bit from the right side.

Once both numbers match, the shared prefix has been isolated. The final line restores that prefix to its original bit position using a left shift.

This solution uses only constant extra space and performs at most 31 to 32 iterations because integers are bounded by 32 bits.

Go Solution

func rangeBitwiseAnd(left int, right int) int {
    shiftCount := 0

    for left != right {
        left >>= 1
        right >>= 1
        shiftCount++
    }

    return left << shiftCount
}

The Go implementation is nearly identical to the Python version.

Go uses explicit variable declarations with :=, and the loop syntax differs slightly. Bit shifting behaves the same way for non-negative integers.

Since the problem guarantees values within 32-bit integer limits, there are no overflow concerns in this implementation.

Worked Examples

Example 1

Input:

left = 5
right = 7

Binary representation:

5 = 101
7 = 111
Step left right shift_count
Initial 101 111 0
Shift 1 10 11 1
Shift 2 1 1 2

Now left == right.

Restore the prefix:

1 << 2 = 100

Result:

4

Example 2

Input:

left = 0
right = 0
Step left right shift_count
Initial 0 0 0

The numbers are already equal, so no shifts occur.

Final result:

0 << 0 = 0

Example 3

Input:

left = 1
right = 2147483647

Binary:

1          = 000...0001
2147483647 = 111...1111

The numbers differ in almost every bit position.

After repeated right shifts, both eventually become 0.

Step left right
Initial 1 2147483647
... ... ...
Final 0 0

Restoring the prefix:

0 << shift_count = 0

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(32) At most one shift per bit position
Space O(1) Uses only a few variables

The algorithm removes one bit during each iteration. Since integers are limited to 32 bits, the loop executes at most 32 times.

This makes the runtime effectively constant.

The algorithm also uses no additional data structures, so the space complexity remains constant.

Test Cases

solution = Solution()

assert solution.rangeBitwiseAnd(5, 7) == 4          # Basic example
assert solution.rangeBitwiseAnd(0, 0) == 0          # Single zero
assert solution.rangeBitwiseAnd(1, 2147483647) == 0 # Large range collapsing to zero

assert solution.rangeBitwiseAnd(8, 8) == 8          # Same number
assert solution.rangeBitwiseAnd(10, 11) == 10       # Adjacent numbers
assert solution.rangeBitwiseAnd(12, 15) == 12       # Shared prefix remains
assert solution.rangeBitwiseAnd(26, 30) == 24       # Multiple differing lower bits
assert solution.rangeBitwiseAnd(0, 1) == 0          # Range including zero
assert solution.rangeBitwiseAnd(16, 31) == 16       # Power of two boundary
assert solution.rangeBitwiseAnd(31, 32) == 0        # Crossing major bit boundary
assert solution.rangeBitwiseAnd(1024, 2047) == 1024 # Large stable prefix
assert solution.rangeBitwiseAnd(1023, 1024) == 0    # Complete prefix change
Test Why
5, 7 Standard example with shared prefix
0, 0 Smallest possible input
1, 2147483647 Maximum range size
8, 8 Identical inputs
10, 11 Adjacent numbers
12, 15 Lower bits vary
26, 30 Multiple suffix bits removed
0, 1 Zero forces final answer to zero
16, 31 Stable high-order bit
31, 32 Crossing a power-of-two boundary
1024, 2047 Large range with common prefix
1023, 1024 Prefix changes completely

Edge Cases

One important edge case occurs when left == right. In this scenario, the range contains only a single number, so the answer must equal that number itself. Some incorrect implementations continue shifting unnecessarily or accidentally alter the value. This implementation handles the case naturally because the loop condition left != right immediately fails.

Another critical edge case happens when the range includes zero. Since bitwise AND with zero always produces zero, any range starting at zero must return zero. A brute-force implementation still works but wastes time. The optimal implementation quickly shifts both numbers until they become zero, correctly producing the result.

A particularly tricky case occurs when the range crosses a power-of-two boundary, such as [31, 32]. In binary:

31 = 011111
32 = 100000

No prefix bits remain stable, so the answer becomes zero. Many naive optimizations fail on this kind of transition because they do not correctly account for high-bit changes. The shifting approach handles this perfectly because all differing bits are removed until both numbers converge to zero.

Another subtle edge case involves very large ranges. For example:

left = 1
right = 2147483647

Iterating through every number would be infeasible. The optimal algorithm remains efficient because it performs only a constant number of bit shifts, independent of the range size.