LeetCode 201. Bitwise AND of Numbers Range

Posted on | In |
Words count in article: 124 | Reading time ≈ 1

题目

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

1
2
Input: [5,7]
Output: 4

Example 2:

1
2
Input: [0,1]
Output: 0

思路

数学题。
[m, n]范围的按位与的结果即为m与n的公共左边首部，所以将m和n右移到公共部分再左移还原即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        i = 0
        while n != m:
            n >>= 1
            m >>= 1
            i += 1
        return m << i