题解：SP25844 MAXXOR - Find the max XOR value

我们先考虑如果两个数的二进制位数不同的情况，显然这种情况下，我们可以取与

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}

这个词语，应该不难理解。）

那么简单了，上代码。

CPP

#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;
}

题解：SP25844 MAXXOR - Find the max XOR value

文章操作

相关推荐

评论

题解：SP25844 MAXXOR - Find the max XOR value