Bitwise AND of Numbers Range

How it works

Instead of shifting both numbers, we can repeatedly clear the rightmost set bit of right until right becomes less than or equal to left. The operation (n & (n-1)) clears the lowest set bit of n. This works because any bit position where right has a 1 but needs to flip within the range will be cleared, leaving only the common prefix.

Steps

1. While left is less than right:
   • Apply the operation right = right AND (right - 1) to clear the rightmost set bit of right.
2. Return right (which now equals the common prefix with trailing zeros).

Complexity

• Time complexity: O(1)
• Space complexity: O(1)

Things to watch for

Iterating Through All Numbers in the Range

The brute force approach of ANDing every number from left to right will time out for large ranges. For example, when left = 1 and right = 2^31 - 1, this requires billions of operations.

Misunderstanding the Common Prefix Property

The result is the common binary prefix of left and right with trailing zeros. A common mistake is trying to AND only left and right directly, missing that intermediate values determine which bits survive.

Integer Overflow in Bit Calculations

When calculating (1 << (i + 1)) for bit position 31, the result exceeds 32-bit signed integer range in some languages. Use unsigned types or 64-bit integers to avoid overflow.

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

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        while (left < right) {
            right &= (right - 1);
        }
        return right;
    }
};