不要使用第三個變數,交換二個變數的值


int a = 3, b = 5;
a = (b = (a ^ b) ^ b) ^ (a ^ b);

十幾天前,前去一家公司面試,在附帶的小測驗中,見到了這個題目:要交換二個變數的值,但不要使用第三個變數。以上一句是解答。

在以上解答中,有二個基本概念:一是一個數值對另一個數值做『互斥或』 (exclusive-or) 二次,可以還原為原有的數值,即 a ^ b ^ b = a 與 a ^ a ^ b = b ;第二個概念是 C 語言的每一則式子都有傳回值,而且『指定』運算 (assignment) 也有傳回值。

雖然孰悉 C 語言的人經常都喜歡思考一連串的符號與運算之間的細節,然而對許多朋友來說,即使看著解答,也很難調整清楚想法。

傳統的 programming ,被稱為 Value-level Programming ,其重點是在於變數與值二者不同。因此,當我們看到一則 C 語言式子寫 a = a ^ b ,要能理解『變數 a 』與『內容 a 』二回事。

展開

我們可以用『不可塗改的變數』 (immutable variable) 之因素,將程式展開為幾個步驟,以便於理解。


int a = 3, b = 5;
a_b = a ^ b; //(1)
b_1 = a_b ^ b; //(2)
a_1 = b_1 ^ a_b; //(3)

根據以上程式, a_1 能展開如下:


a_1
=> b_1 ^ a_b {因為 (3) }
=> (a_b ^ b) ^ a_b {因為 (2) }
=> ((a ^ b) ^ b) ^ a_b {因為 (1) }
=> ((a ^ b) ^ b) ^ (a ^ b) {因為 (1) }
=> a ^ (a ^ b) {因為 a ^ b ^ b = a}
=> b {因為 a ^ a ^ b = b}

並且 b_1 能展開如下:


b_1
=> a_b ^ b {因為 (2) }
=> (a ^ b) ^ b {因為 (1) }
=> a {因為 a ^ b ^ b = a}

另一個解答

假如用函數語言,則更簡單:

以 Lambda Expression 來寫,是 λ x . λ y . (y, x)

以 Haskell 來寫,是

swap :: (Int, Int) -> (Int, Int)
swap (x, y) = (y, x)

以 Erlang 來寫,是

swap({x, y}) -> {y, x}.

而當然,要計較有沒有使用到第三個變數,在 C 語言與在函數語言的底蘊,是彼此根本不同。 C 語言的人仍然可以刁鑽地說:使用到一個函式,等同於使用到第三個變數。

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Problem。將永久鏈結加入書籤。