数字范围按位与

Problem: 201. 数字范围按位与

基本思路

根据与运算的性质，只要区间内的任意数在某一位出现，那么该位的最终结果为。

从的过程，二者的公共前缀肯定不会变化。

设非公共前缀分别为序列，。

对于：成立；

对于：

若，由于需要为或进，故 区间必有一个数使得成立；

若，则成立。

可据此推广到剩余序列，。

根据上述分析可知，最终结果的非部分只可能来自二者的公共前缀。

解题方法

通过异或运算 diff = left ^ right，二者的公共前缀长度即为 diff 变量的最长前缀的长度。故只需将 diff 向左移动直到 diff == 0 成立时的最小偏移量 shift 即为非公共前缀的长度。最终利用掩码 0xffffffff << shift & right 即得到结果。

Java


class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int diff = left ^ right;
        int shift = 0;
        while (diff != 0) {
            shift++;
            diff >>= 1;
        }
        return right & 0xffffffff << shift;
    }
}

Python3


def rangeBitwiseAnd(left: int, right: int):
    diff = left ^ right
    shift = 0
    while diff != 0:
        shift += 1
        diff >>= 1
    return right & 0xffffffff << shift

TypeScript


var rangeBitwiseAnd = (left: number, right: number) => {
    let diff: number = left ^ right;
    let shift: number = 0;
    while (diff != 0) {
        shift++;
        diff >>= 1;
    }
    return right & 0xffffffff << shift;
}

JavaScript


var rangeBitwiseAnd = (left, right) => {
    let diff = left ^ right;
    let shift = 0;
    while (diff != 0) {
        shift++;
        diff >>= 1;
    }
    return right & 0xffffffff << shift;
}


public class Solution {
    public int RangeBitwiseAnd(int left, int right) {
        int diff = left ^ right;
        int shift = 0;
        while (diff != 0) {
            shift++;
            diff >>= 1;
        }
        return right & 0xffffffff << shift;
    }
}


int rangeBitwiseAnd(int left, int right) {
    int diff = left ^ right;
    int shift = 0;
    while (diff != 0) {
        shift++;
        diff >>= 1;
    }
    return right & 0xffffffff << shift;
}

复杂度分析

时间复杂度: 。

空间复杂度: 。