线性代数中基就好像是向量中的基向量。线性基是异或运算的基，定义为通过原集合 $S$ 中的最小子集中的元素可以相互异或的值域 $Y$ 和原集合的相互异或的值域 $Y_{0}$ 相同。相当于用原集合中最少最精简的元素组成子集，实现原集合相同的的异或值域的效果。通常情况下很多和二进制有关的组合问题可以用线性基来完成，并且需要理解XOR位运算的含义。

性质

线性基集合能够实现原来集合的值域

线性基中的每一个元素的二进制最高位互不相同

线性基的子集异或和非0

线性基中每一个元素的异或方案是唯一的，运算出的得数唯一

其中第二个性质可以用来构造线性基的时候使用，有一个检查每一位1的情况来决定是否要加入到线性基集合中。

作用

线性基主要解决一些异或的组合问题，比如很典型的开关灯https://www.luogu.com.cn/problem/P3857问题，可以用第四个性质来解决。

1. 在 $O(\log n)$ 的时间复杂度下求出某个集合的子集异或和的最大最小值
2. 解决一些异或的搭配组合问题，比如出现异或相互抵消的https://www.luogu.com.cn/problem/P4570

代码实现

• 构造线性基

int p[100];
void insert(int val) {
  for (int i = 62; i >= 0; i--) {
    if (val & (1ll << i)) {
      // Check the position of the highest binary bit 1 of the number. If the
      // bit is empty, it can join the collection.
      if (!p[i]) {
        p[i] = val;
        return;
      }
      val ^= p[i];
      // If the bit of the highest binary bit array is not empty, XOR the
      // existing number of this bit and search again.
    }
  }
}

• 检查XOR可得性

这个就要解释一下了，知道的是一个数可以被线性基中的组合异或得到，如果最高位1对应在线性基中找得到，那么就和这个已有的进行异或。由下面这个性质可得如果这个数最后被异或使得所有位1都变成0，那么说明线性基中的数异或产生了它本身，也就是说它可以由该线性基XOR得到。

相同的数异或的结果是0，任何数和0异或得它本身

int p[100];
bool check(int val) {
  for (int i = 62; i >= 0; i--) {
    if (val & (1 << i)) {
      if (!p[i]) {
        // Unable to continue, indicating that this number cannot be obtained.
        return false;
      }
      val ^= p[i];
    }
  }
  // Going to this step means that the number has been reset to zero.
  return true;
}

实践应用

实际运用上主要是异或最大值和最小值，还有像上面的开关组合问题的使用。

这里有一个最大异或和的板题可以练习https://www.luogu.com.cn/problem/P3812。

XOR 位运算

位运算中最神奇的恐怕就是异或运算了，具有交换律和结合律和自反性。自反性就是 $A\oplus B\oplus B=A$ ，其实可以有结合律来得到，因为后两B异或是0，这也说明异或同样的数只有奇数次才会有效果。

异或运算运算的时候相当于二进制下不进位的加法运算，所以也叫半加运算，对于整数范围内的XOR运算就是将二进制的位对应进行异或运算。

• 快速比较

比较通常采用的是==来完成，利用相同值整型异或结果为0的特性可以使用异或来比较，速度稍微快一点点。就是记录下来玩一玩，具体效果十分不明显。

if (!(a ^ b)) {
  // code...
}