05 August 2008
Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.
Example 1:
1
2
Input: left = 5, right = 7
Output: 4
Example 2:
1
2
Input: left = 0, right = 0
Output: 0
Example 3:
1
2
Input: left = 1, right = 2147483647
Output: 0
Constraints:
1
0 <= left <= right <= 231 - 1
数字范围按位与
The idea is very simple:
1
2
3
last bit of (odd number & even number) is 0.
when m != n, There is at least an odd number and an even number, so the last bit position result is 0.
Move m and n rigth a position.
Keep doing step 1,2,3 until m equal to n, use a factor to record the iteration time.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
/*
等价于 求 m 与 n 二进制编码中 同为1的前缀.
*/
public int rangeBitwiseAnd(int m, int n) {
if(m == 0){
return 0;
}
int moveFactor = 1;
while(m != n){
m >>= 1;
n >>= 1;
moveFactor <<= 1;
}
return m * moveFactor;
}
}