题目

题目描述：
有一只可爱的兔子被困在了密室了，密室里有两个数字，还有一行字：
只有解开密码，才能够出去。
可爱的兔子摸索了好久，发现密室里的两个数字是表示的是一个区间[L,R]
而密码是这个区间中任意选择两个(可以相同的)整数后异或的最大值。
比如给了区间[2,5] 那么就有2 3 4 5这些数，其中 2 xor 5=7最大 所以密码就是7。
兔子立马解开了密室的门，发现门外还是一个门，而且数字越来越大，兔子没有办法了，所以来求助你。
提示：异或指在二进制下一位位比较，相同则 0 不同则 1
例如2=(010)2，5=(101)2所以2 xor 5=(111)2=7

输入描述：
第一行一个数 T，表示数据组数。
接下来 T 行，每行两个数 L，R, 表示区间[L,R]。

输出描述：
输出共T行每行一个整数，表示[L,R]的密码。

解析

1）知识点

  • 这道题其实不难，只是要对这个区间有一个理解。这是一个简单的位运算。要注意的就是二进制位怎么比较与存取。

2）看题目

  • 这道题目的意思就是说，求在一个区间里面取任意两个数的最大异或值。

3）算法分析

  1. 首先我们明确一个观点，越高的数位不同，得到的数字也就越大（就是异或的特性，不同则留下，相同则归零）。
  2. 这个时候我们就可以注意到，区间的两头分别是最大值和最小值，也就是说判断两端的情况就知道最高位是否相同了。
  3. 所以我们这个时候就可以分成两种情况来讨论：
    1. 最高位（指二进制1所在的最高位置）是相同的：这个时候最高位就不重要了，因为不管取哪两个，结果都会把最高位的1抵消了。所以这个时候直接把最高位删除。
    2. 那如果最高位是不同的：这个时候就说明 l < 2i 而且 r > 2i ，这个时候最大的异或值就是2i ^ 2i - 1 = 2i+1 - 1（为什么？因为10……0和01……1异或时全都不一样，肯定最大呀）。
  4. 这就是结果了。

4）算法操作

  1. 这里我们注意一下特殊情况，左右相等直接为0： 
    if (l == r) {
        cout << 0 << endl;
    continue;
}
  2. 还有左右不等的判断方法就好了，没有必要求出最高位什么的，直接从二进制上限遍历下来就好了： 
    for (int i = 59; i >= 0; i--) {
        if ((l & (1ll << i)) != (r & (1ll << i))) {
                cout << (2ll << i) - 1ll << endl;
        break;
    }
    if (l & (1ll << i)) {
            l ^= 1ll << i;
        r ^= 1ll << i;
    }
}

5）打代码

  1. 打代码！
  2. 还是先输入。
  3. 然后进行循环进行遍历情况。
  4. 看我代码咯~

AC代码 

#include <iostream>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

ll l, r, ans;//区间左右边界和答案
//全局变量区

int main() {
    IOS;
    int T; cin >> T;
    while (T--) {
        cin >> l >> r;
        if (l == r) {
            cout << 0 << endl;
            continue;
        }
        for (int i = 59; i >= 0; i--) {
            if ((l & (1ll << i)) != (r & (1ll << i))) {
                cout << (2ll << i) - 1ll << endl;
                break;
            }
            if (l & (1ll << i)) {
                l ^= 1ll << i;
                r ^= 1ll << i;
            }
        }
    }
    return 0;
}
//函数区