最好的交换算法？

Question

我从我的一个朋友那里听说最好的交换算法是“(a^=b^=a^=b)”，其中a和b是要交换的两个整数。但是当我使用c语言应用它的时候，它导致了崩溃。你们这些优秀的人能解释一下可能的原因吗？请推荐最好的交换算法。谢谢！伙计们，我想知道坠机的原因。

Answer 1

这种交换技巧有时是危险的，我见过一个错误的快速排序程序使用这种交换产生错误的结果。但通常的交换会生成正确的程序。

在速度方面，如果我们使用tmp变量，编译器有时会生成更快的代码。

使用tmp = a; a = b; b = tmp;

Answer 2

a^=b^=a^=b;崩溃可能是因为它调用了可怕的未定义行为。它打破的规则是，它修改a两次，而不使用中间的序列点。可以通过插入一些序列点来修复它-例如，使用逗号运算符：

a ^= (b ^= a ^= b, b);`

或者将其分解为多个语句：

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

然而，对于交换变量来说，这通常仍然是一个糟糕的方法-其他几个答案和评论已经充分解释了原因。

Answer 3

参见http://en.wikipedia.org/wiki/Swap_(computer_science)。

使用临时变量会产生更多开销，但比XOR交换算法更稳定，并且并行计算使其比XOR交换更快。

有关使用临时变量进行交换的可靠实现，请参阅http://www.ibm.com/developerworks/linux/library/l-metaprog1.html的第一个代码示例。