Bitwise AND of Numbers Range — Common Prefix
Sanjeev SharmaAdvertisement
Problem
Return the bitwise AND of all numbers in range [left, right].
Key Insight
AND of a range = common binary prefix of left and right (lower bits all become 0 due to numbers in between).
Solutions
Python
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
shift=0
while left!=right: left>>=1; right>>=1; shift+=1
return left<<shift
C++
class Solution {
public:
int rangeBitwiseAnd(int l, int r){
int s=0; while(l!=r){l>>=1;r>>=1;s++;} return l<<s;
}
};
Complexity
- Time: O(log(max)) = O(32) | Space: O(1)
Advertisement
