C. Mikasa(按位枚举）

题目：

题目链接

You are given two integers nn and mm. Find the MEXMEX of the sequence n⊕0,n⊕1,…,n⊕mn⊕0,n⊕1,…,n⊕m. Here, ⊕ is the bitwise XOR operator.

MEX of the sequence of non-negative integers is the smallest non-negative integer that doesn't appear in this sequence. For example, MEX(0,1,2,4)=3, and MEX⁡(1,2021)=0.

Input

The first line contains a single integer tt (1≤t≤30000)  — the number of test cases.

The first and only line of each test case contains two integers nn and mm (0≤n,m≤10^9).

Output

For each test case, print a single integer  — the answer to the problem.

Example

5

3 5

4 6

3 2

69 696

123456 654321

4

3

0

640

530866

题目大意：

这个题的意思是说给你一个n和m，然后让你求n^0,n^1,n^2-------n^m中最小没有出现的那个数k,

题解

官方题解

如果k在序列中存在，那么一定有x使得0≤x≤m n⊕x=k，

你知道n⊕k=x等于n⊕x=k吗?

所以我们可以检查n⊕k是否≤m !很简单!

修正后的问题是求出最小的非负整数k，使n⊕k≥m+1。你现在能解决吗?

这样我们可以从大到小按位枚举，

认为使用比特。

设p=m+1, ti是t的第i位，我们要找到最小的k使n⊕k≥p。

让我们贪婪地从最高位到最低位构建k。假设我们要找到k的第i位更高的位已经生成了。显然，如果可能的话，我们将尝试把这个部分去掉。什么时候不可能?思考。

如果ni=pi，则设ki=0为ni⊕0=ni≥pi。如果ni=1和pi=0，我们可以在这里中断，将k的剩余位设置为无论n的剩余位是什么，n⊕k总是大于p。最后，如果ni=0和pi=1，我们必须设置ki=1，因为我们没有其他选择。

 if(!((n>>i)&1)&&((m>>i)&1)){
       ans|=(1<<i);
}
 if(((n>>i)&1)&&!((m>>i)&1)){
       break;
 } 

　这个就是核心代码，n^k>=m，就是如果n的这一位为0的话，那么k这一位必须是1，然后继续枚举下去，如果n这一位为1，m为0那么可以结束枚举了，此时已经大于了

代码：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
int a[maxn];
int t;
int main(){
    cin>>t;
    while(t--){
        ll n,m;
        cin>>n>>m;
        m++; 
        ll ans=0;//n^ans>=m 
        for(int i=30;i>=0;i--){
            if(!((n>>i)&1)&&((m>>i)&1)){
                ans|=(1<<i);
            }
            if(((n>>i)&1)&&!((m>>i)&1)){
                break;
            } 
        }
        printf("%lld\n",ans);
    }
}

You are given two integers nn and mm. Find the MEXMEX of the sequence n⊕0,n⊕1,…,n⊕mn⊕0,n⊕1,…,n⊕m. Here, ⊕⊕ is the bitwise XOR operator.

MEXMEX of the sequence of non-negative integers is the smallest non-negative integer that doesn't appear in this sequence. For example, MEX(0,1,2,4)=3MEX⁡(0,1,2,4)=3, and MEX(1,2021)=0MEX⁡(1,2021)=0.