数字范围按位与

来源Leetcode第201题数字范围按位与

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

示例 1:

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

暴力

按顺序执行按位运算，然后有一个测试算例超时了，在运算时排除全0与全1的数，即到了0xFFFF和0x0就可以返回运算结果了。

public int rangeBitwiseAnd(int m, int n) {
    if(m == Integer.MAX_VALUE)
        return m;
    int ans = m++;
    while(m <= n) {
        ans &= m;
        if(ans == 0 || m == Integer.MAX_VALUE)
            break;
        m++;
    }
    return ans;
}

二进制1的个数

来源题解

此题其实就是寻找[m,n]范围内二进制数高位（左边）没有变化的数，后面补上0即为所求的结果。

判断m、n是否相等，如果不相等，m+1会使m的二进制数末位进位，有进位说明m的末位肯定有0的情况，0与任何数相与皆得0，所以结果的末位肯定是0。同理，不断右移1位进行比较，直到最终 m=n 时，说明找到了[m,n]这个范围内高位没有变化的数，左移相同位数得到的结果就是所求的值。

public int rangeBitwiseAnd(int m, int n) {
    if(m == Integer.MAX_VALUE || m == 0)
        return m;
    int count = 0 ; // 记录移位次数
    while(m < n){
        m >>>= 1;
        n >>>= 1;
        count ++;
    }
    return n <<= count;
}

二进制最右边1置0

有一个方法，可以把最右边的 1 置为 0，举个具体的例子。

比如十进制的 10，二进制形式是 1010，然后我们只需要把它和 9 进行按位与操作，也就是 10 & 9 = (1010) & (1001) = 1000，也就是把 1010 最右边的 1 置为 0。

规律就是对于任意一个数 n，然后 n & (n-1) 的结果就是把 n 的最右边的 1 置为 0 。

也比较好理解，当我们对一个数减 1 的话，比如原来的数是 ...1010000，然后减一就会向前借位，直到遇到最右边的第一个 1，变成 ...1001111，然后我们把它和原数按位与，就会把从原数最右边 1 开始的位置全部置零了 ...10000000。

public int rangeBitwiseAnd(int m, int n) {
    int zeros = 0;
    while (n > m) {
        n = n & (n - 1);
    }
    return n;
}