Максимально побитовое и всех возможных пар в данном диапазоне

Question

При заданном диапазоне [l,r] найти максимальный бит and из всех возможных пар

Какой подход мне выбрать, чтобы решить его эффективно?

Answer 1

Вот реализация javascript:

function maxAndInRange2(start, end) {
    if (end - start == 0) return 0;
    if (end - start == 1) return end & start;

    if (end % 2 == 0) return (end - 1) & (end - 2)
    return end & (end - 1)
}

Если end нечетный, тогда ответ должен быть end & (end-1), потому что end-1 будет иметь все те же двоичные цифры, кроме последнейодин, который будет превращен в 0. Таким образом, результатом этого будет конец - 1, очевидно, что никакая другая пара не может быть выше этой.

Если конец четный, то (конец - 1) нечетный.С той же логикой, (конец - 1) & (конец - 2) даст нам (конец - 2).Может ли быть пара выше, чем эта?Только end - 1 может быть выше, но end & (end - 1) не даст нам end - 1 в этом случае, поэтому (end - 2) - самый высокий результат