从汇编角度与你分析「为什么不要用异或来交换两个数」

❝

作者：宫水三叶。现微软工程师（Java 后端方向），退役 OIer。

更多面试算法相关内容可点击「这里」关注 ~

转载需关注公众号联系开白名单 ~ 

交换两个的方式有很多种。

最经典的借助一个临时变量，或是通过“异或”来是实现。

当然还有 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中（写）

简单的三行“异或”，居然需要转换成这么多条汇编指令。

上面我们说到「异或方案除了需要三次异或运算以外，还需要六次读和三次写，但现代编译器已经帮我们优化到了两读三写。」

但即使如此，「“异或”仍然要比借助临时变量的方案要慢」。

所以不要觉得使用临时变量少的方案必然更好，更不要觉得代码少的，纯运算的解决方案会更优。