Bitwise AND of Numbers Range

• medium
• tag: math, bit
• similar: bit题目

• 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.

思路

• 一开始没有思路, 只能一个个的AND.
• 看了答案, 才发现原来这个题目是找max prefix of two binary number. 参考cnblog, 例如:
  • 看一个范围[26, 30]，它们的二进制如下：
  • 11010　　11011　　11100　　11101　　11110
  • 最后的结果是11000. 所以就是找max prefix, 但是怎么找呢?

idea 1:

• 参考的discuss, 代码如下

public int rangeBitwiseAnd(int m, int n) {
    int moveFactor = 1;
    while (m != n) {
      m >>= 1;
      n >>= 1;
      moveFactor <<= 1;
    }
    return m * moveFactor;
  }