题目描述：

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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

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