※ 引述《SecondRun (南爹摳打)》之銘言：
: 201. Bitwise AND of Numbers Range
: 給你left跟right兩個整數
: 回傳left AND left+1 AND left+2 AND ... AND right
解1 TLE
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
res = left
for i in range(left, right + 1):
res &= i
return res
解2 WA
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
res = left
for i in range(left, right + 1):
res &= i
if res == 0:
break
return res
https://i.imgur.com/8ZXLj1O.jpg
只好看答案。
思路：
1.因為 left <= right所以 left 轉成二進制只有兩種可能：
right的位數比left多，例如： 1000 比 10
right的位數和left一樣多，例如：1001 比 1000
2.參考下圖，如果right的位數比left多
l: 1xxx
r:1xxxxxxx
因為l會不斷遞增直到等於r，所以最後一定會碰到除了最高位元以外全為0的狀況
l:10000000
r:1xxxxxxx
10000000（做and一定會變最高位元以外全0）
又因為l位數小於r，所以把上面的結果和l做AND：
10000000
l:00001xxx
我們可以得到如果right的位數比left多，那麼必定AND起來為0。
3.參考下圖，如果right的位數和left一樣多
l:1xxxxxxxx
r:1xxxxxxxx
很明顯的，左半邊的and結果就是l和r全為1的部份（因為前面2提到的補0特性），所以
我們只要找出左半邊有幾個連續的1，再把右半邊補0，就是全部AND在一起的結果了，
AKA從右邊開始找幾個位元範圍的0和1不同，然後把左半邊相同的位數右邊全補0。
pycode：
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
shift = 0
while left < right:
left = left >> 1
right = right >> 1
shift += 1
return left << shift
恨bitwise

這題蠻微妙的 我一開始一直在想差多少的話要把那些數字弄成0然後看了提示就直接懂了

這題沒提示我只好抄答案bitwise沒看過這種用法就想不太到

留言區蠻多提示的 然後直接寫解答的我都恨恨的給他倒讚

大師