& quot; Маленькая девочка и максимум XOR & quot;

Question

& quot; Маленькая девочка и максимум XOR & quot;

Как мне решить этот проблема на codeforces.

Второй подход (Non DP) в редакционный кажется проще, но я не могу понять, как это работает.

Может кто-нибудь подробно объяснить подход без дп?

Также я нашел эту реализацию кода, которую я не могу понять

#include <iostream>
#define ll long long
#define cnt_leading_zero_bits(x) __builtin_clzll(x);

using namespace std;

int main() {
ll l, r;
cin >> l >> r;
if (l == r) {
cout << "0\n";
return 0;
}
ll cnt = cnt_leading_zero_bits(l ^ r);
ll val = 64 - cnt;
cout<< ((1LL << val) - 1) << "\n";
return 0;
}

Кто-нибудь помогите.

-6

bit-manipulation c++xor

Решение

Другие решения

Источник

Accepted Answer

Если вы читаете о __builtin_clzll в http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html

— Встроенная функция: int __builtin_clzll (unsigned long long x)

Возвращает количество начальных 0-битов в x, начиная с самой старшей позиции бита. Если х равен 0, результат не определен.

От https://cs.stackexchange.com/a/29510,

Максимально возможное XOR любых двух целых чисел из интервала [l, r] можно определить из l ⊕ rпредполагая l, r быть целыми числами. Это значение равно pow(2, p) − 1, где p наименьшее значение, такое, что pow(2, p) больше чем l ⊕ r,

Теперь, касаясь кода,

val = 64 - __builtin_clzll(l ^ r);    // p

(1LL << val) - 1;    // pow(2, p) - 1

1