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.

解题方法

brute force

显然最简单的就是将每个and一次，但是时间复杂度太高

找规律

我们已经知道x & (x-1)会消去x最右边为1的bit, 那么对于一个数y, y & (y+1)是同样的效果，y & ( y + 2)其实就能够bit 2设为0

那么这道题其实并不难，我们先从题目中给的例子来分析，[5, 7]里共有三个数字，分别写出它们的二进制为：

101　　110　　111

相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：

11010　　11011　　11100　　11101　　11110

发现了规律后，我们只要写代码找到左边公共的部分即可，然后每次向左移一位，比较m和n是否相同，不同再继续左移一位，直至相同， 然后再将m右移回去得到结果

Solution

class Solution(object):
    def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        numDiff = 0
        while m != n:
             m >>= 1
             n >>= 1
             numDiff += 1
        return m << numDiff

Reference