※ 引述《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没看过这种用法就想不太到

留言区蛮多提示的 然后直接写解答的我都恨恨的给他倒赞

大师