LEETCODE 201. Bitwise AND of Numbers Range 解题思路分析

题目大意：

数字范围按位与

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例 1: 

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

示例 2:

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=201

解题思路分析：

看完本题的数据规模后，心里一凉，发现暴力解是行不通的。不过好在我们可以通过剪枝操作来达到优化的效果，因此暴力解法是本题的基础。接下来我们先看下原始版本的代码：

    int res=m;
    for(int i=m+1;i<=n;i++){
        res &= i;
    }
    return res;

在思考如何优化之前，我们应该先思考一下按位与的特性：

1. 数字0与任何数进行按位与的结果一定是0。
2. 如果两个二进制数的长度不同，他们进行按位与的结果也一定是0。

上面两个知识点是我们本题优化的关键所在，首先我们来求出两个数字的二进制长度并进行比较，如果不一致，直接返回0。这一步剪枝至关重要，这使得剩下的分支中，m和n的差距大大降低，这也就大幅减少了循环的次数。接下来我们需要按照上面暴力解的方式从m循环至n，计算出所有数字的按位与。不过，在循环过程中，当我们遇到了值为0的中间结果时，根据按位与的第一条特性，最终结果一定是0，因此此时可中断退出循环。

不过到这里还没有结束，先看下目前为止的代码：

public int rangeBitwiseAnd(int m, int n) {
    // 如果两个数字的二进制长度不同，返回0
    if(Integer.toBinaryString(m).length()!=
      Integer.toBinaryString(n).length()){
        return 0;
    }
    int res=m;
    for(int i=m+1;i<=n;i++){
        res &= i;
        if(res == 0){
            break;
        }
    }
    return res;
}

看似天衣无缝的代码，提交后，竟然错在了下面这个例子上：

输入：
2147483646
2147483647

输出：
0 （错误）

正确答案：
2147483646

想了半天才反应过来，原因出在java语言Integer型数字的最大值问题上（其他语言可能没事）。java中int的最大值是2147483647，当i循环完2147483647并进行加一操作时，i并不会变成2147483648（int越界），而是会变成0，此时循环继续，0再与之前的结果进行按位与操作后结果变为0，退出循环，造成返回结果是0。因此修改后的最终代码如下：

public int rangeBitwiseAnd(int m, int n) {
    // 如果两个数字的二进制长度不同，返回0
    if(Integer.toBinaryString(m).length()!=
      Integer.toBinaryString(n).length()){
        return 0;
    }
    // 如果两个数字相同，返回m
    // 此处实际上是为了避免m等于MAX_VALUE
    if(m == n){
        return m;
    }
    int res=m;
    for(int i=m+1;i<=n;i++){
        res &= i;
        // 如果res为0，或者i已经循环至MAX_VALUE
        if(res == 0 || i == Integer.MAX_VALUE){
            break; // 退出循环
        }
    }
    return res;
}

本题解法执行时间为5ms。

Runtime: 5 ms, faster than 43.16% of Java online submissions for Bitwise AND of Numbers Range.

Memory Usage: 39 MB, less than 10.00% of Java online submissions for Bitwise AND of Numbers Range.

实际上本题还存在其他解法，看了很多大神的帖子，发现通过纯粹的二进制运算的解法效率更高，这里暂且掠过（偷懒）。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-201-bitwise-and-of-numbers-range-解题思路分析/