Bitwise AND of Numbers Range

Problem Description

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

Examples

Constraints

• 0 ≤ left ≤ right ≤ 2³¹ - 1

Find the Common Prefix of left and right

Any bit that changes from 0 to 1 across the numbers in the range will be zeroed out in the final bitwise AND. The only bits that remain unaltered are those that are identical in both left and right from the most significant bit down to where they first differ.

In other words, the bitwise AND of a range is simply the common prefix of the binary representations of left and right, padded with trailing zeros.

To find it:

1. Shift both left and right rightward until they are equal.
2. Count the number of shifts shiftCount.
3. Shift the common value leftward by shiftCount to restore the zeros.

Solution: Common Prefix Shift

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shiftCount = 0;
        // shift right until left and right match (find the common prefix)
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shiftCount++;
        }
        return left << shiftCount;
    }
}

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

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int shiftCount = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shiftCount++;
        }
        return left << shiftCount;
    }
};

Complexity Analysis:

• Time Complexity: O(1) average/worst. Since the range numbers are 32-bit integers, the loop runs at most 32 times.
• Space Complexity: O(1).

Alternative: Clear the Lowest Set Bit (Brian Kernighan’s Algorithm)

Instead of shifting, we can iteratively clear the lowest set bit of right using right = right & (right - 1). As soon as right becomes ≤ left, right holds the common prefix.

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        while (right > left) {
            right &= (right - 1); // clears lowest set bit
        }
        return right;
    }
}

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

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

← All Problems