Bitwise AND of Numbers Range
1. Description
Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.
2. Example
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
3. Constraints
- 0 <= left <= right <= $2^{31}$ - 1
4. Solutions
Bit Operations
n = right
Time complexity: O(logn)
Space complexity: O(n)
class Solution {
public:
int rangeBitwiseAnd(const int left, const int right) {
int shift = 0;
int i = left, j = right;
while (i < j) {
i >>= 1;
j >>= 1;
++shift;
}
return i << shift;
}
};