題目

不使用暫存變數交換兩個變數。
Swap two variables without using a temporary variable.

解法

常見的方法有以下方式：

加減法

1
2
3
a = a + b
b = a - b
a = a - b

乘除法

1
2
3
a = a * b
b = a / b
a = a / b

XOR 法

1
2
3
a = a ^ b
b = a ^ b
a = a ^ b

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

說明

加減乘除我們用數學角度來看很好理解，以加減為例：

1
2
3
4
假設 X、Y 和 Z 為未知數，a 和 b 為已知數，已知：
X = a + b
Y = X - b
Z = X - Y

X 代入第二式

1
Y = (a + b) - b = a

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

1
Z = (a + b) - a = b

回頭和程式對比，可以發現 Y 相當於 b 變數，Z 相當於 a 變數。

使用位元運算並不好去理解為什麼這樣子做就可以達到交換的目的，首先要瞭解以下三點：

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

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

1
2
3
4
假設 X、Y 和 Z 為未知數，a 和 b 為已知數，已知：
X = a ^ b
Y = X ^ b
Z = X ^ Y

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

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

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

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

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

延伸閱讀

面試常見程式考題