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

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