"Little girl and maximum XOR"

Question

我如何解决 codeforces 上的 this 问题。

Editorial 中的第二种方法（非 DP）似乎更简单，但我无法理解它是如何工作的。

有人可以详细解释一下非 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;
}

有人帮忙。

Answer 1

如果您在 http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html

中阅读了有关 __builtin_clzll 的内容

— Built-in Function: int __builtin_clzll (unsigned long long x)

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

来自 https://cs.stackexchange.com/a/29510、

The maximum possible XOR of any two integers from an interval [l, r] can be determined from l ⊕ r, assuming l, r to be integers. This value is equal to pow(2, p) − 1, where p is the smallest value such that pow(2, p) is larger than l ⊕ r.

现在，与代码相关，

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

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

"Little girl and maximum XOR"

"Little girl and maximum XOR"

c++

bit-manipulation

xor