1 定义与基本性质

异或（Exclusive OR，简称XOR）是一种二元逻辑运算，其输出为真当且仅当两个输入值不同（一个为真、一个为假）。在数学、计算机科学、电子工程及密码学中具有广泛的应用。异或的符号通常表示为 ⊕、⊻、XOR 或 ^（编程中）。其真值表为：0⊕0=0、0⊕1=1、1⊕0=1、1⊕1=0。异或运算满足交换律、结合律，并具有自反性（A⊕A=0）等优良性质，常被用于错误检测、简易加密、数据交换（如不使用临时变量的值互换）以及神经网络的激活函数等场景。

1.1 真值表

异或运算的真值表定义了两个布尔输入的所有可能组合及其输出结果。设输入为A和B，输出为Q，则真值表如下：

ABQ (A⊕B)
000
011
101
110

从真值表可见，异或本质上是一种“不相容或”关系：当输入相同时输出为假，输入不同时输出为真。

1.2 符号表示

异或在不同的领域和语境中拥有多种符号表达方式，但核心含义一致。

1.2.1 数学符号

在数学和逻辑学中，异或的常用符号有：

  • ⊕（圆圈内加号，通常读作“oplus”）
  • ⊻（逻辑异或符号，Unicode中为U+22BB）
  • ∨̇（带点的或号，较少见）

在代数结构中，⊕也常表示模2加法。

1.2.2 编程语言中的运算符

在编程语言中，异或运算符通常用脱字符（^）表示。例如：

  • C、C++、Java、JavaScript、Python（作为位运算符）、Go、Rust 等：a ^ b
  • 在Verilog和VHDL硬件描述语言中，使用 ^ 作为归约异或或二元异或。
  • 一些语言（如Pascal）使用 xor 关键字。
  • 在SQL中，异或运算符为 ^（部分数据库）或函数 XOR。

1.3 逻辑等价式

异或可以通过基本的与、或、非逻辑门进行组合表达，也可以化简为蕴含关系的形式。

1.3.1 与、或、非的组合表达

异或的标准逻辑表达式是：

A ⊕ B = (A ∧ ¬B) ∨ (¬A ∧ B)

即：A真B假，或A假B真。另一种等价形式为：

A ⊕ B = (A ∨ B) ∧ ¬(A ∧ B)

即：至少一个为真，但不能同时为真。

1.3.2 蕴含关系的化简

利用蕴含关系（→），异或可表示为：

A ⊕ B = ¬(A → B) ∧ ¬(B → A)

或等价地：A ⊕ B = (A → ¬B) ∧ (¬A → B)

这些形式在逻辑推导中常被用来消除异或运算符，将其转化为更基础的门电路。

2 数学特性

异或运算具有优雅的代数性质，使其在数学和计算机科学中成为基石之一。

2.1 交换律与结合律

交换律：对于任意布尔值A、B，有 A⊕B = B⊕A。异或运算的输出与输入顺序无关。

结合律：对于任意A、B、C，有 (A⊕B)⊕C = A⊕(B⊕C)。这意味着多输入异或可以任意分组计算，结果唯一。

这两个性质使得异或可以扩展到任意多个变量的运算，结果仅取决于输入中1的个数是奇数还是偶数。

2.2 恒等式与自反性

2.2.1 与0异或：保持原值

对于任意布尔值A，有 A⊕0 = A。0是异或运算的单位元。这一性质在数据掩码和清零操作中非常有用。

2.2.2 与自身异或：结果为0

对于任意布尔值A，有 A⊕A = 0。这是异或的自反性或称幂零性。利用这一性质，可以设计出“无临时变量交换”等经典算法。

2.3 异或作为模2加法

从代数角度看，异或等价于模2加法，即两个二进制位相加，忽略进位。在布尔域GF(2)中，加法和减法没有区别（因为-1=1），异或同时扮演了加法和减法的角色。

2.3.1 在伽罗瓦域中的角色

异或是有限域GF(2)中加法运算的唯一实现。在GF(2)中，加法对应于逻辑异或，乘法对应于逻辑与。基于GF(2)的线性代数、纠错码（如线性分组码）和密码学（如AES的字节加法）均依赖异或。

2.3.2 与奇偶校验的关系

