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]中的所有数都AND起来，看最后的结果。当然暴力做就没什么意思了，也肯定会超时。

下面是我自己的做法，Discuss中也有同样的做法. 我的想法是这样的。

  1. 如果两个数a, b，相差 >= 1，那么[a, b]之间必定有一个数，他的最后(rightmost)一位是0.
  2. 然后，m和n都右移一位，可以判定倒数第二位是不是0，以此类推。
  3. 用i来记录右移的位数
  4. 当m == n的时候，说明m就是所求数字最左边的一部分，需要把右边的0补齐，也就是 m << i。
1
2
3
4
5
6
7
8
9
public int rangeBitwiseAnd(int m, int n) {
    int i = 0;
    while (m != n) {
        m = m >> 1;
        n = n >> 1;
        i++;
    }
    return m << i;
}

位运算奇妙无穷啊，这里贴几个别人不同的做法：
https://discuss.leetcode.com/topic/12093/my-simple-java-solution-3-lines/2

1
2
3
4
5
6
public int rangeBitwiseAnd(int m, int n) {
    int r = Integer.MAX_VALUE;
    while ((m & r) != (n & r))
        r = r << 1;
    return n & r;
}

https://discuss.leetcode.com/topic/20176/2-line-solution-with-detailed-explanation

1
2
3
4
5
public int rangeBitwiseAnd(int m, int n) {
    while (m < n)
        n = n & (n - 1);
    return n;
}