LeetCode - 解题笔记 -201- Bitwise AND of Numbers Range

Solution 1

整体的规律实际上就是找所有数字（实际上就是range左右端点）的公共前缀。因为只要给定数字是连续的，那么一定存在两个相邻数字，在公共前缀的后一位，小的是0111……，大的是1000……，因此最后按位与的结果就是这些数字的公共前缀后面补零。

针对给定的两个数，不断右移，直到二者的结果一样，对应的就是公公前缀。最后的结果就是想对应的部分作为前缀补零左移即可。

• 时间复杂度：$O(\log N)$，其中$N$为输入两个数的较小的位长度。按位操作。
• 空间复杂度： $O(1)$，仅维护常数个状态量。

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int num_shift = 0;
        
        while (left < right) {
            left >>= 1;
            right >>= 1;
            
            num_shift++;
        }
        
        int ans = right << num_shift;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Solution 2

根据题解数字范围按位与 - 数字范围按位与 - 力扣（LeetCode）的Brian Kernighan算法，用于高效处理位表示最右边的1。

和 0191. Number of 1 Bits 的思路是一样的，去掉右侧1的目的不同。

其实和上面位移的思路是一样的，只是换了一种方法：不断地对n与n-1进行与运算，直到变成m或者比m小，此时n保留的就是公共后缀。

• 时间复杂度：$O(\log N)$，其中$N$为输入两个数的较小的位长度。按位操作。
• 空间复杂度： $O(1)$，仅维护常数个状态量。

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        while (left < right) {
            right &= (right - 1);
        }
        
        int ans = right;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11

Solution 3

Solution 1的Python实现

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        num_shift = 0
        
        while left < right:
            left >>= 1
            right >>= 1
            
            num_shift += 1
            
        ans = right << num_shift
        return ans
1
2
3
4
5
6
7
8
9
10
11
12

Solution 4

Solution 2的Python实现

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while left < right:
            right &= (right - 1)
            
        ans = right;
        return ans
1
2
3
4
5
6
7