Problem 34.10 · Bit ManipulationMedium

Bitwise AND of Numbers Range

What it teaches: The AND of a range keeps only the common binary prefix of its ends.

Practise it on judges as “Bitwise AND of Numbers Range”.

The problem

Return the bitwise AND of all integers in [left, right].

Example 1

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

101 & 110 & 111 = 100.

Constraints

0 ≤ left ≤ right ≤ 2³¹ − 1

Pattern clues in the wording

→ AND over a huge range

These clues point to Bit Manipulation: Use XOR, AND, OR and shifts to test, set and cancel bits, often in O(1) space.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	left = 5 right = 7	4
2	left = 0 right = 0	0
3	left = 1 right = 2147483647	0

From slow to fast

Approaches

1. Common prefix · O(32)2. Clear right's low bits · O(number of ones)

Common prefix

Time O(32) Space O(1)

Shift left and right down together counting shifts until equal; shift back up.

Approach 1

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

Verdict: Never touches the range itself.

Clear right's low bits

Time O(number of ones) Space O(1)

While right > left: right &= right − 1 (drop its lowest set bit).

Approach 2

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

Verdict: Same prefix, different route.

Before you submit

Edge cases and common mistakes

Test these inputs

left == right
Range crossing a power of two (0 below it)

Mistakes people make

Looping from left to right (up to 2³¹ iterations).

Interview

Follow-up questions

What about the OR of a range?