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。
說明
使用位元運算並不好去理解為什麼這樣子做就可以達到交換的目的,就算是寫例子也還是不瞭解,這邊數學的角度去解釋,應該可以幫助思考,首先瞭解以下三點:
- 首先我們知道XOR的定義是:有且僅有一個為真,換句話說就是,相同的為0,不同的為1。
- 有了以上的定義,我們假設一變數N,當N ^ N的時候,由於每個位元必定相同,所以結果一定是0。
- 而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法就能理解交換之原理,當然也可以直接背起來就好。