强大的数学原理，异或用以字符交换
强大的数学原理，异或用于字符交换
今天看到一篇有关字符串逆序的各种实现算法的文章，里面有一种不使用临时变量的字符交换算法把我震惊了。
上网搜了下，发现百度百科里就有这么一段：
xor运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即（a xor b) xor b = a。
x <- x # y
y <- x @ y
x <- x @ y
执行了第一句后x变成了x # y。那么第二句实质就是y <- x # y @ y，由于#和@互为逆运算，那么此时的y变成了原来的x。第三句中x实际上被赋值为（x # y) @ x，如果#运算具有交换律，那么赋值后x就变成最初的y了。这三句话的结果是，x和y的位置互换了。
加法和减法互为逆运算，并且加法满足交换律。把#换成+，把@换成-，我们可以写出一个不需要临时变量的swap过程（Pascal）。
procedure swap(var a,b:longint);
begin
a:=a + b;
b:=a - b;
a:=a - b;
end;
好了，刚才不是说xor的逆运算是它本身吗？于是我们就有了一个看起来非常诡异的swap过程：
procedure swap(var a,b:longint);
begin
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
注意：位运算版本的交换两数不适用于一个数的自我交换。也就是说，如果上述程序的“b”改成“a”的话，其结果是变量a变成零。因此，在使用快速排序时，由于涉及到一个数的自我交换，因此如果要在其中使用位运算版的交换两数的话，应该先判断。