在给定范围内寻找掩码的子掩码。

Question

如何找到一个给定掩码的最大的子掩码，这只是等于或小于给定的值r.For example the sub masks of a mask(5 in binary 101) is 4(100 in binary),1(001 in binary).Now if given r=5,then answer would be 5,if r =3,then answer would be 1 etc.I want efficient algorithm which can calculate it in less time. 现在如果给定r=5，那么答案将是5，如果r=3，那么答案将是1等等。

但是这段代码给我的时间限制超过了.因为掩码的值可以是<=10^9这将是非常有用的，如果有人给我优化的方法，以减少时间的复杂性。

我在尝试什么。

for(int i=mask;i>0;i=(i-1)&mask)
     if(i<=r)
       print(i);

Answer 1

这似乎工作得相当快（对于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
>>>