线性基（又称 XOR 基、异或基）是用来高效处理一组数在线性空间（GF(2) 向量空间）上的“异或线性组合”问题的数据结构。它的核心思想是：把一组整数看成二进制向量，维护一组“基向量”，使得任意一个数都能表示成这些基向量的异或和，且基向量之间两两“独立”（无法互相通过异或得到）。

为什么需要线性基？

  1. 求最大子集异或和

    给定一组数，选一个子集，使得它们的异或和最大。

  2. 判断一个数能否表示

    给定目标值 T，判断是否存在若干数异或后等于 T。

  3. 枚举所有可能的异或和

    统计所有子集能产生的不同异或和数量。

核心原理

  1. 向量空间视角

    把整数看作长度为 W （通常是 32 或 64）的二进制向量，异或运算对应于 GF(2) 上的向量加法。

  2. 基向量

    维护一个长度为 W 的数组 basis[]，其中 basis[k] 是最高位为 k （从 0 到 W−1）的“基向量”。

  3. 插入新向量

    对于待插入的数 x：

    1
    2
    3
    4
    5
    6
    7
    for k = W-1 … 0:
        if 第 k 位的 x 为 1:
            if basis[k] == 0:
                basis[k] = x;   // 找到新基，插入结束
                break
            else:
                x ^= basis[k];  // 消掉 x 在第 k 位的 1，再继续

    如果最终 x 被消成 0，说明它在已有基下可表示，无需插入。

  4. 查询最大异或和

    维护好 basis[] 后，想要从一组数里选若干得到最大异或和，只需：

    1
    2
    3
    answer = 0
    for k = W-1 … 0:
        answer = max(answer, answer ^ basis[k])

    依次尝试能否“打开”更高位。

C++示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int W = 31;            // 最高到 2^30
int basis[W+1] = {0};        // 初始化全 0

// 插入一个数 x
void insert_basis(int x) {
    for (int k = W; k >= 0; --k) {
        if (!(x & (1 << k))) continue;        // x 第 k 位为 0，跳过
        if (!basis[k]) {                      // 目前无基，x 成为新基
            basis[k] = x;
            return;
        }
        x ^= basis[k];                        // 消掉当前位，再继续
    }
    // 若走到这里，x 最终被消成 0，说明冗余
}

// 计算最大异或和
int get_max_xor() {
    int res = 0;
    for (int k = W; k >= 0; --k) {
        res = max(res, res ^ basis[k]);
    }
    return res;
}

Python示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
W = 31                        # 支持到 2^31
basis = [0] * (W + 1)         # basis[k] 存放最高位为 k 的基向量

def insert_basis(x: int) -> None:
    """
    将整数 x 插入线性基。
    """
    for k in range(W, -1, -1):
        if not ((x >> k) & 1):
            continue
        if basis[k] == 0:
            # 找到空位，x 成为新的基向量
            basis[k] = x
            return
        # 否则，用已有基消去 x 在第 k 位的 1
        x ^= basis[k]
    # 若 x 最终变为 0，则表示它是冗余的，无需插入

def get_max_xor() -> int:
    """
    在已插入的数中，选子集求最大异或和。
    """
    res = 0
    for k in range(W, -1, -1):
        # 若使用 basis[k] 能提升结果，就异或它
        if (res ^ basis[k]) > res:
            res ^= basis[k]
    return res