Bitwise AND of Numbers Range

描述

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.

分析

最简单的解法，遍历所有数，不断进行按位与，时间复杂度O(n)。这个做法太慢，不可接受。

先观察 [5,7]这个例子，5,6,7的二进制如下：

  1. 101
  2. 110
  3. 111

三个数按位与后结果为0，仔细观察这个过程我们可以得出，最后的结果是该范围内所有数的左边的共同部分，即公共左边首部(left header)。

我们再举一个更大的例子来感受一下，例如[26,30]，这些数的二进制如下：

  1. 11010
  2. 11011
  3. 11100
  4. 11101
  5. 11110

最后的结果是11000，果然是公共左边首部。

发现了规律后，这题就简单了，我们只需要写代码找到公共左边首部即可。

解法1

解法2

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/bitwise-operations/bitwise-and-of-numbers-range.html