在 C 中交换值的最快方法是什么？

数字 2 经常被引用为“聪明”的方式。事实上，它很可能更慢，因为它掩盖了程序员的明确目标 - 交换两个变量。这意味着编译器无法对其进行优化以使用实际的汇编程序操作进行交换。它还假定能够对对象执行按位异或操作。

坚持第 1 点，它是最通用和最容易理解的交换，可以很容易地模板化/通用化。

这个维基百科部分很好地解释了这些问题：http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice

第一种速度更快，因为按位运算（如异或）通常很难为读者可视化。

当然，理解起来更快，这是最重要的部分;)

真正知道的唯一方法是测试它，答案甚至可能因您使用的编译器和平台而异。如今，现代编译器非常擅长优化代码，除非你能证明你的方式真的更快，否则你永远不应该试图超越编译器。

话虽如此，你最好有一个很好的理由选择#2而不是#1。#1 中的代码更具可读性，因此应始终首先选择。只有当你能证明你需要做出改变时，才切换到#2，如果你这样做了 - 评论它以解释发生了什么以及为什么你以不明显的方式这样做。

作为一个轶事，我和几个喜欢过早优化的人一起工作，这使得代码非常可怕，无法维护。我也敢打赌，他们经常搬起石头砸自己的脚，因为他们以一种非直接的方式编写代码，从而阻碍了编译器优化代码的能力。

如果 a 和 b 指向同一地址，则 XOR 方法将失败。第一个异或将清除两个变量指向的内存地址上的所有位，因此一旦函数返回 （*a == *b == 0），无论初始值如何。

在 Wiki 页面上的更多信息：XOR 交换算法

虽然不太可能出现这个问题，但我总是更喜欢使用保证有效的方法，而不是在意外时刻失败的聪明方法。

如果您可以使用一些内联汇编程序并执行以下操作（psuedo 汇编程序）：

PUSH A
A=B
POP B

您将节省大量参数传递和堆栈修复代码等。

你优化了错误的东西，这两者都应该如此之快，以至于你必须运行它们数十亿次才能获得任何可衡量的差异。

几乎任何事情都会对你的性能产生更大的影响，例如，如果你正在交换的值在内存中接近你触摸的最后一个值，它们就会在处理器缓存中，否则你将不得不访问内存 - 这比你在处理器内执行的任何操作都慢几个数量级。

无论如何，你的瓶颈更有可能是低效的算法或不适当的数据结构（或通信开销），而不是你如何交换数字。

如前所述，要回答您的问题，需要深入研究此代码将在其上运行的特定 CPU 的指令时序，因此需要我围绕系统中缓存的状态和编译器发出的汇编代码做出一系列假设。从了解您选择的处理器实际工作方式的角度来看，这将是一个有趣且有用的练习，但在现实世界中，差异可以忽略不计。

我只是将两个交换（作为宏）放在我一直在玩的手写的快速排序中。XOR版本（0.1秒）比带有临时变量的版本（0.6秒）快得多。然而，XOR确实破坏了数组中的数据（可能与Ant提到的地址相同）。

由于它是一个胖的枢轴快速排序，XOR 版本的速度可能是由于使数组的大部分相同。我尝试了最容易理解的第三个版本的交换，它与单个临时版本的时间相同。

acopy=a;
bcopy=b;
a=bcopy;
b=acopy;

[我只是在每个交换周围放置了一个 if 语句，因此它不会尝试与自身交换，并且 XOR 现在与其他 XOR 花费相同的时间（0.6 秒）]

在现代处理器上，在对大型数组进行排序时，可以使用以下方法，并且速度没有差异：

void swap (int *a, int *b)
{
  for (int i = 1 ; i ; i <<= 1)
  {
    if ((*a & i) != (*b & i))
    {
      *a ^= i;
      *b ^= i;
    }
  }
}

你的问题中真正重要的部分是“为什么？”部分。现在，回到 20 年前的 8086 天，上述内容将是一个真正的性能杀手，但在最新的 Pentium 上，这将是与您发布的两个相匹配的速度。

原因纯粹归结为内存，与CPU无关。

