首页 > 其他 > 详细

【Leetcode】Bitwise AND of Numbers Range

时间:2016-05-22 12:23:46      阅读:276      评论:0      收藏:0      [点我收藏+]

题目链接:https://leetcode.com/problems/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.

思路:

32位整型,只需判断每一位在m~n之间是否有0存在,若有,该位 在AND操作中一定为0,只需判断32次

算法

[java] view plain copy
 技术分享技术分享
  1. public int rangeBitwiseAnd(int m, int n) {  
  2.         if (m == n)  
  3.             return m;  
  4.         int res = 0, i = 0;  
  5.         while (n != 0 && m != 0) {  
  6.             // 检查m~n是否有偶数存在时间复杂度O(1)  
  7.             boolean flag = false;  
  8.             for (int j = m; j <= n; j++) {  
  9.                 int tmp = j;  
  10.                 if ((tmp & 1) == 0) {// 最后一位为0  
  11.                     flag = true;  
  12.                     break;  
  13.                 }  
  14.             }  
  15.   
  16.             if (flag == false) {// 最低位全是1  
  17.                 res = res | (1 << i); // 将指定为置为1  
  18.             }  
  19.             i++;  
  20.             n = n >> 1;  
  21.             m = m >> 1;  
  22.         }  
  23.         return res;  
  24.     }  

【Leetcode】Bitwise AND of Numbers Range

原文:http://blog.csdn.net/yeqiuzs/article/details/51472675

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!