201. Bitwise AND of Numbers Range
Last updated
Last updated
/**
* 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;
}
}