201. 数字范围按位与

本题也可也换一个讲法:求[m,n]范围上的数的公共前缀

https://leetcode.cn/problems/bitwise-and-of-numbers-range/

方法1:从[left,right]范围循环,每个数进行相与

写一个 for 循环，依次相与即可:

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

超时！ 原因:当范围太大的话会造成超时

如何优化呢? 只需要在 res == 0 的时候提前出 for 循环即可

public int rangeBitwiseAnd(int m, int n) {
    int res = m;
    for (int i = m + 1; i <= n; i++) {
        res &= i;
        //如果res已经为0，后序再相与也是0
        if(res == 0) break;
    }
    return res;
}

遇到了错误案例:

解析:

右边界 n 是 2147483647，也就是 Integer 中最大的正数，二进制形式是 01111…1，其中有 31 个 1。在代码中当 i 等于 n 的时候依旧会进入循环。出循环执行 i++，我们期望它变成 2147483647 + 1 = 2147483648，然后跳出 for 循环。事实上，对 2147483647 加 1，也就是 01111…1 加 1，变成了 1000…000，其中有 31 个 1。而这个二进制在补码中表示的是 -2147483648。因此我们依旧会进入 for 循环，以此往复，直到结果是 0 才出了 for 循环

所以如何解决呢? 我们只需要判断 i == 2147483647 的话，就跳出 for 循环即可

public int rangeBitwiseAnd(int m, int n) {
    //m 要赋值给 i，所以提前判断一下
    //否则刚进循环的m+1就溢出了
    //m = INT_MAX --> n也是INT_MAX  a&a = a
    if(m == INT_MAX){
        return m;
    }
    int res = m;
    for (int i = m + 1; i <= n; i++) {
        res &= i;
        //当i已经到INT_MAX了,跳出循环！防止下一次判断之后执行i++导致溢出
        if(res == 0 ||  i == INT_MAX){
            break;
        }
    }
  	  return res;
}

方法2:利用规律

n&(n-1):我们每次对n进行该运算,其最右边的 1 会被抹去变成 0

基于上述技巧，我们可以用它来计算两个二进制字符串的公共前缀

其思想是:

• 对于给定的范围 [m,n]，我们可以对数字n 迭代地应用上述技巧，清除最右边的 1，直到它小于或等于 m，此时非公共前缀部分的 1 均被消去。因此最后我们返回 n 即可

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        //求公共前缀，本质就是去除非公共部分的 1 
        //给定两个整数，我们要找到它们对应的二进制字符串的公共前缀
        //求 m 和 n 的公共前缀，实际上就是把 m 和 n 非公共部分的 1 都敲掉，这个结果，一定小于等于 m 
         //即 res ≤ m ≤ n 
        //不断敲掉 n 最后一位 1，若此时 n 恰好小于等于 m ，说明已经将非公共部分的 1 全部敲掉
        
        //当right<=left时,此时right中保存的就是公共前缀！直接返回对应的值
        while(left < right)
        {
            right &=(right-1);
        }
        return right;
    }
};