与内存速度相比，CPU 速度已经天文数字地上升了。访问内存已成为应用程序性能的主要瓶颈。所有交换算法都将花费大部分时间等待从内存中获取数据。现代操作系统最多可以有 5 个级别的内存：

• 缓存级别 1 - 以与 CPU 相同的速度运行，访问时间可以忽略不计，但很小
• 缓存级别 2 - 运行速度比 L1 慢一点，但更大，访问开销更大（通常，需要先将数据移动到 L1）
• 缓存级别 3 - （并非总是存在）通常位于 CPU 外部，速度较慢且大于 L2
• RAM - 主系统内存，通常实现一个管道，因此读取请求存在延迟（CPU 请求数据，消息发送到 RAM，RAM 获取数据，RAM 将数据发送到 CPU）
• 硬盘 - 当没有足够的RAM时，数据被分页到HD，这真的很慢，而不是真正在CPU的控制之下。

排序算法会使内存访问变得更糟，因为它们通常以非常无序的方式访问内存，从而产生从 L2、RAM 或 HD 获取数据的低效开销。

因此，优化交换方法真的毫无意义 - 如果它只被调用几次，那么由于调用次数少，任何低效率都会被隐藏起来，如果它被调用了很多，那么任何低效率都会被隐藏，因为缓存未命中的数量（其中 CPU 需要从 L2（1 个周期）获取数据）， L3（10 个周期）、RAM（100 个周期）、HD（！

您真正需要做的是查看调用 swap 方法的算法。这不是一项微不足道的工作。尽管 Big-O 表示法很有用，但对于小 n，O（n） 可能比 O（log n） 快得多。此外，许多算法都存在退化情况，即代码执行的操作超出了必要的范围（对几乎有序的数据使用 qsort 可能比使用提前检查的冒泡排序慢）。因此，您需要分析您的算法及其使用的数据。

这就引出了如何分析代码。探查器很有用，但您确实需要知道如何解释结果。永远不要使用单次运行来收集结果，始终在多次执行中平均结果 - 因为测试应用程序可能在中途作系统分页到硬盘。总是分析发布、优化构建、分析调试代码是没有意义的。

至于最初的问题——哪个更快？- 这就像试图通过观察后视镜的大小和形状来弄清楚法拉利是否比兰布尔吉尼更快。

对于那些偶然发现这个问题并决定使用 XOR 方法的人。应考虑内联函数或使用宏来避免函数调用的开销：

#define swap(a, b)   \
do {                 \
    int temp = a;    \
    a = b;           \
    b = temp;        \
} while(0)

关于@Harry： 切勿将函数实现为宏，原因如下：

1. 类型安全。没有。以下代码仅在编译时生成警告，但在运行时失败：

   float a=1.5f,b=4.2f;
   swap (a,b);
   

   模板化函数将始终具有正确的类型（为什么不将警告视为错误？

   编辑：由于 C 中没有模板，因此您需要为每种类型编写单独的交换或使用一些 hacky 内存访问。

2. 这是一个文本替换。以下操作在运行时失败（这次没有编译器警告）：

   int a=1,temp=3;
   swap (a,temp);
   

3. 它不是一个函数。因此，它不能用作 qsort 之类的参数。

4. 编译器很聪明。我的意思是真的很聪明。由非常聪明的人制作。它们可以对函数进行内联。即使在链接时（这更聪明）。不要忘记内联会增加代码大小。大代码意味着在获取指令时缓存未命中的机会更大，这意味着代码速度较慢。

5. 副作用。宏有副作用！考虑：

   int &f1 ();
   int &f2 ();
   void func ()
   {
     swap (f1 (), f2 ());
   }
   

   在这里，f1 和 f2 将被调用两次。

   编辑：具有令人讨厌的副作用的C版本：

   int a[10], b[10], i=0, j=0;
   swap (a[i++], b[j++]);
   

宏：说不就行了！

编辑：这就是为什么我更喜欢以大写字母定义宏名称，以便它们在代码中脱颖而出，作为谨慎使用的警告。

编辑2：回答Leahn Novash的评论：

假设我们有一个非内联函数 f，它被编译器转换为字节序列，那么我们可以定义字节数，这样：

bytes = C(p) + C(f)

