链接
最大的位或
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3589 Accepted Submission(s): 1369
Problem Description
B君和G君聊天的时候想到了如下的问题。
给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。
其中|表示按位或，即C、 C++、 Java中的|运算。
Input
包含至多10001组测试数据。
第一行有一个正整数，表示数据的组数。
接下来每一行表示一组数据，包含两个整数l,r。
保证 0 <= l <= r <= 1018。
Output
对于每组数据输出一行，表示最大的位或。
Sample Input
5
1 10
0 1
1023 1024
233 322
1000000000000000000 1000000000000000000
Sample Output
15
1
2047
511
1000000000000000000
Source
2016年中国大学生程序设计竞赛（合肥）-重现赛（感谢安徽大学）
【分析】
我们想要得到的位或最大，那么进行位或的一个数一定是最右边的数，因为它的二进制位最多
假设区间为5-10
那我们观察5的二进制有效位是3，10的二进制有效位是4
像这样区间的端点的有效位不相同，那么从有效位少的左端点3位增加到4位的过程中一定会出现一个3位都是1的数字，对应于我举得例子就是7，7的二进制为111，那么111和1010或运算得到1111，即15.这就是或运算最大的值。
如果区间俩个端点有效位相同
假设区间为8-10
8的二进制是1000
10的二进制是1010.我们这样想因为他们分别是左右端点，那么从左端点增加至右端点一定不会超过右端点。且因为二进制增加是从末尾增加，那么从8增加到10，一定不会出现1011，因为1011已经大于10，不属于区间了
那我们从前往后找，找到8和10的二进制的第一个不同位是第三位。那我们来看10的第三位往后是10，8的第三位往后是00，那么从00增加到10，是不是一定会出现01，也就是小于10的有效位一位的全为1的数字。
那么1010和1001或运算为1011，即11
再举一个例子：
假设区间是16-22
他们的二进制分别为10000，10110，
首先他们有效位相同，那么从左往右找到第三位开始不同，把前面的忽略，为什么忽略？因为左边的高位即使有0，但是在左端点增加至右端点过程，也不会出现那个位是1得数，因为那个位是1的数肯定大于右端点。忽略前面的位，他们二进制分别是000，110，那么从000增加至110，一定会出现011，对吧。
那么最大位或就是10011和10110的或运算结果
【代码】
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1005;
ll l,r,ans;
ll a[N],b[N];
int main()
{
int t;
cin>>t;
while(t--)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cin>>l>>r;
//十进制转换为二进制
ll n=l,m=r;
int cl=0,cr=0;
while(n)
{
a[cl++]=n%2;
n/=2;
}
while(m)
{
b[cr++]=m%2;
m/=2;
}
ans=0;
for(int i=cr-1;i>=0;i--)
{
if(a[i]==b[i])
{
if(b[i])
{
ans+=(ll)pow(2,i);
}
}
else
{
ans+=(ll)pow(2,i+1)-1;break;
}
}
cout<<ans<<endl;
}
return 0;
}
10000
10110
---
10000
+ 111
因为中间一定遇到001
而R必须选
那么001|110——>111