Bitwise AND of Numbers Range

Bit Manipulation

15 min

Problem Statement

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

Example

Example 1:

Input: left = 5, right = 7

Output: 4

Explanation:
5 = 0101
6 = 0110
7 = 0111
The bitwise AND of these numbers is 4 (0100).

Solution (Common Prefix)

The key insight is that the bitwise AND of a range of numbers is determined by their common most significant bits. Any bit that flips from 0 to 1 (or vice versa) within the range will result in a 0 in that position in the final AND result.

Therefore, the problem reduces to finding the common "left-side" prefix of the binary representations of left and right.

Algorithm Steps

Initialize a shift counter to 0.
While left is not equal to right:
Right-shift both left and right by 1.
Increment the shift counter.
Once left and right are equal, you have found the common prefix.
Left-shift the common prefix (left) by the shift count to get the final result.

left:

right:

Left

00000101

Right

00000111

Shifts

Initial state: left = 5, right = 7

Bitwise AND of Numbers Range Solution


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