每日一题 兔子的区间密码 (思维/位运算)

一.题意

给你一个区间
求两个数异或最大

二.题解

由于数据很大，所以不能暴力找
而题目说到异或最大，其实就是让我们往位运算方面/二进制方面去想
让这个数最大，就是尽量让高位为 1
比如[111101,110011]这种情况
可以发现最高两位的 1 两者都会异或抵消，所以最大的贡献位在第三位
从第三位开始可以找到1101和0010凑成1111就是使得答案最大
所以其实就是找最高的贡献位
其余的低位部分都在范围里可以操控使得全1
所以答案就是 最高位*2-1

三.代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define eps 1e-10
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
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;
}

const int manx=1e3+5;
const int N=5e2+5;
const int mod=1e9+7;

int main(){
    io; ll n; cin>>n;
    while(n--){
        ll l,r; cin>>l>>r; 
        if(l==r){ cout<<0<<endl; continue;}
        ll x=1ll<<62;
        while((l&x)==(r&x)) x>>=1;
        x<<=1;
        cout<<x-1<<endl;
    }
}