LeetCode 201: Bitwise AND of Numbers Range

Problem Restatement

We are given two integers left and right.

They define an inclusive range:

[left, left + 1, left + 2, ..., right]

We need to return the bitwise AND of every number in that range.

The official statement says: given two integers left and right representing the range [left, right], return the bitwise AND of all numbers in this range, inclusive. The constraints are 0 <= left <= right <= 2^31 - 1.

Input and Output

Example function shape:

def rangeBitwiseAnd(left: int, right: int) -> int:
    ...

Examples

Example 1:

left = 5
right = 7

The numbers are:

5 = 101
6 = 110
7 = 111

Now compute:

101
& 110
& 111
= 100

So the answer is:

4

Example 2:

left = 0
right = 0

There is only one number in the range, so the answer is:

0

Example 3:

left = 1
right = 2147483647

This range crosses many powers of two and contains enough variation that every bit position becomes 0 after AND.

So the answer is:

0

First Thought: Brute Force

The direct solution is to AND every number in the range.

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

        for x in range(left + 1, right + 1):
            ans &= x

        return ans

This is easy to understand.

For example:

left = 5
right = 7

We compute:

ans = 5
ans = ans & 6
ans = ans & 7

The final answer is 4.

Problem With Brute Force

The range can be very large.

For example:

left = 1
right = 2147483647

A loop over every number would require more than two billion iterations.

So we need to use the structure of binary numbers instead of visiting every number.

Key Insight

Bitwise AND keeps a bit as 1 only when every number in the range has that bit set to 1.

If a bit changes from 0 to 1 or from 1 to 0 somewhere inside the range, then that bit becomes 0 in the final answer.

So the final answer is the common binary prefix of left and right.

For example:

left  = 5 = 101
right = 7 = 111

The common prefix is:

1__

The changing lower bits become 0.

So the answer is:

100 = 4

Another example:

left  = 26 = 11010
right = 30 = 11110

The common prefix is:

11___

The lower changing bits become 0.

So the answer is:

11000 = 24

Algorithm

We can find the common prefix by shifting both numbers right until they become equal.

Each right shift removes one lower bit.

We count how many bits we removed.

When left == right, the remaining value is the common prefix.

Then we shift it back left by the number of removed bits.

Steps:

1. Set shift = 0.
2. While left != right:
   1. Shift left right by one bit.
   2. Shift right right by one bit.
   3. Increase shift.
3. Shift left back left by shift.
4. Return the result.

Walkthrough

Use:

left = 5
right = 7

Binary:

left  = 101
right = 111

They are different, so shift both right.

left  = 10
right = 11
shift = 1

Still different. Shift again.

left  = 1
right = 1
shift = 2

Now they are equal.

The common prefix is:

1

Shift it back left by 2:

1 << 2 = 100

So the answer is:

4

Correctness

The bitwise AND of a range keeps only the bit positions that are 1 in every number from left to right.

When left and right differ at some binary position, the range between them must vary across lower positions. Those lower positions cannot remain fixed as 1 for every number in the interval. Therefore, every bit after the first differing position becomes 0 in the final AND.

The only bits that can survive are the shared leading bits of left and right.

The algorithm repeatedly shifts both numbers right. This removes lower bits until only the shared leading prefix remains. When the two shifted values become equal, that value is exactly the common prefix.

The algorithm then shifts the prefix back to its original position. The removed lower bits are filled with zeros, which matches the behavior of AND over the full range.

Therefore, the algorithm returns the correct bitwise AND of all numbers in [left, right].

Complexity

Since right <= 2^31 - 1, the loop runs at most 31 times.

Implementation

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

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

        return left << shift

Code Explanation

We start with:

shift = 0

This counts how many lower bits we remove.

The loop continues while the two numbers have different remaining prefixes:

while left != right:

Inside the loop, we remove one low bit from both numbers:

left >>= 1
right >>= 1

Then we record that one more bit was removed:

shift += 1

When the loop ends, left and right are equal. That value is the common prefix.

Finally:

return left << shift

This restores the prefix to its original bit position and fills the removed lower bits with zeros.

Alternative Implementation

There is another common solution using this identity:

right &= right - 1

This removes the lowest set bit of right.

We keep doing this while right > left.

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

        return right

This works because every removed bit is in a lower changing region that cannot survive the range AND.

The shifting version is often easier to explain. The right &= right - 1 version is shorter.

Testing

def run_tests():
    s = Solution()

    assert s.rangeBitwiseAnd(5, 7) == 4
    assert s.rangeBitwiseAnd(0, 0) == 0
    assert s.rangeBitwiseAnd(1, 2147483647) == 0
    assert s.rangeBitwiseAnd(8, 8) == 8
    assert s.rangeBitwiseAnd(26, 30) == 24
    assert s.rangeBitwiseAnd(10, 12) == 8

    print("all tests passed")

run_tests()