Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
Example 1:
Input: [5,7] Output: 4
Example 2:
Input: [0,1] Output: 0
Related Topics:
Bit Manipulation
// OJ: https://leetcode.com/problems/bitwise-and-of-numbers-range/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int ans = 0;
for (int i = 0; i < 31; ++i) {
int k = 1 << i, a = m / k, b = n / k;
ans |= (a == b && a % 2) << i;
}
return ans;
}
};
// OJ: https://leetcode.com/problems/bitwise-and-of-numbers-range/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int count = 0;
while (m && n && m != n) {
m >>= 1;
n >>= 1;
++count;
}
return m << count;
}
};
// OJ: https://leetcode.com/problems/bitwise-and-of-numbers-range/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
while (m < n) n = n & (n - 1);
return n;
}
};