给定范围数字按位与的结果

题目-给定范围数字按位与的结果

给一个数字范围 [m, n] ,同时 0 <= m <= n <= 2147483647, 求从m到n所有整数的按位与的结果

示例

给定:[5, 7]

结果: 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

知识共享署名4.0国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » 给定范围数字按位与的结果

赞 (3) 打赏

评论 0

如果对您有帮助,别忘了打赏一下宝宝哦!

支付宝扫一扫打赏

微信扫一扫打赏