一个多比特序列的奇偶校验位，等于所有比特的异或结果。如果序列中1的个数为奇数，则异或结果为1；为偶数则结果为0。因此，异或天然是奇偶校验的数学基础。

3 电路实现

数字电路中，异或门可通过多种方式构建，既可以使用基本逻辑门，也可以使用CMOS晶体管直接实现。

3.1 基本门电路组合

3.1.1 用与、或、非构建XOR

根据逻辑表达式 A⊕B = (A·¬B) + (¬A·B)，使用两个与门、两个非门和一个或门即可实现。标准电路由两个与门、一个或门和两个非门组成。

3.1.2 用与非门（NAND）构建XOR

由于与非门是通用门，异或门可以用四个与非门实现。典型拓扑为：

  • 第一层：两个NAND，分别输入(A, B)和(A, B)的变体
  • 第二层：一个NAND接收第一层输出
  • 第三层：一个NAND接收第二层输出和另一个信号

具体连接方式（常见于教材）：令 X = NAND(A, B)，Y = NAND(A, X)，Z = NAND(B, X)，则输出W = NAND(Y, Z)即为A⊕B。

3.2 CMOS晶体管级实现

CMOS工艺中，异或门通常使用传输门（Transmission Gate）或互补逻辑实现。一种典型的CMOS XOR电路由12个晶体管组成（6个PMOS和6个NMOS），通过构造对称的推挽结构实现。现代工艺中也会使用更多晶体管的变体以优化速度或功耗。

3.3 三态门与多输入异或

在数字系统中，有时需要将多个输入进行异或操作（如奇偶校验）。多输入异或可以用树形结构串联基本异或门实现。利用异或的结合律，这种树形连接保证了无论输入顺序如何，输出都是所有输入的模2和。在FPGA中，LUT（查找表）可以直接实现多输入异或，通常支持4~6输入。

4 应用领域

异或因其简洁高效的特性，在多个工程和科学领域占据重要地位。

4.1 计算机科学

4.1.1 交换两个变量（无需临时变量）

4.1.1.1 经典算法示例

使用异或交换两个整数值（假设变量a和b）的经典代码：

a = a ^ b;
b = a ^ b;
a = a ^ b;

原理：第一步后a = a⊕b，第二步b = (a⊕b)⊕b = a⊕(b⊕b)=a⊕0=a，第三步a = (a⊕b)⊕a = b⊕(a⊕a)=b⊕0=b。交换完成。

4.1.1.2 潜在陷阱（整数溢出、指针）

该算法在大多数平台工作良好，但存在以下问题：

  • 同一地址陷阱：如果a和b指向同一内存地址（例如交换数组元素时索引相同），第一步后值变为0，后续步骤导致所有值归零。因此必须确保a和b不是同一对象。
  • 整数溢出：异或操作不会产生溢出，因此安全。但该算法比临时变量交换慢（现代CPU流水线中更差），且编译器通常不会将其优化为更快的版本。
  • 指针类型：在弱类型语言中，指针和整数混合使用异或可能导致未定义行为。在C/C++中，对指针进行异或运算是未定义行为（除非通过整数转换）。

4.1.2 哈希函数与校验和

异或广泛用于构造简单的哈希函数和校验和。例如，IP数据报头部校验和将16位字以1的补码求和后取反，但底层求和本身依赖于异或的“不进位加法”性质。许多轻量级哈希（如XOR-based hash）将输入数据按块异或，作为指纹。尽管碰撞率高，但计算速度快。

4.1.3 位图与布尔掩码操作

在位图图像处理中，异或用于切换像素位（例如，在黑白位图上画橡皮擦或光标）。掩码操作中，用异或可以将特定位取反：value ^= mask。这种操作在低级图形编程（如游戏开发、GUI库）中很常见。

4.2 密码学

4.2.1 一次性密码本（One-time Pad）

一次性密码本是理论上绝对安全的加密方案，其核心操作就是异或。加密：密文 = 明文 ⊕ 密钥；解密：明文 = 密文 ⊕ 密钥。只要密钥是真随机、与明文等长且只使用一次，则该方案不可破解。然而密钥分发与管理成本极高，实际中极少使用。

4.2.2 对称加密中的轮函数

4.2.2.1 AES中的密钥加法层

