线性基是用来求解数组子集最大异或和的一种方法。其思想与线性代数中的最大线性无关组相似。

线性基的性质

线性基有以下几种性质：

  1. 数组中的所有元素都能够用线性基中的元素相互异或计算出来
  2. 线性基中不存在异或值为0的子集
  3. 满足性质1的前提下，线性基中的元素个数是最少的。
  4. 线性基中每个元素二进制位数均不相同

线性基的计算

对于当前所求出来的线性基，我们在插入一个新的元素时（即使得其表示范围多一个数 x

），要保证插入的元素与其他元素异或不为零。

根据性质4，我们能够通过位运算对插入的元素进行异或计算：

x=p1⨁p2⨁…⨁pi⨁px

pi 为线性基中的某个基，则：
px=p1⨁p2⨁…⨁pi⨁x


根据性质4，我们求解的线性基中不能包含二进制位数相同的数，因此我们把x按照最高位向最低位异或的方式进行计算，假如当前x的二进制最高位所对应的基存在，则x异或这个基（此时x的值会改变），这样能够保证x的二进制位数至少能够减少1位，然后继续进行计算，计算终点有两种结果：

  1. x二进制最高位对应的基不存在，则把x插入线性基，运算结束
  2. x值变为0，说明当前线性基能够表示最开始的x，则直接结束。

这样就能够求出来 px

的值，即线性基需要插入的元素。

代码如下： 
void update(int x){
    for(int i=30;i>=0;i--){
        if(x>>i){
            if(!f[i]){
                f[i]=x;
                return ;
            }
            x^=f[i];
        }
    }
}