x>>i&1 的解释

#include<iostream>
using namespace std;
const int N=31*1e5;
int f[N][2],g[N],index;
void insert(int x)//创建trie树
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
    //x>>i&1 是x的二进制表示中第i位上的数
        if(!f[p][(x>>i&1)]) f[p][(x>>i&1)]=++index;
        p=f[p][x>>i&1];
    }
}
int query(int x)//直接返回最大异或对
{
    int p=0,res=0;
    //为什么取30?
    //题目给的数据范围是[0,2^31) 注意2^31没有取到
    //因为都是整数 所以[0,2^31)其实就是[0,2^31-1]
    //所以位数为31,最大右移30位即可(为什么位数为31位? 假设31的二进制上每位数都为1,利用等比数列求和公式可以知道,31位的二进制对应的最大十进制数就是2^31-1)
    for(int i=30;i>=0;i--)
    {
    //res+=1<<i怎么理解?
    // 只有当if(f[p][!(x>>i&1)]) 成立时,才会执行res+=1<<i
    //而if(f[p][!(x>>i&1)]) 的意思是如果trie数中的第i位数是否存在x的二进制数的第i位数取反的值
    //我们知道 当trie数中的第i位数存在x的二进制数的第i位数取反的值,此时该位上的异或值最大,最大为1
    //所以此时x的二进制数的第i位数与trie数中的第i位数异或值为1;
    //∴res+=1<<i
        if(f[p][!(x>>i&1)]) res+=1<<i,p=f[p][!(x>>i&1)];
        else p=f[p][x>>i&1];
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    int res=0;
    for(int i=0;i<n;i++) cin>>g[i];
    for(int i=0;i<n;i++) insert(g[i]);
    for(int i=0;i<n;i++)
        res=max(res,query(g[i]));
    cout<<res;
    return 0;
}