Leetcode 201 Bitwise And of Numbers Range

这道题是求区间内所有数相与的值，首先想到的就是暴力循环求解，什么都不做直接循环求值，会超时。所以加上了一个提前退出的判断方法：出现了0。这种方法虽然很慢，但能AC，需要注意的是，中间变量可能有越界int类型的可能，所以变为long类型。代码如下

int rangeBitwiseAnd(int m, int n) {  // 420 ms
  long res = static_cast<long> (m);
  for (long i=res+1; i<=n; ++i)
    if (res == 0)
      return 0;
    else
      res &= i;
  return static_cast<int>(res);
}

但是我们刷题，遇到一道有趣的题目，总要多思考，寻求高效的算法。 再看这道题，求区间内的数字相与的结果。与操作，只有参与与操作的所有数都是1的时候，这个1才能被保留，只要有一个是0，那结果就是0。以题目中的 [5, 7] 举例具体说明。

这三个数相与，结果是4，二进制表示为100。相同的位相与，出现过0的，结果位便是0，全是1的位，结果中相应的位才能是1。 再看一个例子 [13, 17]

没有哪一位全是1，所以结果为 0。

在 [m, n] 区间内的整数，越低的位，0-1-0 变化的越频繁，较高的位，出现 0 或者 1 的情况更“稳定”。注意到这种现象，我们意识到只需要考虑区间首尾两个数的位情况即可。从高位向低位遍历，出现相同的 1，则后面的相同的位开始有意义，当某一位不同时，后面的数相同与否就变得没有意义了，因为在[m, n]区间内，一定存在一个数，在该位是 0，使区间内所有数相与的结果中该位为 0 。

虽然在理解算法的时候，我们从高到低遍历，但是在写代码时，从低到高更容易实现。依次删除最后一位，直到 m 与 n 剩下的位相等，记下删除的位数，最后在相同的前缀中，填入删除的位数个的 0，就是答案。注意，我们可以通过判断区间开始是否为 0 来提前退出循环。

int rangeBitwiseAnd(int m, int n) {
  int count = 0;
  while (m && m != n) {
    m >>= 1;
    n >>= 1;
    ++count;
  }
  return m << count;
}

另一种写法

int rangeBitwiseAnd(int m, int n) {
  while(n > m) n = n & (n-1);
  return n;
}

#直达链接

LeetCode 201. Bitwise AND of Numbers Range