题目链接：牛客网 NC20860

题意

给定一个非负整数区间 [L, R]，从中任选两个整数 a、b（可以相同），求 a ^ b 的最大值。

其中 ^ 表示按位异或：两个二进制位相同，结果为 0；不同，结果为 1。

例如区间 [2, 5] 中，可以选择 2 和 5：

2 = 010
5 = 101
-------
^ = 111 = 7

一、原来的方法为什么不对？

原来的代码分别寻找 L 和 R 各自最高的 1，然后根据这两个位置构造答案。

当两个位置相同时，不能直接把最高位以下的所有位都设成 1，因为它们可能还有更多相同的高位。

例如 [12, 13]：

12 = 1100
13 = 1101

两数最高的 1 都在第 3 位（从第 0 位开始计数）。如果把低三位全部设成 1，会得到 7。

但区间中只有 12 和 13，它们异或的最大值为：

12 ^ 13 = 0001 = 1

所以，需要找的是 L 和 R 的最高不同位。

二、如何找到最高不同位？

计算：

x = L ^ R;

x 中为 1 的位置，就是 L 和 R 不同的位置。因此，x 的最高有效位就是我们要找的最高不同位。

例如 [10, 12]：

10 = 1010
12 = 1100
---------
^  = 0110

最高不同位是第 2 位。

结论：如果最高不同位是第 k 位，那么答案为低 k + 1 位全为 1 的数：

答案 = 2^(k + 1) - 1

这里的 ^ 在数学表达式中表示乘方；在 C++ 代码中，^ 表示异或，不能用它计算乘方。

当 L == R 时，只能选择同一个数，答案为 0。

三、为什么这个结论一定正确？

证明分成两部分：先证明结果不可能更大，再证明一定能选到两个数达到这个结果。

1. 结果不可能更大

设 L < R，最高不同位为第 k 位，第 k 位以上的公共二进制前缀记作 P。

因为 L < R，在最高不同位上，L 必须为 0，R 必须为 1：

L = P 0 ……
R = P 1 ……

具有前缀 P 的所有数构成一个连续区间。L 和 R 都位于这个区间，因此夹在它们之间的数也都具有相同的前缀 P。

所以，从 [L, R] 中任意选择两个数，其第 k 位以上的部分异或后必然全部为 0。只有第 k 位及以下可能为 1。

于是，异或值最多为：

高位全为 0，低 k + 1 位全为 1
即 2^(k + 1) - 1

2. 一定能达到这个值

考虑下面两个相邻的整数，其中第 k 位后面各有 k 位：

A = P 0 111…111
B = P 1 000…000

A 是前缀为 P 0 的最大数，而 L 的前缀正是 P 0，所以 L <= A。

B 是前缀为 P 1 的最小数，而 R 的前缀正是 P 1，所以 B <= R。

同时，A + 1 = B，于是：

L <= A < B <= R

这说明 A 和 B 必然都在题目给定的区间内。

它们异或时，公共前缀变成 0，第 k 位和所有更低位全部变成 1：

A = P 0 111…111
B = P 1 000…000
----------------
^ = 0 1 111…111

因此，确实可以达到 2^(k + 1) - 1。结合前面证明的上界，这就是最大值。

例如 [10, 12] 的这两个分界数是 11 和 12：

L = 10 = 1010
A = 11 = 1011
B = 12 = 1100
R = 12 = 1100

11 ^ 12 = 0111 = 7

注意：L ^ R 用来确定最高不同位，它本身不一定就是答案。这里 10 ^ 12 = 6，但最大值为 7。

四、代码如何构造答案？

先令 x = L ^ R，然后每次把 x 右移一位，直到变成 0。循环次数就是 x 的二进制位数。

每次循环同时给 ans 的二进制末尾添加一个 1：

ans = (ans << 1) | 1;

• ans << 1：左移一位，相当于在末尾添加一个 0。
• | 1：把末尾这一位设成 1。

例如 x = 6，二进制为 110：

最终得到 111，即十进制的 7。

如果 L == R，那么 x == 0，循环不会执行，ans 自然保持为 0。

五、完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        unsigned long long l, r;
        cin >> l >> r;

        unsigned long long x = l ^ r;
        unsigned long long ans = 0;

        while (x != 0) {
            ans = (ans << 1) | 1ULL;
            x >>= 1;
        }

        cout << ans << '\n';
    }

    return 0;
}

这里使用 unsigned long long 保存非负整数，避免大数超出普通 int 的范围。循环逐位构造答案，也不需要直接计算可能发生边界溢出的 1 << (k + 1)。

六、复杂度分析

设整数类型的位数为 W。

• 每组时间复杂度：O(W)。在 64 位无符号整数范围内，循环最多执行 64 次。
• 额外空间复杂度：O(1)。

七、自测样例

输入：

5
2 3
2 5
10 12
12 13
8 8

输出：

1
7
7
1
0

对应的取数方式分别可以是 (2, 3)、(2, 5)、(11, 12)、(12, 13) 和 (8, 8)。