题解：SP25844 MAXXOR - Find the max XOR value

yanxu_cn · 2025-09-03 16:43:10 · 题解

我们先考虑如果两个数的二进制位数不同的情况，显然这种情况下，我们可以取与 R 二进制位数相同的最小值 K 然后取 K\oplus(K-1) 即为答案，这个非常容易理解吧。

那么如果位数相同，我们可以不断分别去掉 L 和 R 的前导 1（因为这些统一的 1 其实与统一的 0 就没什么区别），直到有一位不同，然后可以参考上面的方法处理。

所以我们发现，实际上只要先取 t=L\oplus R，然后求 2^{\operatorname{highbit}(t)+1}-1 即可。我们注意到 GNU C++ 提供了一个叫做 __builtin_clz 的函数可以计算前导零的数目并且速度非常快（这是对于洛谷评测机来说的，因为可以通过 LZCNT 指令计算，但是部分 OJ 比如 BZOJ 显然不支持，所以只能回退到 BSR 指令实现）。（造了一个 \operatorname{highbit} 这个词语，应该不难理解。）

那么简单了，上代码。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    unsigned long long L, R;
    cin >> L >> R;
    unsigned long long xor_val = L ^ R;
    if (xor_val == 0) {
        cout << "0\n";
        return 0;
    }
    int bit_length = 64 - __builtin_clzll(xor_val);
    unsigned long long result = (1ULL << bit_length) - 1;
    cout << result << '\n';
    return 0;
}