给定范围数字按位与的结果
题目-给定范围数字按位与的结果
给一个数字范围 [m, n] ，同时 0 <= m <= n <= 2147483647, 求从m到n所有整数的按位与的结果
示例
结果： 5 & 6 & 7 = 4
转成二进制简单分析一下： 101 & 110 & 111 = 100
又是一道考察位操作Bit Operation的题，相似的题目在LeetCode中还真不少，比如Repeated DNA Sequences 求重复的DNA序列， Single Number 单独的数字, Single Number II 单独的数字之二 ， Grey Code 格雷码，和 Reverse Bits 翻转位 等等，那么这道题其实并不难，我们先从题目中给的例子来分析，[5, 7]里共有三个数字，分别写出它们的二进制为：
101 110 111
相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：
11010 11011 11100 11101 11110
发现了规律后，我们只要写代码找到左边公共的部分即可，我们可以从建立一个32位都是1的mask，然后每次向左移一位，比较m和n是否相同，不同再继续左移一位，直至相同，然后把m和mask相与就是最终结果。
其实也很好理解，找充分必要条件，所有的数字的公共位，肯定是首尾数字的公共位。首尾数字的公共位也是整个所有数字的公共位。
Just Try
请你自动动手试一下：在线编程环境想想有没有其他思路？
想想时间和空间复杂度，能否优化一下
真的做不到么？
let you think， think makes you happy!
参考答案
头尾右移比较
function algorithm(n){
let [x, y] = n;
let i = 0;
while(x != y){
x >>= 1
y >>= 1
i++;
}
return x << i
}
function main(param) {
console.show("参数：" + param, "结果：" + JSON.stringify(algorithm(param)))
testPerformance(algorithm, param)
}
main([5, 7]);
基于异或
有很多答案，我给个不一样的吧
function algorithm(n){
let m = n[0] ^ n[1];
// 高位补全
while(m.toString(2).length < n[0].toString(2).length){
m |= m<<1
}
return m & n[0] & n[1]
}
function main(param) {
console.show("参数：" + param, "结果：" + JSON.stringify(algorithm(param)))
testPerformance(algorithm, param)
}
main([5, 7]);
参考资料
http://www.cnblogs.com/grandyang/p/4431646.html
https://discuss.leetcode.com/topic/13508/one-line-c-solution
https://discuss.leetcode.com/topic/12133/bit-operation-solution-java
https://discuss.leetcode.com/topic/20176/2-line-solution-with-detailed-explanation