Нахождение подмаски маски в заданном диапазоне

Question

Как найти наибольшую субмаску данной маски, которая равна или меньше заданного значения r. Например, подмаски маски (5 в двоичном 101) равны 4 (100 в двоичном), 1 (001 в двоичном). Теперь, если задано r = 5, тогда ответ будет 5, если r = 3, тогда ответ будет 1 et c. Я хочу эффективный алгоритм, который может вычислить его за меньшее время.

Но это код, дающий мне ограничение по времени, превышен. поскольку значение маски может быть <= 10 ^ 9. Будет очень полезно, если кто-нибудь даст мне оптимизированный подход, чтобы уменьшить сложность времени. </p>

то, что я пытался:

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

Answer 1

Кажется, это работает довольно быстро (не более 32 итераций для 10 ^ 9 чисел, в основном сложность 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
>>>