给你两个整数$n,m$,求出$n\oplus0,n\oplus1,…,n\oplus m$这个序列的$MEX$值
数据范围
$t$组数据,$0\le n,m \le 30000$
$0\le n,m \le 10^9$
分析:
$n \oplus m = k$,其中$m \in [0,m]$
根据性质$a \oplus b = k$等价于$a \oplus k = b$,可以推出$n \oplus k = m$,其中$m \in [0,m]$
也就是找到最小的数$k$,使得$n\oplus k \ge m+1 $
设$p=m+1$
从高到低按位枚举$n$和$p$的每一位
- 如果$n_i=p_i$,$k_i$填0
- 如果$n_i=1,p_i=0$,那么$k$这一位填1,后面全填0即可。
- 如果$n_i=0,p_i=1$,$k_i$一定为1
根据以上方法,就可以构造出最小的$k$
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n, m;
scanf("%d%d", &n, &m);
if(n > m)
{
puts("0");
return;
}
int k = 0;
m ++ ;
for(int i = 30; i >= 0; i -- )
{
int pi = n >> i & 1, mi = m >> i & 1;
if(pi == 0 && mi == 1) k += (1 << i);
else if(pi == 1 && mi == 0) break;
}
cout << k << endl;
}
int main()
{
int t;
scanf("%d", &t);
while (t -- ) solve();
return 0;
}