close

原文出處：kejames 學習筆記本--【動腦時間】要如何交換兩個變數，而不動用第三個變數?
http://www.cnblogs.com/kejames/archive/2007/09/19/898333.html

Q : 如何交換兩個變數，而不動用第三個變數?
有興趣的人可以想想...
從http://www.cnblogs.com/oomusou/archive/2007/09/09/887337.html看來的文章，寫的真的很好。

以下為轉載資料。
---
這是我一個網友問我的，他說他同學去工作面試時所考的題目，一般我們要交換兩個變數會這樣寫。
C++

/**//* 
(C) OOMusou 2007 http://oomusou.cnblogs.com

Filename    : swap_normal.cpp
Compiler    : Visual C++ 8.0 / BCB 6.0 / gcc 3.4.2 / ISO C++
Description : Demo how to swap 2 variable in C++
Release     : 09/08/2007 1.0
*/
#include <iostream>

using namespace std;

void swap(int& x, int& y) {
  int tmp = x;
  x = y;
  y = tmp;
}

int main() {
  int x = 1;
  int y = 2;
 
  cout << "x = " << x << ", y = " << y << endl;
  swap(x,y);
  cout << "x = " << x << ", y = " << y << endl;
}


執行結果

x = 1, y = 2
x = 2, y = 1



假如你也這樣寫，表是你是一個很正常的coder，:D，但這樣寫還必須多一個變數tmp當暫存，能否不需tmp也能交換呢?

神奇的xor
xor全名為exclusive or，其truth table為
x y x xor y
0 0 0
0 1 1
1 0 1
1 1 0

簡單的說，就是當x和y不同時，其質為true。但xor最神奇的，是它具可逆性，這是其他and、or、or等邏輯做不到的。
x xor y = z
z xor y = x
z xor x = y


所以z可以看成是一個暫存變數，只要在xor x回來就可以得到y，或xor y回來等於x。

所以若要兩數交換，可以這樣寫。

x = x xor y
y = x xor y
x = x xor y


為什麼三次xor就可以呢?以上的code原本應該寫成

z = x xor y
y = z xor y
x = z xor y (此時y已經等於x，所以相當於z xor x)


但這樣寫多了一個變數z，且x在過程中已經不會用到了，所以將變數z放在x中，可以省下一個變數，所以就變成了

x = x xor y
y = x xor y
x = x xor y


一切的神奇都歸因於xor具有可逆性。

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 Cliff 的頭像
    Cliff

    Cliff的部落格

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

    E-mail轉寄