`
SunnyYoona
  • 浏览: 361568 次
社区版块
存档分类
最新评论

[LeetCode]201.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.

思路

[5, 7]里共有三个数字(5,6,7),二进制分别为:

1 01  1 10  1 11

相与后的结果为100

[9, 11]里共有三个数字(9,10,11),二进制分别为:

1 001  1 010  1 011

相与后的结果为1000

[26, 30]里共有五个数字(26,27,28,29,30),二进制分别为:

11 010  11 011  11 100  11 101  11 110

相与后的结果为11000

仔细观察我们可以得出,我们要求出的结果就是给定范围内所有数的左边公共1的部分,其他位都为0。

代码

/*---------------------------------------
*   日期:2015-04-26
*   作者:SJF0115
*   题目: 201.Bitwise AND of Numbers Range
*   网址:https://leetcode.com/problems/bitwise-and-of-numbers-range/
*   结果:AC
*   来源:LeetCode
*   博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        if(m == 0){
            return 0;
        }//if
        int count = 0;
        while(m != n){
            // 左移一位
            m >>= 1;
            n >>= 1;
            ++count;
        }//while
        return m << count;
    }
};

int main(){
    Solution solution;
    int m = 9;
    int n = 11;
    int result = solution.rangeBitwiseAnd(m,n);
    // 输出
    cout<<result<<endl;
    return 0;
}

运行时间

这里写图片描述

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics