MAXXOR - Find the max XOR value 题解
August_Light
·
·
题解
MAXXOR - Find the max XOR value 题解
题目传送门
题意简述
给定 l,r，在 [l,r] 中取出两数 a,b（可相同），使 a \oplus b 最大。输出 a \oplus b。（\oplus 为按位异或运算）
## 解法
这种题当然上来先打表啦。
首先我猜答案和不超过 $r$ 的最大的 $2$ 的幂（记为 $b$）有关。
显然 $l < b$ 时，答案为 $b \oplus (b - 1)$。
注意到表中有相似部分：
（第一列为 $l$，第二列为 $r$，第三列为答案。）
```
8 8 0
8 9 1
8 10 3
8 11 3
8 12 7
8 13 7
8 14 7
8 15 7
...
```
```
16 16 0
16 17 1
16 18 3
16 19 3
16 20 7
16 21 7
16 22 7
16 23 7
...
```
发现答案这一列一模一样啊，$l$ 和 $r$ 正好差一个 $b$。然后就有了下面的代码，它过了。
时间复杂度 $O(\log n)$。
### 证明
显然根据代码最终的 $b$ 是 $l \oplus r$ 的 highbit。
显然此题有 $O(1)$ 解法。懒得写了。
## 代码
highbit 注意用 `log2l` 而非 `log2`。会被卡。
```cpp
uLL find_max_xor(uLL l, uLL r) {
while (r) {
uLL b = (1ull << uint(log2l(r)));
if (l < b)
return b^(b-1);
l -= b; r -= b;
}
return 0;
}
```
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef unsigned long long uLL;
uLL find_max_xor(uLL l, uLL r);
int main() {
uLL l, r; scanf("%llu %llu", &l, &r);
printf("%llu", find_max_xor(l, r));
return 0;
}
```
## 双倍经验
[Little Girl and Maximum XOR](https://www.luogu.com.cn/problem/CF276D)