17
04/2015
[LeetCode] Bitwise AND of Numbers Range
Bitwise AND of Numbers Range
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.
解题思路：
这道题的意思是，计算从m到n的非负整数的按位与值。太牛逼了，我想了好久都是计算超时。结果其实就是m和n公共头部。例子中5的二进制为101,7的二进制位111，其公共头部为100。再如，若计算3到5的按位或，3的二进制位11，5的二进制位101，没有公共头部，返回0。
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
if(m>n){
return 0;
}
int i=0;
while(m!=n&&m!=0){
m >>= 1;
n >>= 1;
i++;
}
return m<<i;
}
};这是一类非常有意思的题目。我在网上还看到了，计算[m, n]的非负整数的按位异或。一种解法非常巧妙：
long long f(long long a) {
long long res[] = {a,1,a+1,0};
return res[a%4];
}
long long getXor(long long a, long long b) {
return f(b)^f(a-1);
}为什么这个代码能够工作呢？让我们先看看4位二进制的从0到a的按位异或。
0000 <- 0 [a] 0001 <- 1 [1] 0010 <- 3 [a+1] 0011 <- 0 [0] 0100 <- 4 [a] 0101 <- 1 [1] 0110 <- 7 [a+1] 0111 <- 0 [0] 1000 <- 8 [a] 1001 <- 1 [1] 1010 <- 11 [a+1] 1011 <- 0 [0] 1100 <- 12 [a] 1101 <- 1 [1] 1110 <- 15 [a+1] 1111 <- 0 [0]
上述代码中，我们看到，f函数其实就是返回[0, a]的按位异或。对于主体函数，f(b)表示从[0, b]的异或，f(a-1)表示[0, a-1]的异或，f(b)^f(a-1)则等于[a, b]的异或。因为任何数异或自身都为0。
0 条评论