Bitwise AND of Numbers Range — Problem & Solution
Bitwise AND of Numbers Range solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Bitwise AND of Numbers Range is a medium coding problem on bit manipulation, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Bit Manipulation
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two integers left and right with left <= right, return the bitwise AND of every number in the inclusive range [left, right].
Example 1
Input: left = 5, right = 7
Output: 4
Example 2
Input: left = 0, right = 0
Output: 0
Example 3
Input: left = 1, right = 2147483647
Output: 0
Constraints
0 <= left <= right <= 2147483647The answer fits in a signed 32-bit integer.
Hints for Bitwise AND of Numbers Range
Hint 1
Any bit that changes anywhere in the range gets ANDed with a 0 somewhere, so it ends up 0.
Hint 2
Only the common binary prefix of
leftandrightsurvives.Hint 3
Shift both right until they match, then shift the result back by the same amount.
How to solve Bitwise AND of Numbers Range
Any bit that changes anywhere in the range is ANDed with a 0, so only the common binary prefix of left and right survives.
Approach
- Shift both right until they are equal, counting shifts.
- Shift the common value back left by that count.
Why it works
If left and right differ at bit b, then somewhere in between bit b flips and every lower bit cycles through 0, so all bits from b down are cleared; the prefix above b is shared by every number in the range.
Complexity
- Time —
O(log right) - Space —
O(1)
Pitfalls
- Iterating the range is far too slow when
right - leftis large.
Reference solution
Python
def rangeBitwiseAnd(left: int, right: int) -> int:
shift = 0
while left != right:
left >>= 1
right >>= 1
shift += 1
return left << shiftJava
public static int rangeBitwiseAnd(int left, int right) {
int shift = 0;
int a = left, b = right;
while (a != b) {
a >>>= 1;
b >>>= 1;
shift++;
}
return a << shift;
}C++
int rangeBitwiseAnd(int left, int right) {
int shift = 0;
unsigned int a = (unsigned int) left, b = (unsigned int) right;
while (a != b) {
a >>= 1;
b >>= 1;
shift++;
}
return (int) (a << shift);
}JavaScript
var rangeBitwiseAnd = function(left, right) {
let shift = 0;
let a = left, b = right;
while (a !== b) {
a = Math.floor(a / 2);
b = Math.floor(b / 2);
shift++;
}
return a * Math.pow(2, shift);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 146 bit manipulation problems · the whole catalogue
Learn the technique: Bit Manipulation