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

小开

人们经常引用第二种做法，认为这是一种“聪明”的做法。事实上，它很可能比较慢，因为它模糊了程序员交换两个变量的明确目标。这意味着编译器不能优化它来使用实际的汇编器操作来交换。它还假定能够对对象执行按位 xor 操作。

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

这个维基百科部分很好地解释了这些问题: Http://en.wikipedia.org/wiki/xor_swap_algorithm#reasons_for_avoidance_in_practice

小开

第一个更快，因为 xor 之类的按位操作通常很难为读者可视化。

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

小开

要真正了解它，唯一的方法就是测试它，答案甚至可能因所在的编译器和平台而异。现在的编译器都是真的，它们很擅长优化代码，除非你能证明你的方法真的比编译器更快，否则你永远不应该试图比编译器更聪明。

说到这里，你最好有一个非常好的理由选择2号而不是1号。1中的代码更具可读性，因此应该总是首先选择它。只有切换到 # 2，如果你能证明你的需要做出改变，如果你做到了-注释它，以解释发生了什么，为什么你这样做，非明显的方式。

作为一个轶事，我与几个人工作，爱过早优化，它使真正可怕的，不可维护的代码。我也愿意打赌，他们往往是在搬起石头砸自己的脚，因为他们已经削弱了编译器通过非直接的方式编写代码来优化代码的能力。

小开

最佳答案

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

更多关于维基页面的信息: 异或交换算法

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

小开

如果你可以使用一些内联汇编并执行以下操作(psuedo 汇编程序) :

PUSH A
A=B
POP B

您将保存大量的参数传递和堆栈修复代码等。

小开

你正在优化错误的东西，这两个应该是如此之快，你将不得不运行它们数十亿次，只是得到任何可测量的差异。

而且几乎任何东西都会对你的性能产生更大的影响，例如，如果你交换的值在内存中接近你触摸的最后一个值，那么它们在处理器缓存中就是 lily，否则你将不得不访问内存——这比你在处理器中的任何操作都要慢几个数量级。

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

小开

如上所述，要回答你的问题，需要深入挖掘这段代码将运行的特定 CPU 的指令计时，因此需要我对系统中缓存的状态和编译器发出的汇编代码做出一系列假设。从理解您选择的处理器实际上是如何工作的角度来看，这将是一个有趣而有用的练习，但在现实世界中，这种差异将是微不足道的。

小开

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

因为它是一个胖轴快排，所以 XOR 版本的速度可能来自于使数组的大部分相同。我尝试了第三个版本的交换，这是最容易理解的，它有同样的时间作为单一的临时版本。


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

[I just put an if statements around each swap, so it won't try to swap with itself, and the XOR now takes the same time as the others (0.6 sec)]

小开

在现代处理器上，对大型数组进行排序时可以使用以下命令，并且不会看到速度上的差异:

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

你问题中真正重要的部分是“为什么?”？一部分。现在，回溯到20年前的8086天，上面这些将是一个真正的性能杀手，但是在最新的奔腾上，它将是一个比赛的速度明智的你发布的两个。

原因纯粹是内存，与 CPU 无关。

与内存速度相比，CPU 速度已经大幅提高。访问内存已经成为影响应用程序性能的主要瓶颈。所有的交换算法都将花费大部分时间等待从内存中取出数据。现代操作系统可以有5个级别的内存:

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

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

因此，优化交换方法实际上是毫无意义的——如果它只被调用了几次，那么由于调用次数较少，任何低效率都会被隐藏起来; 如果它被调用了很多次，那么由于缓存丢失的次数(CPU 需要从 L2(1个周期)、 L3(10个周期)、 RAM (100个周期)、 HD (!)中获取数据) ，任何低效率都会被隐藏起来.

您真正需要做的是查看调用交换方法的算法。这不是一个无关紧要的练习。虽然 Big-O 符号很有用，但是对于小 n，O (n)可能比 O (log n)快得多(我相信 CodingHorror 上有一篇关于这方面的文章)此外，许多算法都存在代码执行不必要操作的退化情况(对接近有序的数据使用 qsort 可能比使用提前退出检查的冒泡排序慢)。所以，你需要分析你的算法和它所使用的数据。

这就引出了如何分析代码。分析器是有用的，但是您需要知道如何解释结果。永远不要使用单次运行来收集结果，总是在许多执行中取得平均结果-因为您的测试应用程序可能已经在操作系统中途被分页到硬盘。总是配置文件发布，优化构建，配置调试代码是毫无意义的。

至于最初的问题——哪个更快？这就像通过观察后视镜的尺寸和形状来判断法拉利是否比兰博基尼快。

小开

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

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

小开

关于@Harry: 永远不要以宏的形式实现函数，原因如下:

类型安全。没有类型安全。以下代码只在编译时生成警告，但在运行时失败:
```
float a=1.5f,b=4.2f;
swap (a,b);
```
模板化函数的类型总是正确的(为什么不将警告视为错误?)。

编辑: 由于 C 语言中没有模板，因此需要为每种类型编写一个单独的交换，或者使用一些蹩脚的内存访问。
这是一个文本替换。下面的代码在运行时失败(这次没有编译器警告) :
```
int a=1,temp=3;
swap (a,temp);
```
It's not a function. So, it can't be used as an argument to something like qsort.
Compilers are clever. I mean really clever. Made by really clever people. They can do inlining of functions. Even at link time (which is even more clever). Don't forget that inlining increases code size. Big code means more chance of cache miss when fetching instructions, which means slower code.
Side effects. Macros have side effects! Consider:
```
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++]);
```

Macros: Just say no!

EDIT: This is why I prefer to define macro names in UPPERCASE so that they stand out in the code as a warning to use with care.

EDIT2: To answer Leahn Novash's comment:

Suppose we have a non-inlined function, f, that is converted by the compiler into a sequence of bytes then we can define the number of bytes thus:

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

它可能会生成4字节指令:

mov eax,[ecx + offsetof (m_value)]

也就是四个字节。调用指令是五个字节。因此，可以节省整体尺寸。如果函数更复杂，比如索引器(“ 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 上编译此代码，那么结果会有很大的不同。

如果你有一个特定的目标，然后只是尝试他们两个，看看生成的代码或配置文件，您的应用程序与两种方法，看看哪一个实际上是更快的平台。

小开

所有排名靠前的答案实际上并不是决定性的“事实”... ... 它们只是人们的猜测！

您可以确定哪些代码执行较少的程序集指令，因为您可以查看编译器生成的输出程序集，并查看哪些代码执行较少的程序集指令！

下面是我用标志“ gcc-std = c99-S-O3 lookAtAsmOutput.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);
}

交换传统()的 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

总装产出摘要:
交换 _ 传统()需要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 努力通过指令管道并行执行指令。在 XOR 技术中，每个操作的输入取决于前一个操作的结果，因此它们必须严格按顺序执行。如果非常关注效率，建议在目标体系结构上测试异或技术和临时变量交换的速度。查看给你了解更多信息。

编辑: 方法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;