XOR的特性（A XOR B XOR B = A），我们可以用加密的密钥解密。由于XOR操作是可逆的，我们只需要按相反的顺序和相同的密钥进行XOR就能解密。

100

010

110

110

010

100

核心定义：什么是异或？

异或，英文为 XOR 或 Exclusive OR，中文全称是“异或逻辑运算”。它是一种基本的二进制位运算。

它的核心逻辑是：“相异为真，相同为假”。

也就是说，当比较的两个位（bit）不相同时，结果为 1（真）；当两个位相同时，结果为 0（假）。

真值表

我们可以用一个真值表来清晰地展示它的规则。假设有两个输入 A 和 B，一个输出 Y。

A B Y (A XOR B)
0 0 0
0 1 1
1 0 1
1 1 0

从表中可以一目了然地看到：

  • 当 A 和 B 都是 0（相同）时，结果是 0。
  • 当 A 和 B 一个是 0，一个是 1（相异）时，结果是 1。
  • 当 A 和 B 都是 1（相同）时，结果是 0。

常见的符号表示

在不同的领域，异或有不同的表示符号：

  • 编程语言中常用： ^ （脱字符号）
  • 数学/逻辑学中常用： ⊕ （圆圈加号）
  • 电子工程中常用： XOR

一个简单的例子

让我们用十进制数来演示一下异或运算（实际是在二进制位上操作的）：

计算 5 ^ 3 （^ 是编程中的异或符号）

  1. 转换为二进制：
    • 5 的二进制是 101
    • 3 的二进制是 011

按位进行异或运算（对齐，一位一位地比较）：

  1. text
1
2
3
4
1 0 1   (5)
XOR 0 1 1   (3)
    -----
    1 1 0   (6)
- 最右边： `1` XOR `1` = `0`
- 中间： `0` XOR `1` = `1`
- 最左边： `1` XOR `0` = `1`
  1. 将结果转换回十进制：二进制 110 等于十进制 6。

所以，5 ^ 3 的结果是 6。

异或运算的重要特性

异或有一些非常独特且有用的数学特性，这些特性是它在各种算法中得以应用的基础。

  1. 交换律: A ^ B = B ^ A
  2. 结合律: (A ^ B) ^ C = A ^ (B ^ C)
  3. 与自身的运算: **A ^ A = 0** （任何数与自己异或，结果为0）
  4. 与 0 的运算: **A ^ 0 = A** （任何数与 0 异或，结果还是自己）
  5. 自反性: 如果 A ^ B = C，那么 C ^ B = A 且 C ^ A = B。
    • 这个特性是加密和解密、交换两个变量等功能的核心。

异或的常见应用

凭借上述特性，异或在计算机科学中有着广泛的应用。

1. 交换两个变量的值（不使用临时变量）

这是一个经典的面试题。利用异或的自反性，可以不需要第三个临时变量就交换两个数。

python

1
2
3
4
5
6
7
8
9
10
a = 5
b = 10

print(f"交换前: a = {a}, b = {b}")

a = a ^ b  # a 现在变成了 5 ^ 10
b = a ^ b  # b = (5 ^ 10) ^ 10 = 5 ^ (10 ^ 10) = 5 ^ 0 = 5
a = a ^ b  # a = (5 ^ 10) ^ 5 = (5 ^ 5) ^ 10 = 0 ^ 10 = 10

print(f"交换后: a = {a}, b = {b}")

输出：

text

1
2
交换前: a = 5, b = 10
交换后: a = 10, b = 5

2. 简单的加密和解密

利用自反性，可以使用同一个密钥对数据进行加密和解密。

  • 加密： 密文 = 明文 ^ 密钥
  • 解密： 明文 = 密文 ^ 密钥

python

1
2
3
4
5
6
7
8
9
10
plain_text = 42        # 原始数据
key = 123              # 密钥

# 加密
cipher_text = plain_text ^ key
print(f"密文: {cipher_text}") # 输出一个看起来是乱码的数字

# 解密
decrypted_text = cipher_text ^ key
print(f"解密后的明文: {decrypted_text}") # 输出 42

3. 在算法题中的应用：找出“落单”的数字

这是一个非常著名的算法题：

一个非空整数数组中，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

解决方案：利用 A ^ A = 0 和 A ^ 0 = A 的特性，将所有数字一起进行异或运算，成对出现的数字会变成 0，最后剩下的就是那个“落单”的数字。

python

1
2
3
4
5
6
7
8
9
def single_number(nums):
    result = 0
    for num in nums:
        result ^= num  # 等同于 result = result ^ num
    return result

# 示例
arr = [4, 1, 2, 1, 2]
print(single_number(arr))  # 输出：4

计算过程： 0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2 = (1^1) ^ (2^2) ^ 4 = 0 ^ 0 ^ 4 = 4

4. 图形学中的“异或”模式

在一些古老的绘图软件或硬件中，有一种“异或”绘图模式。当你在同一个位置用同一种颜色画两次时，第二次绘制会擦除第一次的痕迹，因为 颜色 ^ 颜色 = 0（背景色），从而实现了一种“橡皮擦”效果。

总结

  • 异或（XOR） 是一种“相异为1，相同为0”的二进制逻辑运算。
  • 它的关键特性是 **A ^ A = 0** 和 **A ^ 0 = A**，以及强大的自反性。
  • 这些特性使其在变量交换、简单加密、算法优化（如找落单数）和底层计算等领域非常有用。