异或运算：二进制世界的神奇魔术

一、什么是异或运算？

异或（XOR，Exclusive OR）是计算机科学中最基础也最有趣的位运算之一。它的名字”异或”很贴切地描述了其含义：”异”表示不同，”或”表示逻辑或，合起来就是”当且仅当不同时为真”。

基本定义

对于两个二进制位：

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

用简单的话说：相同为0，不同为1。

二、C++中的异或运算符

在C++中，异或运算使用符号 ^：

int a = 5;    // 二进制：0101
int b = 3;    // 二进制：0011
int c = a ^ b; // 结果是 6，二进制：0110

基本用法示例

#include <iostream>
using namespace std;

int main() {
    int x = 12;  // 二进制：1100
    int y = 7;   // 二进制：0111
    
    cout << "x = " << x << " (" << bitset<4>(x) << ")" << endl;
    cout << "y = " << y << " (" << bitset<4>(y) << ")" << endl;
    cout << "x ^ y = " << (x ^ y) << " (" << bitset<4>(x ^ y) << ")" << endl;
    // 输出：x ^ y = 11 (1011)，因为 1100 ^ 0111 = 1011
    
    return 0;
}

三、异或运算的五大神奇性质

1. 交换律

a ^ b = b ^ a

2. 结合律

(a ^ b) ^ c = a ^ (b ^ c)

3. 自反性（最重要的性质！）

a ^ a = 0
a ^ 0 = a

4. 可逆性

如果 a ^ b = c
那么 a ^ b ^ b = a = c ^ b

5. 与0的关系

a ^ 0 = a
0 ^ a = a

四、异或运算的经典应用

1. 不使用临时变量交换两个数

void swap(int &a, int &b) {
    a = a ^ b;  // 步骤1：a = a ^ b
    b = a ^ b;  // 步骤2：b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a
    a = a ^ b;  // 步骤3：a = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b
}

2. 找出数组中唯一出现一次的数

int findSingleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;  // 利用 a ^ a = 0
    }
    return result;
}
// 如果数组中只有一个数出现一次，其他都出现两次，这个函数能找出那个数

3. 奇偶校验

// 计算一个数的二进制表示中1的个数的奇偶性
bool parity(int x) {
    bool parity = false;
    while (x) {
        parity ^= (x & 1);  // 每次翻转奇偶性
        x >>= 1;
    }
    return parity;
}

4. 简单的加密和解密

string encryptDecrypt(const string& data, char key) {
    string result = data;
    for (int i = 0; i < data.length(); i++) {
        result[i] = data[i] ^ key;  // 加密
    }
    return result;
}
// 注意：同样的操作可以用于解密！

五、实际编程中的应用场景

1. 算法竞赛中的应用

// 前缀异或：计算子数组异或和
vector<int> prefixXor(const vector<int>& arr) {
    int n = arr.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] ^ arr[i];
    }
    return prefix;
}

2. 游戏开发：棋盘状态判断

// 判断井字棋是否有玩家获胜
bool checkTicTacToe(const vector<vector<char>>& board) {
    const int winMasks[] = {7, 56, 448, 73, 146, 292, 273, 84};
    int player1 = 0, player2 = 0;
    
    // 将棋盘转换为位掩码
    for (int i = 0; i < 9; i++) {
        int bit = 1 << i;
        if (board[i/3][i%3] == 'X') player1 ^= bit;
        else if (board[i/3][i%3] == 'O') player2 ^= bit;
    }
    
    // 检查是否有获胜
    for (int mask : winMasks) {
        if ((player1 & mask) == mask) return true;  // 玩家1获胜
        if ((player2 & mask) == mask) return true;  // 玩家2获胜
    }
    return false;
}

3. 内存优化：用异或链表实现双向链表

class XORNode {
public:
    int data;
    XORNode* both;  // 存储prev ^ next的指针
    
    XORNode(int val) : data(val), both(nullptr) {}
};

六、注意事项和常见陷阱

1. 优先级问题

int a = 5, b = 3, c = 2;
int result1 = a ^ b & c;  // 错误：&优先级高于^
int result2 = (a ^ b) & c;  // 正确

2. 浮点数不能进行异或

// 错误！
float f1 = 3.14, f2 = 2.71;
// float f3 = f1 ^ f2;  // 编译错误！

3. 注意符号位

int x = -1;  // 二进制：111...111
int y = 1;   // 二进制：000...001
int z = x ^ y;  // 结果是 -2，因为符号位被改变

七、性能比较

异或运算是CPU中最快的操作之一，因为它只需要简单的硬件门电路：

操作	时钟周期	备注
XOR	1	最快
ADD	1-3	与XOR相当
MUL	3-4	较慢
DIV	10-20	最慢

八、练习题

基础题：交换两个变量的值，不使用临时变量
进阶题：找出数组中两个只出现一次的数字（其他数字都出现两次）
挑战题：实现一个函数，判断一个数的二进制表示是否是回文
实际应用：使用异或实现简单的校验和计算

九、总结

异或运算虽然看起来简单，但其应用却异常广泛：

它是加密算法的基础
在算法优化中经常使用
可以高效处理二进制问题
是许多巧妙算法的核心

掌握异或运算不仅仅是掌握一个运算符，更是理解了一种解决问题的思维方式。当你面对一个问题时，不妨想想：能不能用异或来解决？

记住这个魔法公式：a ^ a = 0和 a ^ 0 = a，这两个简单的公式能解决无数复杂的问题！

学习建议：多写代码实践，从简单的例子开始，逐步尝试解决更复杂的问题。异或运算的魅力只有通过实际应用才能真正体会到。