Problem Statement

You are given two integers left and right representing a range [left, right] (inclusive).
You need to find the bitwise AND of all numbers in this range.

Example

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

Explanation:

5 = 101  
6 = 110  
7 = 111  
Bitwise AND of (101 & 110 & 111) = 100 = 4

Understanding the Problem

The bitwise AND (&) operation compares each bit of two numbers:

• If both bits are 1, the result is 1.
• Otherwise, the result is 0.

If we take the AND of a continuous range of numbers, we will notice that as the range increases, more bits turn to zero. This happens because as numbers increase, lower bits keep flipping between 0 and 1, so they eventually cancel out to 0 in the AND operation.

For example:

• Range [5, 7] → 5 (101), 6 (110), 7 (111) → common prefix bits are 100.
• So, the result is 4.

Thinking About the Approach

Naive Thinking (Brute Force):
You might first think of directly performing the AND operation on every number from left to right:

int result = left;
for (int i = left + 1; i <= right; i++) {
    result &= i;
}
return result;

While this works for small ranges, it is very slow when right - left is large (for example, millions or billions).
So we need a more efficient mathematical or bit-based approach.

Key Observation

When numbers are close together, their binary forms share common higher-order bits, but lower-order bits change frequently.
For example:

Number	Binary
5	101
6	110
7	111

The common prefix is 1 (in the hundreds place), and the rest differs.
The answer is this common prefix with zeros for the differing part: 100 (which is 4).

This means the problem can be rephrased as:

Find the common prefix (in binary) of all numbers between left and right.

Efficient Solution Idea

We repeatedly shift both left and right to the right (dividing by 2) until they become equal.
Every time we shift, we count how many times we shifted.
The remaining equal number represents the common prefix.
Then we shift it back left by the same count (multiplying by 2 repeatedly) to fill the zeros.

Step-by-Step Example

Let left = 5, right = 7.

1. left = 5 (101), right = 7 (111)
   They are not equal → shift both right by 1.
   • left = 2 (10)
   • right = 3 (11)
   • shift count = 1
2. Again, not equal → shift both right by 1.
   • left = 1 (1)
   • right = 1 (1)
   • shift count = 2

Now they are equal (1).

We shift back left by the same number of times:

1 << 2 = 100 (binary) = 4

Result = 4

Java Code Implementation

public class BitwiseAndOfNumbersRange {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        
        // Keep shifting until left and right become equal
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        
        // Shift back to get the final result
        return left << shift;
    }
}

Explanation of Code

1. Initialize shift to 0: this counts how many bits we have shifted.
2. While loop (left < right):
   • As long as left and right differ, shift both one bit to the right.
   • Each shift removes one differing bit from the rightmost side.
3. After loop:
   • When left equals right, we have found the common prefix.
4. Shift back (left << shift):
   • We restore the prefix to its original bit position.

Complexity Analysis

Time Complexity: O(log(max(left, right)))
We shift at most once per bit, so it depends on the number of bits in the input (up to 31 shifts for integers).

Space Complexity: O(1)
We use only a few variables, no extra data structures.

Another Way of Thinking

Another approach to find the same result is to keep clearing the least significant bit of right until right becomes less than or equal to left.

public int rangeBitwiseAnd(int left, int right) {
    while (right > left) {
        right = right & (right - 1);  // clear the rightmost set bit
    }
    return right;
}

This method works because each time we clear a bit in right, we eliminate part of the range that differs. Eventually, both left and right will share the same prefix.

Summary

1. The goal is to find the common prefix of all numbers between left and right.
2. A direct loop works but is too slow for large ranges.
3. The efficient solution uses bit shifting to find the shared prefix.
4. Time complexity is logarithmic in the number of bits, making it very efficient.