如何找到给定掩码的最大子掩码,该掩码恰好等于或小于给定值r。例如,掩码(二进制101中的5个)的子掩码是4(二进制为100),1(二进制为001)。现在如果给定r=5,那么答案将是5,如果r =3,那么答案将是1,依此类推。我想要一个有效的算法,可以在较短的时间内计算它。
但是这段代码给我的时间限制超过了.as,掩码的值可以是<=10^9,如果有人给我优化的方法来降低时间复杂度,这将是非常有帮助的。
我尝试的是:
for(int i=mask;i>0;i=(i-1)&mask) if(i<=r) print(i);
发布于 2020-05-04 15:18:20
这似乎非常快(对于10^9个数字,迭代不超过32次,基本上是O(logN)复杂度):
>>> def submask( mask, r ) :
... result = 0
... for bit in range(32,-1,-1) :
... value = 1 << bit
... if value & mask == 0 : continue
... if value | result <= r :
... result |= value
... return result
...
>>> submask(5,1)
1
>>> submask(5,3)
1
>>> submask(5,4)
4
>>> submask(5,5)
5
>>> submask(7,2)
2
>>>
https://stackoverflow.com/questions/61595166
复制相似问题