Максимальное значение xor b для всех пар целых чисел a, b (l ≤ a ≤ b ≤ r)

Question

Проблема заключается в том, чтобы найти максимум xor b для всех пар целых чисел пары целых чисел a, b (l ≤ a ≤ b ≤ r). Если l и R равны 8 и 16, ответ будет 31, который на самом деле 15 xor 16.I наткнулся на этот кусок кода, и он дает правильный результат, но логическая часть не ясна.

int main() { 
    cin >> A >> B; 
    ll num = 1; 
    while (A/num != B/num) { 
     num *= 2; 
    } 
    cout << num - 1 << "\n"; 
    return 0; 
}           

Answer 1

Ну, я могу легко свернуть этот код. Введя один и тот же номер дважды. Если l = r, то алгоритм сработает, но наибольшее значение для xor b, очевидно, 0, так как l = a = b = r.

Предположим l < r и что для некоторого n имеем (l/(2^n)) = (r/(2^n)). Существует такое n, потому что мы можем просто выбрать n, делая 2^n> r. И n> 0, потому что l < r. Выберите наименьший такой n.

В этом случае a/(2^n) имеет то же значение для всех a, l ≤ a ≤ r. Это означает, что все биты в a^b, начинающиеся с бит n, равны нулю. Поэтому a xor b < 2^n, и мы можем заменить l, r на l по модулю (2^n), r по модулю (2^n).

С другой стороны, n было выбрано как можно меньше. Поэтому бит n-1 устанавливается в r, а бит n-1 очищается в l. Поэтому l < 2^(n-1), r ≥ 2^(n-1). Мы можем выбрать a = 2^(n-1) - 1, b = 2^(n-1). Тогда l ≤ a ≤ b ≤ r и a xor b = 2^n - 1. Так как мы показали, что xor b всегда меньше 2^n, но может быть 2^n - 1, то 2^n - 1 - наибольшее значение.

Именно то, что алгоритм вычисляет, за исключением того, что l = r обрабатывается неправильно.

Answer 2

Возьмем в качестве примера с L = 8 и R = 16, или

l = 00010 
r = 00001 

, что делает этот код, смещается биты, пока числа не являются одинаковыми:

num=2 num=4 num=8 num=16 num=32 

00100 01000 10000 00000 00000 
00010 00100 01000 10000 00000 -> done : max xor is 32-1 

это работает , потому что самый большой xor, который вы можете получить, - это число с таким количеством бит, которое установлено на 1, насколько это возможно, и в целом, если у вас есть

l = 0001010101010101011111111111110000001010101010... 
r = 0010101010101010101101010101010100001010101010... 
            ^...starting from here they are 
             the same (no matter what) 

самый большой результат, который вы можете получить из в исключающего б с л < < б < г

111111111111111111111111111111110000000000000000000...