201-数字范围按位与

LeetCode 201. Bitwise AND of Numbers Range

LeetCode-201

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

method

只要找到left到right的公共前缀就可以了，除了公共前缀，其他部分都会出现0和1交替的情况，按位与之后就都是0

所以left和right每次右移一位，相等的时候就得到了公共前缀，再记录右移了几次，再左移回去，就可以把除了公共前缀的其他部分置0

int rangeBitwiseAnd(int left, int right) {
    int cnt = 0;
    while (left < right) {
        left >>= 1;
        right >>= 1;
        cnt++;
    }
    return left << cnt;
}

• x & x-1可以将x最右边的1置0

利用x & x-1的性质，把x左边第一个1置0，这样一直置0，直到right <= left就找到了公共前缀

int rangeBitwiseAnd(int left, int right) {
    while (left < right) {
        right = right & (right - 1);
    }
    return right;
}