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

题目大意:

给定范围[m, n],其中 0 <= m <= n <= 2147483647,返回范围内所有整数的按位与,包括边界。

例如,给定范围[5, 7], 你应该返回4。

 bin     dec
 101       5
 110       6
 111       7
-------------
 100       4

解题思路:

由数据范围0 <= m <= n <= 2147483647可知,时间复杂度O(n)及以上的解法是不可接受的。

因此可以判断此题为数学题。

参考LeetCode Discuss链接:https://leetcode.com/discuss/32053/accepted-c-solution-with-simple-explanation

[m, n]范围的按位与的结果为m与n的公共“左边首部(left header)”

Python代码:

class Solution:
    # @param m, an integer
    # @param n, an integer
    # @return an integer
    def rangeBitwiseAnd(self, m, n):
        p = 0
        while m != n:
            m >>= 1
            n >>= 1
            p += 1
        return m << p

 

本文链接:http://bookshadow.com/weblog/2015/04/17/leetcode-bitwise-and-numbers-range/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论