其中 C（） 给出生成的字节数，C（f） 是函数的字节数，C（p） 是“内务”代码的字节，编译器添加到函数的前导码和后半段（创建和销毁函数的堆栈帧等）。现在，调用函数 f 需要 C（c） 字节。如果函数被调用 n 次，则总代码大小为：

size = C(p) + C(f) + n.C(c)

现在让我们内联函数。C（p） 是函数的“内务处理”，变为零，因为该函数可以使用调用方的堆栈帧。C（c） 也为零，因为现在没有调用操作码。但是，只要有调用，f 就会被复制。因此，现在的总代码大小为：

size = n.C(f)

现在，如果 C（f） 小于 C（c），则整体可执行文件大小将减小。但是，如果 C（f） 大于 C（c），则代码大小将会增加。如果 C（f） 和 C（c） 相似，那么您还需要考虑 C（p）。

那么，C（f） 和 C（c） 产生多少字节。好吧，最简单的 C++ 函数是 getter：

void GetValue () { return m_value; }

这可能会生成四字节指令：

mov eax,[ecx + offsetof (m_value)]

这是四个字节。调用构造为 5 个字节。因此，整体尺寸节省。如果函数更复杂，例如索引器（“return m_value [index];”）或计算（“return m_value_a + m_value_b;”），则代码会更大。

除非你必须，否则我不会用指针来做。由于指针混叠的可能性，编译器无法很好地优化它们（尽管如果您可以保证指针指向非重叠位置，GCC 至少具有扩展来优化这一点）。

我根本不会用函数来做，因为这是一个非常简单的操作，而且函数调用开销很大。

最好的方法是使用宏，如果原始速度和优化的可能性是您需要的。在 GCC 中，您可以使用内置版本来制作适用于任何内置类型的灵活版本。typeof()

像这样的东西：

#define swap(a,b) \
  do { \
    typeof(a) temp; \
    temp = a; \
    a = b; \
    b = temp; \
  } while (0)

...    
{
  int a, b;
  swap(a, b);
  unsigned char x, y;
  swap(x, y);                 /* works with any type */
}

使用其他编译器时，或者如果需要严格遵守标准 C89/99，则必须为每种类型创建单独的宏。

一个好的编译器会在给定上下文的情况下尽可能积极地优化它，如果使用局部/全局变量作为参数进行调用。

在我看来，像这样的本地优化应该只考虑与平台密切相关。如果您在 16 位 uC 编译器或以 x64 为目标的 gcc 上编译它，这将产生巨大的差异。

如果您有一个特定的目标，那么只需尝试这两种方法并查看生成的 asm 代码或使用这两种方法分析您的应用程序，看看哪种方法在您的平台上实际上更快。

所有最受好评的答案实际上都不是确定的“事实”......他们是投机的人！

您可以明确地知道哪些代码需要较少的汇编指令来执行，因为您可以查看编译器生成的输出程序集，并查看哪些代码在较少的汇编指令中执行！

这是我用标志“gcc -std=c99 -S -O3 lookingAtAsmOutput.c”编译的 c 代码：

#include <stdio.h>
#include <stdlib.h>

