在给定范围内查找掩码的子掩码
在给定范围内查找掩码的子掩码
提问于 2020-05-04 14:54:56
如何找到给定掩码的最大子掩码，该掩码恰好等于或小于给定值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);
回答 1
Stack Overflow用户
发布于 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
>>> 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61595166
复制相关文章
相似问题
存储相关数据以进行搜索的最佳方法
存储大量用户统计信息的最佳方法是什么？
在表中存储可选值的最佳方法是什么？
存储大量用户加密数据的最佳方法是什么？
最佳实践Server维护计划是什么样子的？
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
