Bitwise AND of Numbers Range

 Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

 

Example 1:

Input: left = 5, right = 7

Output: 4

Example 2:

Input: left = 0, right = 0

Output: 0

Example 3:

Input: left = 1, right = 2147483647

Output: 0

class Solution {

    public int rangeBitwiseAnd(int left, int right) {

       

   int shift=0;

        while(left < right)

        {

           left >>= 1;

            right >>= 1;

            shift++;

        }

          // Shift back

        return left << shift;

    }

}

Logic:

 

👉 Idea:

• 🔹 Meaning of left < right

  We want to find the common prefix in binary between left and right.

  
  

  As long as left and right are different, there’s at least one bit position where they don’t match.

  
  

  That means the AND result can’t be final yet.

  
  

  So we keep shifting until they become equal.

  
  

  👉 The condition left < right just checks:

  
  

  “Have we removed enough differing bits so that left and right are the same?”

left = 16 → 10000

right = 20 → 10100

1. First loop:
   left (16) < right (20) → shift

   • left = 8 (01000)

   • right = 10 (01010)

2. Second loop:
   left (8) < right (10) → shift

   • left = 4 (00100)

   • right = 5 (00101)

3. Third loop:
   left (4) < right (5) → shift

   • left = 2 (00010)

   • right = 2 (00010)

Now left == right, so the loop stops. 

🔹 Why Stop When Equal?

When left == right, it means:

• All the differing (rightmost) bits are gone.

• Only the common prefix remains.

• That’s the part that will survive the AND operation.

Then we just shift it back to rebuild the number.

🔑 Key Idea

left < right → there are still different bits → keep shifting.
left == right → we found the common prefix → stop.