异或（^）运算

我们对异或运算都很熟悉，运算的法则是，两个数进行异或，相同为0， 相异为1；即

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

我们也可以将疑惑运算理解为“无进位相加”，异或运算还具有以下性质

• 0和任意数进行异或，得到的结构还是这个数，即0 ^ N = N

• 异或运算满足交换律和结合律：

  • 交换律：a ^ b = b ^ a
  • 结合律：(a ^ b) ^ c = a ^ (b + c)

• 一组数据，a, b , c…他们之间进行异或操作，得到的结果与进行异或的顺序无关。

所以我们在进行两个数交换时，可以采取异或运算进行交换；

首先，我们先看一下在C++中，不用异或操作进行两个数交换的函数应该怎么写：

#include 

void Swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

int main(void) {
    int a = 10;
    int b = 20;
    std::cout << "a = " << a << ", b = " << b << std::endl;
    Swap(a, b);
    std::cout << "a = " << a << ", b = " << b << std::endl;
}

此时的输出结果为：

a = 10, b = 20

a = 20, b = 10

此时我们可以看到，我们在函数中定义了一个临时变量temp，进行辅助交换。

#include 

void Swap(int& a, int& b) {
	a = a ^ b;  // 1
	b = a ^ b;  // 2
	a = a ^ b;  // 3
}

int main(void) {
    int a = 10;
    int b = 20;
    std::cout << "a = " << a << ", b = " << b << std::endl;
    Swap(a, b);
    std::cout << "a = " << a << ", b = " << b << std::endl;
}

这段代码和上面的代码功能一样，都是进行了两个数的交换， 那我们怎么理解呢？

首先我们假设a为X,b为Y;

• 执行代码1后，a的值为X ^ Y; b的值不变，还是Y;
• 执行代码2后，a的值为X ^ Y; b的值为X ^ Y ^ Y,也就是X；
• 执行代码3后，a的值为X ^ Y ^ X, 也就是X; b的值不变， 还是Y；

所以，我们通过异或操作，完成了两个数的交换，且不需要额外的辅助变量。

注意：

我们采用异或操作交换两个数的时候，要交换的两个数值可以相同，比如你要交换两个10，这都不会导致程序输出结果出现问题，但是两个数一定不能指向同一块内存，否则，会将这块内存的数值抹为0!

例如：

#include 

void Swap(int& a, int& b) {
	a = a ^ b;  // 1
	b = a ^ b;  // 2
	a = a ^ b;  // 3
}

int main(void) {
    int a = 10;
    int b = 10;
    std::cout << "a = " << a << ", b = " << b << std::endl;
    Swap(a, b);  // 这不会出现问题
    std::cout << "a = " << a << ", b = " << b << std::endl; // a = 10, b = 10
    int c = 20;
    Swap(c, c);
    std::cout << "c = " << c << std::endl; // c = 0
}

2022/5/31