题意

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

样例

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

1. 解题思路

  这个题的意思非常的简单，就是要求计算[m, n]之间所有数字与远算的值。用常规方法可以很简单的写出来，但是意料之中就是超时，那么有什么比较取巧的方法吗？当然有并且有很多种，这里我只介绍我自己的解题思路。
  首先，我们知道最终的结果无非就是一个int值，也就是说最大位数为32位，只要我们能求出每个位置上的值(0或者1)，那么就能得到最终的答案。那怎么可以计算出来呢？
  我们来看一个规律:

  上面规律很容易得出来，如果数字个数已经超过某个2进制位数表示范围，那么与运算最终结果这一位肯定为0。

2. 代码

  下面我们来看一下实现。

    public int rangeBitwiseAnd(int m, int n) {
        int bitCount = 0;
        int count = n - m + 1;
        for (int i = 0; i < 32; i++) {
            long result1 = 1L << i;
            long result2 = 1L << (i + 1);
            if (n >= result1 && n < result2) {
                bitCount = i;
                break;
            }
        }
        int a[] = new int[bitCount];
        for (int i = 0; i < bitCount; i++) {
            a[i] = 1;
        }
        for (int i = 0; i <= bitCount; i++) {
            int result = 1 << i;
            if (count > result) {
                // 超过范围，直接为0
                a[bitCount - i] = 0;
            } else {
                // 未超过范围，得看所有数字这一位是否都为1
                // 如果都为1，那么为1，反之为0
                // 计算所有数字这一位数字是否都为1，直接计算最小值和最大值的这一位是否为1
                a[bitCount - i] = ((result & m) != 0) && ((result & n) != 0) ? 1 : 0;
            }
        }
        int result = 0;
        for (int i = 31; i >= 0; i--) {
            result += a[i] * (1 << (31 - i));
        }
        return result;
    }