如何在程式中不使用暫存變數交換兩個變數(適用於 Java 與 C/C++ 等語言)

這裡說明如何在程式中不使用暫存變數(temporary variable)交換兩個變數,這個問題也是面試時常問的問題。


在 C/C++ 與 Java 等程式中,如果要將兩個變數所儲存的值交換,最簡單的方式就是使用一個暫存變數,例如若要將 ab 兩個變數交換,則可使用:
tmp = a
a = b
b = tmp
其中 tmp 就是一個暫存變數,而這樣的方式也是最簡單、最直覺會想到的方法。但這裡會多使用到一個暫存變數,是否有辦法不要使用額外的 tmp 變數,就將 ab 交換呢?這個問題是許多程式設計面試時會問到的問題,以下有三種解決方法。

第一種方式是使用 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 運算的方式來交換兩個變數,直接從表面上看不是很好理解,我們可以使用一些簡單的數學運算來解釋,為了避免變數混淆,首先將 XOR 的三條運算改寫為:
x = a ^ b
y = x ^ b
z = x ^ y
然後透過簡單的數學代數運算,我們可以得到 y 的值為
y = (a ^ b) ^ b = a ^ b ^ b = a ^ (b ^ b) = a ^ 0 = az 的值為
z = (a ^ b) ^ a = a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b這樣就比較清楚了。

參考資料:Javarevisited
本站已經搬家了,欲查看最新的文章,請至 G. T. Wang 新網站