為什么不要用異或來交換兩個數(shù)

本篇內(nèi)容主要講解“為什么不要用異或來交換兩個數(shù)”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“為什么不要用異或來交換兩個數(shù)”吧!

成都創(chuàng)新互聯(lián)公司堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站建設(shè)、做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的北辰網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

前言

交換兩個的方式有很多種。

最經(jīng)典的借助一個臨時變量，或是通過“異或”來是實現(xiàn)。

當(dāng)然還有 Python 中優(yōu)雅的 a, b = b, a 。

Python 的這種不借助臨時變量實現(xiàn)交換實際是巧妙的利用了“操作?！保瑢儆谡Z言層面上的特性技巧，不在我們的討論范圍。

今天就來說一下，為什么我建議使用臨時變量來實現(xiàn)交換，而不是使用“異或”。

盡管這看起來并不“高級”。

奇怪的“技巧”

如果你是一個偶爾會上 LeetCode 刷題的人，你或許會看到過一些解決方案。

它們在涉及兩數(shù)交換的時候，并沒有采用常規(guī)的“借助一個臨時變量”的做法。

而是使用如下的“異或”來實現(xiàn):

a = a ^ b;
b = a ^ b;
a = a ^ b;

而這種“技巧”無論是在官方提供的解決方案還是網(wǎng)友的都出現(xiàn)過。

在不了解這種做法的時候，極有可能就因為這幾行代碼直接勸退了，整個解決方案的思路都懶得看了。

但其實這僅僅是實現(xiàn)“兩數(shù)交換”這一簡單功能。

而在我初步了解到這種做法的原理之后，有一種數(shù)學(xué)家跑來做算法題的感覺，這種做法確實在不借助臨時變量的前提下，很巧妙的利用了數(shù)學(xué)原理交換了兩個數(shù)。

但是這對計算機來說，真的比借助變量來得高效嗎？

“異或”意味著高效嗎

一段解決變量的代碼和一段“異或”的代碼放在一起，可能直觀印象會覺得不借助變量的“異或”會更高效：

public static void main(String[] args) {
    int a = 1;
    int b = 99;

    // 借助臨時變量    int c = a;
    a = b;
    b = c;

    // “異或”    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

確實，多開一個臨時變量就需要往“棧幀”的本地變量表中增加一個變量，但也僅此而已。

即使我們交換的不是兩個數(shù)，而是兩個大對象，通過臨時變量實現(xiàn)交換也是多增加一個指針變量而已，并不會在堆上創(chuàng)建多一個對象。

多這么一個的臨時變量，會有多大影響？我們嘗試從內(nèi)存和 CPU（執(zhí)行時間）兩個角度來定性分析。

從內(nèi)存的角度

由于增加的這個變量只是“棧幀”的本地變量表中的一個變量。

所以會增加大概 4 個字節(jié)的內(nèi)存。

而這個內(nèi)存相對于整個“棧幀”大小來說，基本可以忽略。

從 CPU 的角度

通常一個變量會有創(chuàng)建成本和銷毀成本。

由于這個臨時變量只是“棧幀”的本地變量表上的一個記錄，會隨著“棧幀”的彈出而整體銷毀，所以首先沒有增加額外的銷毀成本。

至于變量的創(chuàng)建，由于這個變量只是棧上分配，整個創(chuàng)建過程幾乎是納秒級別，幾乎不會對執(zhí)行時間造成任何影響，也就是創(chuàng)建成本是完全可忽略的。

“初步結(jié)論”

根據(jù)以上的大致分析，可能會得出“異或”方案和借助臨時變量的方案效率大致相同，或者“異或”方案比臨時變量方案要略微高效的結(jié)論。

「但事實上，真實的情況和我們的“初步分析”幾乎相反?！?/strong>

真實的情況

先說結(jié)論，借助臨時變量的方案要比使用“異或”快得多。

為什么“異或”會更慢？因為在借助臨時變量的方案中，只涉及兩次的內(nèi)存讀寫，而在“異或”方案中除了要執(zhí)行三次“異或”運算以外，我們還需要進行六次讀和三次寫（理論上）。

匯編對比

要從本質(zhì)上回答這個問題，需要我們對兩種方案的代碼所編譯出來的匯編指令進行分析。

對于以下的借助變量交換的方案：

int c = a;
a = b;
b = c;

所得到的匯編如下：

movl        b, %eax      ;將b從內(nèi)存載入到寄存器eax（讀）
movl        a, %edx      ;將a從內(nèi)存載入到寄存器edx（讀）
movl        %eax, a      ;將eax的內(nèi)容存入到內(nèi)存a中（寫）
xorl        %eax, %eax  ;將eax置0：設(shè)置返回值
movl        %edx, b      ;將edx的內(nèi)容存入到內(nèi)存b中（寫）

對應(yīng)的匯編指令還是比較清晰：要參與運算的變量首先要從內(nèi)存載入到寄存器中，所以要將兩個變量交換只需按相反的順序再存入到內(nèi)存中就可以了。

可以看到這個「借助臨時變量的方案實際上只包含四個內(nèi)存與寄存器之間交換數(shù)據(jù)的指令，兩讀兩寫」。

再看看使用“異或”的方案：

a ^= b;
b ^= a;
a ^= b;

所得到的匯編如下：

movl        b, %eax       ;將b從內(nèi)存載入寄存器eax（讀）
movl        a, %ecx       ;將a從內(nèi)存載入寄存器ecx（讀）
movl        %eax, %edx    ;將eax的值保存到edx中（寫）
xorl        %ecx, %edx    ;ecx與edx異或
xorl        %edx, %eax    ;edx與eax異或
xorl        %eax, %edx    ;eax與edx異或
movl        %eax, b       ;將eax的值存入到內(nèi)存b中（寫）
xorl        %eax, %eax    ;將eax置0：設(shè)置返回值
movl        %edx, a       ;將edx的值存入到內(nèi)存a中（寫）

簡單的三行“異或”，居然需要轉(zhuǎn)換成這么多條匯編指令。

到此，相信大家對“為什么不要用異或來交換兩個數(shù)”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！