Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
GeeksforGeeks
YouTube
Input: [5, 7]
Output: 4
Input: [0, 1]
Output: 0
Last updated
Was this helpful?
Was this helpful?
/**
* Time complexity : O(1). Although there is a loop in the algorithm,
* the number of iterations is bounded by the number of bits that an
* integer has, which is fixed.
* Space complexity : O(1). The consumption of the memory for our algorithm
* is constant, regardless the input.
*/
class Solution {
public int rangeBitwiseAnd(int m, int n) {
int shift = 0;
// find the common 1-bits
while (m < n) {
m >>= 1;
n >>= 1;
++shift;
}
return m << shift;
}
}/**
* Time complexity : O(1). Although there is a loop in the algorithm,
* the number of iterations is bounded by the number of bits that an
* integer has, which is fixed.
* Space complexity : O(1). The consumption of the memory for our algorithm
* is constant, regardless the input.
*/
class Solution {
public int rangeBitwiseAnd(int m, int n) {
while (m < n) {
// turn off rightmost 1-bit
n = n & (n - 1);
}
return m & n;
}
}