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.
给出两个数字,把两个数字中所有的数相与。
显然真的求所有数相与是不可能的,我们思考一下:
对于两个数,如果他们不等,那意味着两个数及其之间一定包含一个偶数。
一个偶数的末位一定为0。
两个数如果不等,它之间的所有数的末位的与结果一定为0。
两个数如果相等,他们与完还是他们自己。
所以:
这个问题相当于找到两个数二进制表示时,高位完全相同的那部分,剩下的部分置0。
比如:
1010101010001101101001
1010100101010101010101
结果就是:
1010100000000000000000
这样就好解决了,我们不断把两个数右移,两个数不等时offset 就增,相等时就意味着着找到了相同的高位:
var rangeBitwiseAnd = function(m, n) {
var offset = 0;
while (m != n) {
m >>= 1;
n >>= 1;
offset++;
}
return m << offset;
};