為什么不要用異或來交換兩個數

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

前言

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

最經典的借助一個臨時變量，或是通過“異或”來是實現。

當然還有 Python 中優雅的 a, b = b, a 。

Python 的這種不借助臨時變量實現交換實際是巧妙的利用了“操作棧”，屬于語言層面上的特性技巧，不在我們的討論范圍。

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

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

奇怪的“技巧”

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

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

而是使用如下的“異或”來實現:

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

而這種“技巧”無論是在官方提供的解決方案還是網友的都出現過。

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

但其實這僅僅是實現“兩數交換”這一簡單功能。

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

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

“異或”意味著高效嗎

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

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;
}

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

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

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

從內存的角度

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

所以會增加大概 4 個字節的內存。

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

從 CPU 的角度

通常一個變量會有創建成本和銷毀成本。

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

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

“初步結論”

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

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

真實的情況

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

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

匯編對比

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

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

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

所得到的匯編如下：

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

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

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

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

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

所得到的匯編如下：

movl        b, %eax       ;將b從內存載入寄存器eax（讀）
movl        a, %ecx       ;將a從內存載入寄存器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的值存入到內存b中（寫）
xorl        %eax, %eax    ;將eax置0：設置返回值
movl        %edx, a       ;將edx的值存入到內存a中（寫）

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

到此，相信大家對“為什么不要用異或來交換兩個數”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！