leetcode 201 Bitwise AND of Numbers Range
z
 2019-04-07 16:34:20  

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]中，每一个数的每一位上的AND操作之后得到的数值。例如：

  • [5,7]：

    • 0 0 1 0 1

      0 0 1 1 0

      0 0 1 1 1

      -—–

      0 0 1 0 0

  • [0, 1]:

    • 0 0 0 0

      0 0 0 1

      -—-

      0 0 0 0

  • 其实就相当于是求二进制的最长的公共前缀

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int move = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            move ++;
        }
        return n << move;
    }
}