Leetcode868：二进制间距

朴素想法

遍历枚举每一位，使用变量pre记录上一位为1的位置。比较两个1之间的距离选出最大值即可。时间复杂度为O(logn)

class Solution:def binaryGap(self, n: int) -> int:pre=Noneans=0# 遍历位length=n.bit_length()for i in range(length):bit=(n>>i)&1# 判断if bit==1:if pre==None:pre=ielse:ans=max(ans,i-pre)pre=ireturn ans 

使用位运算技巧优化

可以使用位运算获取low_bit的技巧加速。首先去除后导0，使用x & -x得到除最低位1，其余位全置零的结果。比如100100操作之后为000100。这样使用bit_length()就能快速获取间隔距离。

class Solution:def binaryGap(self, n: int) -> int:ans=0# 先去除后导0以及第一个1，下面等价于 n //=(n & -n)*2n >>=(n & -n).bit_length()while n:# 寻找取出后的lowbit，即为1的最小位的长度。gap=(n&-n).bit_length()ans=max(ans,gap)n >>=gapreturn ans