leetcode201.Bitwise AND of Numbers Range

发表于 更新于 分类于 ，

题目要求

1
2
3
4
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.

给一个闭区间[m,n]，对该闭区间的所有数字进行与（and）运算。
与预算是指 1 and 1 = 0, 1 and 0 = 0, 0 and 1 = 0, 0 and 0 = 0。
这里都是以二进制为基础进行与运算。在计算机底层所有的十进制数都是以二进制数进行存储的。写这道题目之前需要先去了解十进制转二进制以及未操作符>>,>>>和<<。

思路和代码

其实可以想到，如果一个区间含有偶数，那么这个区间中一定有一个数，其二进制的末位为0，那么就意味着这些数在该位上的与运算结果一定为0。
计算完末位后，我们来计算倒数第二位的与运算。这就相当于将[m, n]区间转化为[m/2,n/2]区间，在该区间上我们再来判断是否包含偶数。
在一番尝试之后，我们会发现，如果一个区间[m,n]，当m不等于n时，其中一定包含偶数，即该末位的和运算一定为0。
因此，当我们同时左移m,n时，一定会有一个时刻，使得m与n相等。这意味着，从该位起前面的所有位数值均相等。它们进行任何与运算一定等于它们本身。我们可以直接将这些位的内容添加到结果集开头。

代码如下：

1
2
3
4
5
6
7
8
9
10
public int rangeBitwiseAnd(int m, int n) {
    if(m==n) return m;
    int count = 0;
    while(m<n){
        count++;
        m >>>= 1 ;
        n >>>= 1;
    }
    return m<<=count;
}

优化后代码如下：

1
2
3
4
5
6
7
8
9
10
public int rangeBitwiseAnd2(int m, int n) {
    if(m==n) return m;
    int count = 1;
    while(m<n){
        count <<= 1;
        m >>>= 1 ;
        n >>>= 1;
    }
    return m * count;
}