Just My Life & My Work

[C++] 交換變數值-兩個變數VS三個變數 (Swap Two Variables)

2011 年 04 月 09 日

交換變數的值通常我們都會使用三個變數，但卻有方法可以只使用兩個變數，這到底是怎麼辦到的呢？

void swap3(int& n1, int& n2){
 int temp=n1;
 n1=n2;
 n2=temp;
}

以上是正常程式設計師會寫的SWAP函式，正常來說會使用temp變數來交換兩個值，接下來我們來看只用兩個變數就能交換值的方法：

void swap2(int& n1, int& n2){
 n1^=n2^=n1^=n2;
}

這是使用XOR來交換值，因為具有可逆性，所以A與B值取XOR之後，再對A(B)取XOR，就可以變回B(A)值。上學期的高等演算法課程作業使用過，當時是為了做字典的hashing table，需要以字母來XOR編碼。以上講解理論有點複雜，那我們來看個例子：

a=0010, b=0100
1. a^=b : 0010 =>a
———^0100 =>b
———–0110 =>a
2. b^=a : 0110 =>a
———^0100 =>b
———–0010 =>b (原a 的值)
3. a^=b : 0010 =>b
———^0110 =>a
———–0100 =>a (原b的值)

我們可以觀察到兩數做XOR的真值表為：

A     B     A xor B
0     0     0
0     1     1
1     0     1
1     1     0

根據上頭得舉例，程式可以寫得比較清楚如下：

void swap2(int& n1, int& n2){
 n1^=n2;
 n2^=n1;
 n1^=n2;
}

接著就是比較執行時間啦～既然它為了節省一個變數，那在效率上是否會變差呢？答案是肯定的！因為它多了三次XOR運算。

for(int i=0;i<100000000;i++)
 swap3(a,b);
 }

執行結果：

0.69315875740905497000
請按任意鍵繼續 . . .

 for(int i=0;i<100000000;i++)
 swap2(a,b);
 }

執行結果：

1.24816423478402520000
請按任意鍵繼續 . . .

參考：如何交換兩個變數，而不動用第三個變數？

分類：

C&C++, 教學

2 Comments

Comments on: "[C++] 交換變數值-兩個變數VS三個變數 (Swap Two Variables)" (2)

  2. 未知 的大頭貼
    交換變數值-兩個變數VS三個變數 (Swap Two Variables) « 逍遙文工作室 said:
    2011 年 06 月 14 日 於 10:56:44

    […] 好幾個月前很好奇交換變數的方法，寫了交換變數值-兩個變數VS三個變數，今日直接來看組合語言如何交換變數值，就以兩種方式來探討。 […]

    讚

回覆給交換變數值-兩個變數VS三個變數 (Swap Two Variables) « 逍遙文工作室 取消回覆

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料。

標籤雲