【每日一题】7月31日题目精讲—兔子的区间密码
兔子的区间密码
https://ac.nowcoder.com/acm/problem/20860
https://ac.nowcoder.com/acm/problem/20860
思路：
要想让异或之后的结果最大，肯定从高位开始就要尽量大，也就是两个数的高位尽量不同。
如果lr的二进制位数不同，首先高位补0补齐，然后看我们能否在r的最高位取1的时候r的最高是不是不一样（如果一样，那么这一位只能取这个值，异或之后就消掉了），一直到第一个不一样的位置，肯定是r的这一位是1，l的这一位是0，之后小的那个数每一位显然可以任取了，所以后面全部都可以做到一个取1一个取0，于是找到l和r二进制不同的最高位从这位开始全部都是1就是答案。
如果lr的二进制位数不同，首先高位补0补齐，然后看我们能否在r的最高位取1的时候r的最高是不是不一样（如果一样，那么这一位只能取这个值，异或之后就消掉了），一直到第一个不一样的位置，肯定是r的这一位是1，l的这一位是0，之后小的那个数每一位显然可以任取了，所以后面全部都可以做到一个取1一个取0，于是找到l和r二进制不同的最高位从这位开始全部都是1就是答案。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
ll s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main(){
long long t;
cin>>t;
while(t--){
long long l,r;
cin>>l>>r;
if(l==r)
cout<<0<<endl;
else{
long long x=1ll<<62;
while((l&x)==(r&x)) {
x>>=1;
}
x<<=1;
cout<<x-1<<endl;
}
}
return 0;
} 位运算得补补了。掌握的不好
