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

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

前言

交換兩個(gè)的方式有很多種。

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

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

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

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

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

奇怪的“技巧”

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

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

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

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

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

在不了解這種做法的時(shí)候，極有可能就因?yàn)檫@幾行代碼直接勸退了，整個(gè)解決方案的思路都懶得看了。

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

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

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

“異或”意味著高效嗎

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

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

    // 借助臨時(shí)變量    int c = a;
    a = b;
    b = c;

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

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

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

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

從內(nèi)存的角度

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

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

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

從 CPU 的角度

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

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

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

“初步結(jié)論”

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

「但事實(shí)上，真實(shí)的情況和我們的“初步分析”幾乎相反。」

真實(shí)的情況

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

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

匯編對比

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

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

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

可以看到這個(gè)「借助臨時(shí)變量的方案實(shí)際上只包含四個(gè)內(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)換成這么多條匯編指令。

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