高斯消元求解异或方程组 - 编程数学 | C++ & Algorithm 编程研习社

用异或解谜：高斯消元求解异或方程组

你有没有玩过一种开关灯游戏？面前有几盏灯，每个开关按下后，会同时改变好几盏灯的状态（亮变灭，灭变亮）。你想让所有灯都亮起来，该按哪些开关呢？这其实就是一个异或方程组问题。异或方程组是每个方程和未知数都是0或1，所有运算都用异或（XOR，记作 ^ ）代替了普通的加减乘除。高斯消元法就是解开这类方程组的强力工具，它把初中的解方程组方法搬到了“模2加法”的世界里。

1. 异或运算与异或方程组

先回顾异或运算的规则（在二进制中，相当于“不进位加法”）：

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

你可以把异或理解为“相同为0，不同为1”。比如你上午有1颗糖，下午妈妈又给了1颗，你现在有0颗？不对，这是异或，不是普通加法。实际上异或在生活中常用于状态切换：按一下开关，灯的状态就异或1（0变1，1变0）。

异或方程组长这样（未知数 $x_1, x_2, x_3$ 都是0或1，所有运算都是异或）：

\begin{cases} x_1 \oplus x_2 = 1 \\ x_1 \oplus x_3 = 0 \\ x_2 \oplus x_3 = 1 \end{cases}

生活例子：三盏灯的谜题 假设有三盏灯，初始全灭（状态为0）。有三个开关：

开关1：同时改变灯1和灯2的状态
开关2：同时改变灯1和灯3的状态
开关3：同时改变灯2和灯3的状态

你想让所有灯都亮（状态变为1）。按下开关 $x_i$ 表示0（不按）或1（按）。那么灯1的最终状态 = 初始0 ⊕ (按下开关1则异或1) ⊕ (按下开关2则异或1) = $x_1 \oplus x_2$ 。我们希望它等于1，所以得到第一个方程： $x_1 \oplus x_2 = 1$ 。同理可得另外两个方程。解这个方程组就能找到按哪些开关。异或方程组就是用来描述这种“多个操作叠加影响”的问题。

2. 高斯消元在GF(2)上的原理

普通高斯消元解实数方程组时，通过加减消元把系数矩阵变成上三角，再回代解出未知数。在异或世界里，加法变成了异或（模2加法），乘法变成了与（AND），除法因为只有0和1，除以1就是本身，除以0不可行。所以我们只需把加减法换成异或，乘除法换成与和条件判断即可。

关键步骤：

主元选择：在当前列（第 col 列）里找到系数为1的行。如果所有行该列都是0，则跳过这一列（该未知数是自由变量）。
消去：用主元行（被选中的行）去异或掉其他行中该列的1。具体操作：对于每一行（除了主元行），如果该行第 col 列是1，则把整行异或主元行，即 row = row ^ pivot_row。
回代：从上三角矩阵的最后一行开始，从后向前算出每个变量的值。因为只有异或，累加结果也用异或。

对比普通高斯消元：普通消元需要乘除系数，异或消元里系数只有0和1，所以消去时只需判断是否为1，然后异或整行。另外，在普通消元中交换两行很常见，在异或消元中同样需要交换确保主元行在当前列有1。

3. 具体步骤（以三元方程组为例）

我们来看一个具体的例子，并一步一步演示。

方程组（系数矩阵 + 常数项 = 增广矩阵）：

\begin{cases} 1x_1 \oplus 1x_2 \oplus 0x_3 = 1 \\ 1x_1 \oplus 0x_2 \oplus 1x_3 = 0 \\ 0x_1 \oplus 1x_2 \oplus 1x_3 = 1 \end{cases}

写成增广矩阵（每行都是0或1）：

[1 1 0 | 1]
[1 0 1 | 0]
[0 1 1 | 1]

第1步：处理第1列（col=0） 在当前列中找系数为1的行。第0行和第1行都有1，选第0行作为主元行（通常选第一个出现1的行）。然后消去其他行的第0列：

第1行：第0列是1 → 将第1行异或第0行：[1 0 1 | 0] ^ [1 1 0 | 1] = [0 1 1 | 1]
第2行：第0列是0 → 保持不变。

现在的矩阵：

[1 1 0 | 1]
[0 1 1 | 1]
[0 1 1 | 1]

第2步：处理第2列（col=1） 跳过第0行（已经当过主元），看第1行和第2行。第1行第1列是1，选为主元行。然后消去其他行（第2行）的第1列：

第2行：第1列是1 → 异或第1行：[0 1 1 | 1] ^ [0 1 1 | 1] = [0 0 0 | 0]

矩阵变成：

[1 1 0 | 1]
[0 1 1 | 1]
[0 0 0 | 0]

第3步：处理第3列（col=2） 当前col=2，但第0行和第1行已经做过主元，第2行全0，没有系数为1的行，所以跳过。此时矩阵已是上三角（虽然第2行全0）。

第4步：回代 从最后一个有主元的行（第1行）开始。第1行对应方程： $0x_1 + 1x_2 + 1x_3 = 1$ 。注意我们按列索引，第1行主元在第1列，所以 $x_2$ 是主元变量。回代时，从后往前计算：

