201. Bitwise AND of Numbers Range

题目描述和难度

• 题目描述：

输入: [5,7]
输出: 4

输入: [0,1]
输出: 0

• 题目难度：中等。
• 英文网址：201. Bitwise AND of Numbers Range 。
• 中文网址：201. 数字范围按位与 。

思路分析

求解关键：这道题如果按照常规做法，从小到大一个一个做按位与运算的话，会超时。因此，我们就要找规律了。 思路1： + 按位与运算是一种如果某个数位上出现了 0 ，结果就一定是 0 的运算。因此，我们可以罗列一些具体的数，找找规律。为此，编写如下代码。

public class Solution {

    /**
     * 暴力解法会超时
     * @param m
     * @param n
     * @return
     */
    public int rangeBitwiseAnd(int m, int n) {
        int res = m;
        for (int i = m + 1; i <= n; i++) {
            res &= i;
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int m = 200;
        int n = 230;
        int rangeBitwiseAnd = solution.rangeBitwiseAnd(m, n);

        for (int i = m; i <=n ; i++) {
            System.out.printf("%-3d %32s",i,Integer.toBinaryString(i));
            System.out.println();
        }

        System.out.println("结果：");
        System.out.printf("%-3d %32s",rangeBitwiseAnd,Integer.toBinaryString(rangeBitwiseAnd));
    }
}

203                         11001011
204                         11001100
205                         11001101
206                         11001110
207                         11001111
208                         11010000
209                         11010001
210                         11010010
211                         11010011
212                         11010100
213                         11010101
214                         11010110
215                         11010111
216                         11011000
217                         11011001
218                         11011010
219                         11011011
220                         11011100
221                         11011101
222                         11011110
223                         11011111
224                         11100000
225                         11100001
226                         11100010
227                         11100011
228                         11100100
229                         11100101
230                         11100110
结果：
192                         11000000

我们发现，结果只与这些数中最左边“最长”的相等的部分有关，因此，我们可以将 m 和 n 不断右移（题目中说了 m 和 n 不是负数，所以不存在右移符号位的问题），移到相等的时候为止。同时记录移动的步数。最后将相等的部分左移之前的步数（相当于补 0），就是最终要求的数。

思路2：位运算做得题多了，我们就会知道与运算的一条性质：n & (n - 1) 可以将 n 最右边的 1 变成 0 ，这件事情也是很酷的，因为其实不仅把 1 变成了 0，还跳过了很多 0，所以我们从暴力解法的反方向去思考，倒着做按位与，就可以很快得到解了。

参考解答

参考解答1

public class Solution {

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

参考解答2

public class Solution2 {

    /**
     * 利用了 n &= (n - 1) 一下能消死一大片
     *
     * @param m
     * @param n
     * @return
     */
    public int rangeBitwiseAnd(int m, int n) {
        while (n > m) {
            n &= (n - 1);
        }
        return n;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0201-bitwise-and-of-numbers-range ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。