AT2382

题目传送门

考试总是考原题，以后还是要将刷题量提上去。

观察题目，分类讨论两个异或数的定义域。

1.我们先找出二进制下$A$和$B$最高的的不同位（最低位放右边，位数不同就补零）时（设其为$id$），因为$[A，2^{id} - 1)$之间进行$or$运算一定不会进位，也不会变小，所以$2^{id} - 1 - ((l >> id) << id) + 1$这些数都可以取（值域还是$[A,2^{id} - 1)$），因为$B$和$A$在$id$左边的位都相同，所以$((B >> id) << id) - l == (1 << id) - ((l >> id) << id)$，故第一部分的答案为：

z = (B >> id) << id;
ans += z - l; // (z - 1) - (l - 1)

2.再考虑最高位左边的相同位，$[2^{id},B]$ 间内的数相互运算 , 我们找出$B$中最高不同位以下的最高的一（设位数为$k$) ， 即$AxorB$的倒数第二个$1$，则设数$P$等于将$B$中$k$位以后的所有位改为$1$的值。

同理也可以证明，其值域也就为：$[2^{id}, P]$。

3.两个区间内的数相互异或，同理。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL x, y, z, k, maxn;
int T, id, i;
LL ans;
int main()
{
    scanf("%lld%lld", &x, &y);
    if(x == y) 
    {
        puts("1");
        return 0;
    }
    z = x ^ y;
    while(z)
    {
        id ++;
        z >>= 1;
    }
    id --;
    z = (y >> id) << id;
    k = z ^ y;
    ans = z - x;
    while(k)
    {
        i ++;
        k >>= 1;
    }
    i --;
    maxn = y | ((1ll << (i + 1)) - 1);
    LL l = x | z, r = z | (z - 1);
    if(maxn < l) ans += maxn - z + 1 + r - l + 1;
    else ans += r - z + 1;
    cout << ans << endl;
    return 0;
}