python算法:rangeBitwiseAnd(连续整数的与)

时间:2023-03-08 23:33:30
python算法:rangeBitwiseAnd(连续整数的与)

def rangeBitwiseAnd(self, m, n):

i = 0

while m != n:

m >>= 1

n >>= 1

i += 1

return n << i

------

testcase:

【4,7】

4:0x0100

5:0x0101

6:0x0110

7:0x0111

可以用一个 while 循环来做,但是效率太低,有个非常牛逼的算法,从leetcode上学来的,解释下:

假设头尾的两个数字分别是 m=0bxyz0×××,n=0bxyz1xxx,

其中,也就是说把一个数字做了分解,第一部分是高位两个数字共同的部分,另一部分是低位两个数字差异的部分:

此时,结果值,分成两部分:高位是两个数字高位公共的部分,低位是全0.

好了,为什么是这样?因为这两个值的低位两个数字差异的部分必然能找到0!

这个点算是一个转折点了,也迎来本算法的高潮。也就是说 连续的整数中,低位不同的部分每一个位必然存在0于其间的某个整数中

0x01111111

0x10000000

这个结论不好直接想,但是可以用反证的思维想下,如果找不到这样一个0,那么说明这个连续整数数列是这样的:

0bxyz***1***

0bxyx***1***

0bxyz***1***

0bxyz***1***

obxyz***1***

那一串1,就像是一堵墙一样堵住了连续整数的进位,这样也就限制了连续整数的个数。

当1串位于第0位时,连续整数个数最多为1

当1串位于第1位时,连续整数个数最多为2

当1串位于第2位时,连续整数个数最多为4