【笔记】算法设计：异或空间线性基

说明算法设计应用之前，首先明确异或空间线性基：一种数据结构。用于处理异或关系（运算）下的向量空间。

1.什么是异或（定义和性质）

（1）定义
异或，即XOR，exclusive OR，是一种逻辑运算，当两个输入值相同时输出0（false），不同时输出1（true）。记作⊕ 或 ^，异或门是半加器、全加器的核心组件。
（2）性质
异或的性质：
①交换律；
②结合律；
③自反性：自己异或结果为0，A⊕ A=0；
④A⊕ 0=A；
⑤可逆性：若A⊕ B=C，则A⊕ C=B，反之亦然。

2.异或空间线性基的构造方法

前置知识：规定，线性空间： 设正整数有限集S，
span(S)={XOR(T)∣T≠∅,T⊆S}.\mathrm{span}(S)=\{\mathrm{XOR}(T)∣T≠∅, T⊆S\}.span(S)={XOR(T)∣T=∅,T⊆S}.
基：去掉dependent的向量。举例：单位矩阵。
异或和：
$$\mathrm{XOR}(S)=S1\mathrm{xor}S2\mathrm{xor}...\mathrm{xor}Sn$$

构造方法如下：
初始化一个线性基数组base，长度为二进制位数（如：32位），初始值为0；
对于每个数x，从高位到低位检查：
若x的第i位为1，检查base[i]是否为空；
①若为空，将x存入base[i]，结束；
②若不为空，将x异或base[i]，并继续处理下一位。
C++代码：

void insert(int x) {for (int i = 30; i >= 0; i--) {if ((x >> i) & 1) {//x右移i位，和1按位运算，判断最低位1还是0if (!base[i]) {base[i] = x;//文中①情况。。。return;}x ^= base[i];//文中②情况。。。}}
}

3.异或空间线性基的应用

（1）通过求解线性基，合并不同集合；
（2）求解异或空间中的第k小值（或第k大值）：先对线性基进行重构，保证每个基最高位唯一，然后将k二进制表示的数与重构后的基对应位进行匹配。
（3）判断某数能否用线性基表示：将该数插入线性基，如果最终被消为0，则可以表示。

补充： 这样应用的复杂度分析：
1）构建线性基的时间复杂度为 $O(n\log C)$，其中 $C$ 是数的最大值。
2）查询操作的时间复杂度通常为 $O(\log C)$。
3）空间复杂度为 $O(\log C)$。

4.算法设计例举

异或空间线性基作为一种工具，涉及算法设计应用很多，不详细展开。（1）加密算法设计。利用可逆性加密，还有快速计算异或空间；
（2）某些博弈问题中，（结合异或和）可用于分析必胜策略；
（3）校验算法设计。利用异或检测数据一致性。
（4）排序，先按值排序，异或了一个线性基之后肯定更大；
（5）求解问题。获取计算异或和、最大值、最小值等等。。。

5.小结

线性基在处理异或（XOR）问题时非常有效率，广泛应用于竞赛编程和算法设计中。通过合理利用异或线性基，可以高效解决许多与异或运算相关的算法问题。