#201
Bitwise AND of Numbers Range
Medium Common prefix
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the bitwise AND of every integer from left to right inclusive.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: AND every number from left to right.
Why this works: any bit that changes somewhere in the range becomes 0. Only the shared starting bits (the common prefix) survive.
Example: left = 5 (101), right = 7 (111)
101 vs 111 → shift → 10 vs 11→ 1 vs 1 equal after 2 shifts1 << 2 = 100 = 4
✦Hints open one at a time
Any bit that flips somewhere in the range becomes 0 in the AND.
Only the common binary prefix of left and right survives.
↗Approach
Shift both numbers right until they are equal, counting the shifts. Then shift the common prefix back left. (Or repeatedly do right &= right - 1 while right > left.)
</>Solution (Java)
class Solution {
public int rangeBitwiseAnd(int left, int right) {
int shift = 0;
while (left != right) { // strip bits until only the shared prefix remains
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
}!Common mistake
Looping from left to right and ANDing every number — the range can have two billion numbers.
Complexity
- Time: O(32) = O(1).
- Space: O(1).
