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法就能理解交換之原理,當然也可以直接背起來就好。

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()