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

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

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

示例

给定:[5, 7]

结果: 5 & 6 & 7 = 4

转成二进制简单分析一下:    101 & 110 & 111 = 100

 

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国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » 给定范围数字按位与的结果

赞 (2) 打赏

评论 0

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

支付宝扫一扫打赏

微信扫一扫打赏