Непосредственно (НЕ итеративна) максимизация (1 << п) при условии (а & ~ ((1 << n) - 1)) > = Ь

Question

Я пытаюсь найти самый большой 1 << n, что удовлетворяет это неравенство (все переменные являются положительными целыми числами):

a & ~((1 << n) - 1) >= b 

Решая это итеративно тривиально (и да, я знаю, что вы можете получить более высокую производительность за счет разделяй и властвуй и тому подобное), но это не мой вопрос.

мне интересно, если есть Кстати, это можно было бы решить напрямую, как через бит-скручивание?

Примечание 1: Предположим, что вы можете выполнить «округление вверх/вниз до ближайшей мощности 2» за одну операцию.
Примечание 2: При необходимости вы можете предположить представление представления двух (но я сомневаюсь, что это помогает).

Какую технику я могу использовать для решения этой проблемы, если есть прямой способ? Если нет, могу ли я как-нибудь сказать?

Я пробовал много вещей, таких как XORing a и b, округляя результат до следующей мощности 2 и т. Д., Но я не нашел ничего хорошего, что всегда срабатывает.

Answer 1

if (a < b) { 
    oops(); 
} else if (a == b) { 
    return ctz(a); 
} else { 
    // most significant mismatching bit - must be set to 1 in a and 0 in b 
    int msmb = round_down_to_power_of_2(a^b); 
    if (b & (msmb - 1)) { 
     return ctz(msmb); 
    } else { 
     return ctz(b); 
    } 
} 

У нас есть 4 случая:

1. Если в < б, ни одно значение п работ.
2. Если a == b, мы можем очистить каждый бит до наименее значимого бита набора.
3. Если a> b и b установили биты ниже наиболее значимого несоответствующего бита между a и b, мы можем очистить каждый бит до самого значительного несоответствующего бита.
4. Если a> b и b не имеют установленных битов ниже наиболее значимого несоответствующего бита между a и b, мы можем очистить каждый бит до младшего значащего бита b.