兔子的区间密码

兔子的区间密码

https://ac.nowcoder.com/acm/problem/20860

题意：给你L，R<=1e18,问你这个区间里面任意两个数xor最大值是多少？
思路：看完样例就发现ans=(1<<k)-1😂,然而我们怎么找呢?
异或值最大肯定是最高位1尽可能高。
假设L=11010010，R=111000000；那么这个区间里面都是11.......
所以前两个（相同1的情况）不看，然后第三位R=1，L=0，代表这一位异或值必定是1，那么必定存在10000000<=R,01111111<=R,那么我们就构造出来了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e15+7;
const int N=2e5+5;
const int M=1e6+5;
int T,bitl[N],bitr[N];
ll L,R;
int cal(ll x) {
    int cnt=0;
    while(x) {
        x>>=1;
        cnt++;
    }
    return cnt;
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%lld%lld",&L,&R);
        int l=cal(L),r=cal(R);
        if(L==R) {
            printf("0\n");
            continue;
        }
        for(int i=1; i<=r; i++) {
            bitr[i]=R%2;
            R>>=1;
        }
        for(int i=1; i<=r; i++) {
            bitl[i]=L%2;
            L>>=1;
        }
        int pos;
        for(int i=r; i>=1; i--) {
            if(bitr[i]==1&&bitl[i]==0) {
                pos=i;
                break;
            }
        }
        ll ans=(1ll<<pos)-1;
        printf("%lld\n",ans);
    }
}