题目
B君和G君聊天的时候想到了如下的问题。
给定自然数l和r ,选取2个整数\(x,y\)满足\(l <= x <= y <= r\),使得\(x|y\)最大。
其中\(|\)表示按位或，即\(C、 C++、 Java\)中的\(|\)运算。
输入格式
包含至多\(10001\)组测试数据。
第一行有一个正整数，表示数据的组数。
接下来每一行表示一组数据，包含两个整数\(l,r\)。
保证 \(0 <= l <= r <= 1018\)。
输出格式
对于每组数据输出一行，表示最大的位或。
输入样例
5
1 10
0 1
1023 1024
233 322
1000000000000000000 1000000000000000000
输出样例
15
1
2047
511
1000000000000000000
题解
输入两个数字\(l,r\)
二进制位低位对齐, 从高位向低位遍历.
- 如果两个数字第\(i\)位不相同, 那答案从这一位开始, 到最后都是\(1\), 然后停止遍历.
因为这步(不相同)会停止遍历, 所以前面每位都相同, 在保持前面不变的情况下, 可以直接忽略前面, 那么, 由于不相同, 必定有一个\(1\), 有一个\(0\).
因为前面都相等, 所以必定是大数这一位为\(1\), 那就是这样的情况:
1xxxxx (大数)
0xxxxx (小数)
如果最终做运算的一个数可以取大数到小数之间的任何数字, 自然也包括011111, 而011111|1xxxxx 答案自然是111111, 后面无需再计算.
- 如果两个数字的第\(i\)位相同, 答案这一位也相同.
由于遇到第一个不同的数字循环就会停止, 所以前面所有位都相同, 也就没有增减的余地, 这一位加1必定大于最大值, 减1必定小于最小值, 所以不变即可
代码
#include <cstdio>
int main() {
int t;
scanf("%d", &t);
while (t--) {
long long a, b, ans = 0;
scanf("%lld%lld", &a, &b);
for (long long i = 60; i >= 0; i--) {
if(!((1&(a>>i))^(1&(b>>i)))) ans^=(a&(1ll<<i));
else{
ans^=(1ll<<(i+1ll))-1ll;
break;
}
}
printf("%lld\n",ans);
}
return 0;
}