小殘的程式光廊

How to swap two variables without using a temporary variable.

解法

常見的方法有以下方式：

XOR法

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

加減法

a = a + b
b = a - b
a = a - b

乘除法

a = a * b
b = a / b
a = a / b

由於使用加減乘除有可能會有溢位(overflow)的問題，所以最好的方式是使用位元運算的XOR。

說明

使用位元運算並不好去理解為什麼這樣子做就可以達到交換的目的，就算是寫例子也還是不瞭解，這邊數學的角度去解釋，應該可以幫助思考，首先瞭解以下三點：

1. 首先我們知道XOR的定義是：有且僅有一個為真，換句話說就是，相同的為0，不同的為1。
2. 有了以上的定義，我們假設一變數N，當N ^ N的時候，由於每個位元必定相同，所以結果一定是0。
3. 而N ^ 0的時候，只有在位元是1的地方會不同，所以結果就是N本身。

當有了以上三點條件之後，我們再列出數學命題：

假設X, Y, Z為未知數, a, b為已知數, 已知
X = a ^ b
Y = X ^ b
Z = X ^ Y
求Y, Z

我們可以將X代入第二式，並依據前面所提到的三點條件，可得知

Y = (a ^ b) ^ b = a ^ b ^ b = a ^ (b ^ b) = a ^ 0 = a

接著將X, Y代入Z，可得

Z = (a ^ b) ^ a = a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

將以上推導對照程式的XOR法就能理解交換之原理，當然也可以直接背起來就好。