标签: 位运算
难度: Medium
给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。
示例 1：
输入：left = 5, right = 7 输出：4
示例 2：
输入：left = 0, right = 0 输出：0
示例 3：
输入：left = 1, right = 2147483647 输出：0
提示：
0 <= left <= right <= 231 - 1运行时间: 25 ms
内存: 16.2 MB
class Solution:
def rangeBitwiseAnd(self, m: int, n: int) -> int:
shift = 0
# 找到公共前缀
while m < n:
m = m >> 1
n = n >> 1
shift += 1
return m << shift
题解的思路是利用位运算的特点，找到区间 [m, n] 中所有数字的二进制表示的公共前缀。因为按位与运算的结果只保留了公共前缀部分，所以最终结果就是将公共前缀再向左移动 shift 位得到的数字。具体做法是，不断将 m 和 n 同时右移，直到 m 和 n 相等，同时记录右移的次数 shift。最后将 m 左移 shift 位即可得到答案。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def rangeBitwiseAnd(self, m: int, n: int) -> int:
shift = 0
# 找到公共前缀
while m < n:
m = m >> 1 # 将 m 右移一位
n = n >> 1 # 将 n 右移一位
shift += 1 # 记录右移的次数
return m << shift # 将 m 左移 shift 位作为最终结果
在题解中，'公共前缀'指的是数字范围内所有数字二进制表示中相同的最高位序列。例如，对于数字12和15，它们的二进制分别是1100和1111。我们可以观察到，从高位到低位的前两位11是共同的，这部分就是公共前缀。题解的算法通过不断右移m和n，实际上是在逐步剥离这两个数的低位部分，直到它们相等，这时候剩下的部分就是它们的公共前缀，这也是所有数字的公共前缀。
当m小于n时，进行右移操作是为了简化问题。右移操作相当于除以2，这可以快速减少问题的规模，同时保留了m和n的高位部分。这样做的目的是找到m和n的公共前缀。右移直到m等于n意味着我们已经找到了所有数字的公共前缀。右移操作使得我们能够忽略那些不会影响最终按位与结果的低位，因为这些低位在范围内的某些数中会变成0，从而在最终的按位与操作中变为0。
shift变量记录了m和n共同右移的次数，它代表了我们忽略的低位数的数量。当m和n完全相等时，它们的不同之处已经通过右移操作被丢弃，剩下的是它们的公共前缀。此时的shift就是我们为了找到这个公共前缀而执行的右移操作次数。通过将m（此时m和n相等，代表了公共前缀）左移shift位，我们实际上是在将这个公共前缀放回它原来的位置，补回我们之前通过右移丢弃的位数，从而得到正确的范围按位与结果。
在这种极端情况下，本方法的效率非常高。考虑到left和right的范围非常广，如果使用暴力方法逐个计算每个数字的按位与，将非常耗时，因为需要进行大约21亿次按位与操作。而通过不断右移直到m和n相等的方法，最多只需要进行32次迭代（因为2147483647的二进制表示最多有32位）。这大大减少了操作的次数，提高了效率。因此，即使在极端情况下，这种方法也比暴力方法具有明显的优势。