void swap_traditional(int * restrict a, int * restrict b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void swap_xor(int * restrict a, int * restrict b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

int main() {
    int a = 5;
    int b = 6;
    swap_traditional(&a,&b);
    swap_xor(&a,&b);
}

swap_traditional（） 的 ASM 输出>>> 11 条<<<指令（不包括 “leave”、“ret”、“size”）：

.globl swap_traditional
    .type   swap_traditional, @function
swap_traditional:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %ecx
    pushl   %ebx
    movl    (%edx), %ebx
    movl    (%ecx), %eax
    movl    %ebx, (%ecx)
    movl    %eax, (%edx)
    popl    %ebx
    popl    %ebp
    ret
    .size   swap_traditional, .-swap_traditional
    .p2align 4,,15

swap_xor（） 的 ASM 输出采用>>> 11 条<<<指令，不包括 “leave” 和 “ret”：

.globl swap_xor
    .type   swap_xor, @function
swap_xor:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %ecx
    movl    12(%ebp), %edx
    movl    (%ecx), %eax
    xorl    (%edx), %eax
    movl    %eax, (%ecx)
    xorl    (%edx), %eax
    xorl    %eax, (%ecx)
    movl    %eax, (%edx)
    popl    %ebp
    ret
    .size   swap_xor, .-swap_xor
    .p2align 4,,15

程序集输出摘要：
swap_traditional（） 需要 11 条指令 swap_xor（） 需要 11 条指令

结论：
两种方法都使用相同数量的指令来执行，因此在此硬件平台上的速度大致相同。

经验教训：
当你有小代码片段时，查看 asm 输出有助于快速迭代你的代码并提出最快（即最少指令）的代码。而且，即使您不必为每次代码更改运行程序，也可以节省时间。只需在最后使用探查器运行代码更改，即可显示代码更改速度更快。

对于需要速度的繁重 DSP 代码，我经常使用这种方法。

如果您的编译器支持内联汇编程序，并且您的目标是 32 位 x86，那么 XCHG 指令可能是执行此操作的最佳方法......如果你真的那么在乎性能。

下面是适用于 MSVC++ 的方法：

#include <stdio.h>

#define exchange(a,b)   __asm mov eax, a \
                        __asm xchg eax, b \
                        __asm mov a, eax               

int main(int arg, char** argv)
{
    int a = 1, b = 2;
    printf("%d %d --> ", a, b);
    exchange(a,b)
    printf("%d %d\r\n", a, b);
    return 0;
}

void swap(int* a, int* b)
{
    *a = (*b - *a) + (*b = *a);
}

我的 C 有点生疏，所以我希望我得到正确的 * :)

另一种美丽的方式。

#define Swap( a, b ) (a)^=(b)^=(a)^=(b)

优势

无需函数调用，方便使用。

缺点：

当两个输入都是相同的变量时，此操作将失败。它只能用于整数变量。

从来不理解对宏的憎恨。如果使用得当，它们可以使代码更加紧凑和可读。我相信大多数程序员都知道应该谨慎使用宏，重要的是明确特定调用是宏而不是函数调用（全部大写）。如果是问题的持续根源，也许编程不适合您。SWAP(a++, b++);

诚然，xor 技巧在你看到它的前 5000 次很巧妙，但它真正所做的只是以牺牲可靠性为代价来节省一个临时的。查看上面生成的程序集，它保存了一个寄存器，但创建了依赖项。另外，我不推荐 xchg，因为它有一个隐含的锁前缀。

最终，我们都来到了同一个地方，在浪费了无数个小时之后，我们最聪明的代码导致了非生产性的优化和调试 - 保持简单。

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

void swap(size_t esize, void* a, void* b)
{
    char* x = (char*) a;
    char* y = (char*) b;
    char* z = x + esize;

    for ( ; x < z; x++, y++ )
        SWAP(char, *x, *y);
}

对于现代 CPU 架构，方法 1 会比方法 2 更快，也具有更高的可读性。

在现代 CPU 架构上，XOR 技术比使用临时变量进行交换要慢得多。原因之一是现代 CPU 努力通过指令管道并行执行指令。在异或技术中，每个操作的输入都取决于前一个操作的结果，因此它们必须严格按顺序执行。如果效率非常受关注，建议在目标架构上测试异或技术和临时变量交换的速度。查看此处了解更多信息。

---

编辑：方法 2 是一种就地交换的方法（即不使用额外的变量）。为了完成这个问题，我将使用 添加另一个就地交换。+/-

void swap(int* a, int* b)
{
    if (a != b) // important to handle a/b share the same reference
    {
        *a = *a+*b;
        *b = *a-*b;
        *a = *a-*b;
    }
}

下面的代码段将执行相同的操作。此代码段是优化的编程方式，因为它不使用任何第三个变量。

  x = x ^ y;
  y = x ^ y;
  x = x ^ y;

x=x+y-（y=x）;

float x; cout << "X:"; cin >> x;
float y; cout << "Y:" ; cin >> y;

cout << "---------------------" << endl;
cout << "X=" << x << ", Y=" << y << endl;
x=x+y-(y=x);
cout << "X=" << x << ", Y=" << y << endl;