Code Implementation

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shift = 0
        # Find the common prefix
        while left < right:
            left >>= 1
            right >>= 1
            shift += 1
        return left << shift
    

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }
};
    

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }
}
    

var rangeBitwiseAnd = function(left, right) {
    let shift = 0;
    while (left < right) {
        left >>= 1;
        right >>= 1;
        shift++;
    }
    return left << shift;
};
    

Problem Description

The "Bitwise AND of Numbers Range" problem asks you to compute the result of the bitwise AND operation on all integers in the inclusive range between two given integers, left and right. In other words, you need to find the value of left & (left + 1) & (left + 2) & ... & right.

• left and right are both non-negative integers, and left <= right.
• The range can be very large (up to 2³¹-1), so efficiency is important.
• Your answer must be a single integer representing the bitwise AND of all numbers in the range.

Thought Process

At first glance, you might consider iterating through every number from left to right and applying the bitwise AND operation. This brute-force approach works for small ranges, but quickly becomes infeasible for large ranges because it would require looping through potentially billions of numbers.

To optimize, we need to observe what happens to the bits during the AND operation. For any bit position, if that bit changes from 1 to 0 anywhere in the range, the result for that bit will be 0. Therefore, the only bits that remain set are those that are the same for every number in the range — in other words, the common prefix of left and right in binary.

Solution Approach

The key insight is that the result of the bitwise AND is the common leftmost bits (prefix) shared by left and right. Any bit that differs between left and right (and all less significant bits) will be zeroed out in the final result.

• Step 1: While left is less than right, right-shift both left and right by one bit. Keep track of the number of shifts.
• Step 2: When left equals right, we've found the common prefix. All differing bits to the right have been shifted off.
• Step 3: Left-shift the common prefix back by the number of shifts to restore its original position, filling the lower bits with zeros.

This approach is efficient because it only requires as many iterations as there are bits in the numbers (at most 31 or 32 for typical integers), rather than looping through the entire range.

Example Walkthrough

Example: left = 26, right = 30

• Binary of 26: 11010
• Binary of 30: 11110

Let's follow the algorithm:

1. Initial: left = 26 (11010), right = 30 (11110), shift = 0
2. Since left < right, shift both:
   • left = 13 (1101), right = 15 (1111), shift = 1
3. Still left < right, shift again:
   • left = 6 (110), right = 7 (111), shift = 2
4. Still left < right, shift again:
   • left = 3 (11), right = 3 (11), shift = 3
5. Now left == right, so common prefix = 3 (11). Shift back by 3:
   • Result = 3 << 3 = 24 (11000)

The AND of all numbers from 26 to 30 is 24.

Time and Space Complexity

• Brute-Force Approach:
  Time Complexity: O(N), where N is right - left + 1.
  Space Complexity: O(1).
  This is inefficient for large ranges because N can be up to 2³¹.
• Optimized Approach (Common Prefix):
  Time Complexity: O(1) relative to the range size, but in practice O(32) since we shift at most 32 times (number of bits in an integer).
  Space Complexity: O(1), as we use only a few variables.
  This makes the solution extremely efficient even for very large ranges.

Summary

The "Bitwise AND of Numbers Range" problem can be solved efficiently by recognizing that only the common leftmost bits of left and right survive the AND operation across the range. By shifting both numbers right until they match, and then shifting the result back, we avoid iterating through the entire range. This insight leads to a concise, elegant, and highly efficient solution that works for even the largest allowed input sizes.