AES（高级加密标准）在每一轮开始时，将轮密钥与当前状态矩阵进行逐字节异或（AddRoundKey）。这一操作使得密钥与明文/密文混合，提供了基本的混淆。由于异或的可逆性（与同一个密钥再异或一次即可恢复），解密时使用相同的异或操作。

4.2.2.2 RC4与流密码

RC4是一种流密码，其输出密钥流与明文进行异或来生成密文。许多现代流密码（如ChaCha20）也使用异或作为最终组合方式。异或的轻量级特性使得流密码在硬件和软件中都有高性能。

4.3 通信与错误检测

4.3.1 奇偶校验位

在异步串行通信（如UART）中，发送方在数据字节后附加一个奇偶校验位，该位等于数据中所有比特的异或（偶校验）或其反（奇校验）。接收方重新计算并与接收到的校验位进行比较，可检测到奇数个比特的错误。

4.3.2 循环冗余校验（CRC）中的XOR

CRC算法将数据视为二进制多项式，通过生成多项式进行模2除法（实质是逐次异或）。每一轮的移位与异或操作是CRC硬件实现的核心。CRC广泛应用于以太网、存储设备等，是重要的错误检测手段。

4.4 趣味与梗文化

4.4.1 “异或即不同”的段子：程序员的情商测试

程序员之间流传着一个经典梗：“当你问程序员‘你喜欢我还是她？’时，程序员的回答会是什么？答案是：XOR。”因为异或表达“两者只能选一个”。类似地，在恋爱选择中，异或被视为理性的象征——但也常被调侃为“程序员式情商低”。

4.4.2 异或门表情包与网络迷因

网络社区中，异或门的逻辑符号（一个圆形加一个加号，或“^”符号）被用来制作表情包。例如，将“^”放在两个对立事物之间表示矛盾或二选一。一些meme将异或门与“选择困难症”联系起来，或在程序员聊天群中作为“加密”暗号。

5 相关运算与扩展

5.1 同或（XNOR）的对比

同或（XNOR）是异或的取非，即输出为真当且仅当两个输入相同。其符号通常为⊙或⊕上加横线。真值表为：0 XNOR 0 = 1, 0 XNOR 1 = 0, 1 XNOR 0 = 0, 1 XNOR 1 = 1。XNOR等价于A⊕B的取反，也等于(A∧B)∨(¬A∧¬B)。在电路设计中，XNOR常用于比较器。

5.2 多变量异或的奇偶性

对于n个布尔变量的异或，其输出等于所有输入变量中值为1的个数的奇偶性：若奇数则为1，偶数则为0。这种“奇偶性函数”在编码理论中非常重要，也是LDPC码和Reed-Muller码的基础。

5.3 模糊逻辑与多值逻辑中的异或

在模糊逻辑中，异或可以扩展为一种广义的运算，通常定义为 min(1, a+b-2a·b) 或 max(0, a+b-1) 等形式。多值逻辑（三值及以上）中，异或可以有不同的定义，常见的是基于模2加法的推广，但通常限制在数量有限的代数结构内。

6 历史与起源

6.1 布尔代数中的诞生

异或的概念萌芽于19世纪中叶。乔治·布尔（George Boole）在1847年的《逻辑的数学分析》和1854年的《思维规律的研究》中建立了布尔代数，其中包含了“排他性的或”的概念（即“要么A要么B，但不可兼得”），但未赋予独立符号。当时的逻辑学家将异或视为“不相容的析取”，与“相容的析取”（即OR）区分开来。

6.2 克劳德·香农的开关电路理论

1937年，克劳德·香农（Claude Shannon）在其硕士论文《继电器与开关电路的符号分析》中，首次将布尔代数应用于电子开关电路。他明确指出了异或运算可以通过继电器触点组合实现，并分析了其化简方法。这一工作奠定了数字电路设计的理论基础，异或门随之成为基本逻辑元件之一。

6.3 早期计算机中的异或指令

最早的电子计算机之一——ENIAC（1945年）并未直接提供异或指令，但通过组合电路可以实现。1950年代，IBM 701和后续机器开始在算术逻辑单元（ALU）中引入异或指令，通常作为“按位异或”操作直接暴露给程序员。异或由于其对称性和高效性，很快成为汇编语言中常用的位操作指令。随着集成电路的发展，异或门被集成到多个TTL及CMOS系列中（如74LS86），成为标准逻辑器件。