题目大意：
数字范围按位与
给定范围 [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; 在思考如何优化之前，我们应该先思考一下按位与的特性：
- 数字0与任何数进行按位与的结果一定是0。
- 如果两个二进制数的长度不同，他们进行按位与的结果也一定是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-解题思路分析/