題目描述

給你兩個整數(shù) left 和 right ，表示區(qū)間 [left, right] ，返回此區(qū)間內(nèi)所有數(shù)字 按位與 的結(jié)果（包含 left 、right 端點）。

示例 1：
輸入：left = 5, right = 7
輸出：4

示例 2：
輸入：left = 0, right = 0
輸出：0

示例 3：
輸入：left = 1, right = 2147483647
輸出：0

思路分析

這道題是求left到right之間每一個數(shù)與操作的結(jié)果。

測試用例還挺良心的，給了個1-2147483647。告訴你暴力過不了哈哈。

這里可以回想一下二進制與操作，兩個數(shù)的‘’與‘’只要有0則為0。
而一個數(shù)不斷加1變成另一個數(shù)的過程中，實際上每一位都有變成0的情況。
這里舉個例子秒懂，

• 比如4->5 對應(yīng)二進制 101->110
• 9->10 對應(yīng)二進制 111->1000
• 100->101 對應(yīng)二進制 1100100 ->1100101

所以其實就是找兩個數(shù)的最長公共前綴。

這樣思路就簡單了，兩個數(shù)的二進制不斷往右移動，當(dāng)兩者相等的時候，停止移動。
記t為移動的次數(shù)，t就是兩個數(shù)的二進制不同的位數(shù)。此時再左移t位就可以啦。

完整代碼

class Solution:def rangeBitwiseAnd(self, left: int, right: int) -> int:res = 0while left<right:left = left>>1right = right>>1res +=1return left<<res```