Question:
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
Thinking:
It’s bitwise operation question. Some other questions like are Single Number, Single Number II, Reverse Bits, Repeated DNA Sequences, Grey Code and so on and so forth. This question’s point is to find all the numbers between the range and use the bitwise AND on them.
For example, in the range of [5, 7], there are three numbers:
101 110 111
Result of thier bitwise is 100.
What’s more, in the example of [26, 30]:
11010 11011 11100 11101 11110
The result is 11000.
Because bits are incresing from the right (low digits), the left of all the numbers are not going to change in the process. The thing we need to do is finding the common part of the left. There are two solutions:
Solution1:
Idea: State a variable and make it all 1 in all digits. Make the variable left shift every time to check if it’s equal between m and n of their bitwise AND. Finally, the result of m bitwise AND with the variable is the answer.
Code:
class Solution {
public int rangeBitwiseAnd(int m, int n) {
int d = Integer.MAX_VALUE;
while ((m & d) != (n & d)) {
d <<= 1;
}
return m & d;
}
};
Solution2:
Idea:Let m and n make left shift each time if they are different and record the times i they shift. When they are equal, the result of m left shift i is the answer.
Code:
class Solution {
public int rangeBitwiseAnd(int m, int n) {
int i = 0;
while (m != n) {
m >>= 1;
n >>= 1;
++i;
}
return (m << i);
}
};