Bitwise AND of Numbers Range
Medium· bit prefix
Problem
Given two integers left and right, return the bitwise AND of every integer between them, inclusive. The range can be huge, so iterating over it is not an option.
Examples
Input: left = 5, right = 7
Output: 4
101 & 110 & 111 = 100.
Input: left = 1, right = 2147483647
Output: 0
Constraints
- • 0 <= left <= right <= 2^31 - 1
Hints & approach
Hint 1
Any bit that flips somewhere in the range becomes 0 in the result.
Hint 2
Only the leading bits shared by left and right survive.
Hint 3
Shift both right until they are equal, then shift back.
Approachtry the hints first
Counting from left to right, every bit below the highest differing bit takes both values 0 and 1, so it ANDs to 0. The answer is therefore the common binary prefix of left and right followed by zeros. Shift both numbers right until they match, counting shifts, then shift the common value back left by that count.
Time O(log right) · Space O(1)