先看第2行：全0，常数项0，说明这个方程是恒等式（0=0），表示有一个自由变量（这里是 $x_3$ ）。
然后回代到第1行： $x_2 \oplus x_3 = 1$ ，所以 $x_2 = 1 \oplus x_3$ 。
最后第0行： $x_1 \oplus x_2 = 1$ ，代入 $x_2$ ： $x_1 = 1 \oplus x_2 = 1 \oplus (1 \oplus x_3) = x_3$ 。

因此解为： $x_1 = x_3,\ x_2 = 1 \oplus x_3$ ，其中 $x_3$ 可以是0或1。所以有两组解： $(0,1,0)$ 和 $(1,0,1)$ 。

4. 常见错误与调试

主元列全为0时不能跳过：如果某列没有系数为1的行，说明该未知数是自由变量，可以取0或1。新手容易忘记标记自由变量，导致回代时出错。
交换行要完整交换：包括常数项。如果用数组存储，交换两行时记得把常数也交换。
回代顺序错误：必须从最后一个主元行开始往前，每次只解一个变量。提前解还没出现的变量会出错。
无解判断：如果在消元过程中出现某一行系数全0但常数项为1，则方程组无解（例如0=1不可能）。此时应立即停止返回无解。
浮点数比较：在异或消元中所有值都是整数0或1，不用考虑浮点误差，所以用整数运算即可。

5. 完整可运行的代码示例（Python）

下面是一个完整的Python程序，它读入一个异或方程组（增广矩阵），用高斯消元求解，并输出解或提示无解/多解。

def gauss_xor(mat):
    # mat: 列表的列表，每行最后一个是常数项，其余是系数
    n = len(mat)          # 方程个数
    m = len(mat[0]) - 1   # 未知数个数
    row = 0               # 当前处理的行索引
    where = [-1] * m      # 记录每个变量对应哪一行（主元行）

    for col in range(m):
        # 在当前列找系数为1的行
        sel = row
        while sel < n and mat[sel][col] == 0:
            sel += 1
        if sel == n:      # 该列全0，跳过（自由变量）
            continue
        # 将找到的行交换到当前行
        mat[row], mat[sel] = mat[sel], mat[row]
        where[col] = row   # 记录该变量主元行

        # 用主元行消去其他行（包括下面和上面的行）
        for r in range(n):
            if r != row and mat[r][col] == 1:
                for c in range(col, m+1):
                    mat[r][c] ^= mat[row][c]
        row += 1

    # 检查无解：是否有行系数全0但常数项为1
    for r in range(row, n):
        if all(mat[r][c] == 0 for c in range(m)) and mat[r][m] == 1:
            return None   # 无解

    # 回代（实际上消元时已经消干净了，直接读出解）
    result = [0] * m
    for col in range(m):
        if where[col] != -1:
            # 变量对应主元行，该行除了col列和常数外都是0
            result[col] = mat[where[col]][m]
        else:
            # 自由变量，默认赋0（也可以赋1，有多解）
            result[col] = 0
    # 如果存在自由变量，返回标志
    free_vars = [col for col in range(m) if where[col] == -1]
    return result, free_vars

# 示例：解三盏灯问题
if __name__ == "__main__":
    # 增广矩阵：系数3x3，常数3x1
    matrix = [
        [1, 1, 0, 1],   # x1 ^ x2 = 1
        [1, 0, 1, 0],   # x1 ^ x3 = 0
        [0, 1, 1, 1]    # x2 ^ x3 = 1
    ]
    ans = gauss_xor(matrix)
    if ans is None:
        print("方程组无解")
    else:
        solution, free_vars = ans
        print("一个解为：", solution)
        if free_vars:
            print("存在自由变量：", free_vars, "，有无穷多解")

运行结果：

一个解为： [0, 1, 0]
存在自由变量： [2] ，有无穷多解

对应开关方案：不按开关1，按开关2，不按开关3（注意这里变量顺序：x1, x2, x3）。另一个解是 [1,0,1]，按开关1和3。

6. 完整示例：零花钱谜题

再举一个贴近生活的例子：小明每天有零花钱，他每周一、三、五各花1元买零食，周二、周四各花1元买文具，周三、周六各花1元买玩具。一周结束后他发现总共花了4元。问他每天花了多少钱？（假设每天只花0或1元，且周一和周日不花？）实际上我们可以用异或方程组模拟：设每天花钱与否为 $x_1$ （周一）到 $x_7$ （周日），每个花钱项目对应一个异或方程。但这里只演示一个简单版本。

更直接的是：你想知道班级里哪几位同学做了好事，但只知道一些“谁和谁一起做了”的线索，每个线索可以用异或表示“做了”为1，“没做”为0。高斯消元可以帮你找出所有可能的人选。

7. 相关知识点指引

线性基：如果方程组只有系数没有常数（齐次方程组），或者你想求一组基来表示所有解，可以学习线性基，它与异或高斯消元紧密相关。
图论与开关问题：很多开关灯问题可以转化为图上的奇偶性约束，用高斯消元或DFS解决。
组合数学：自由变量的个数决定了解的数量（2^k），这与组合数学中的子集计数有关。
密码学：二进制的线性方程组在密码学（如AES的列混合、线性反馈移位寄存器）中有广泛应用。

掌握了异或高斯消元，你就拿到了解决一大类逻辑谜题的金钥匙。从开关灯到数独，从电路设计到加密算法，它都是基础工具。现在，去试试你自己生活中的谜题吧！

例题精讲