algorithm - 交换整数效率

Question

简单地说，

X = Integer
Y = Another Integer

Z ( If used ,Integer Temp )

什么是最有效的方法？

方法一:

Z = X
X = Y
Y = Z

方法二:

X ^= Y
Y ^= X
X ^= Y

---

编辑 I [ 程序集 View ]

方法一:

MOV  
MOV  
MOV

方法二:

TEST ( AND )  
JZ  
XOR  
XOR  
XOR

注释:

• MOV 比 XOR
慢
• TEST , JZ 用于XOR Equality Safe
• `我使用额外寄存器的方法

Answer 1

在大多数情况下，使用临时变量(通常是汇编级别的寄存器)是最佳选择，也是编译器倾向于生成的变量。

In most practical scenarios, the trivial swap algorithm using a temporary register is more efficient. Limited situations in which XOR swapping may be practical include: On a processor where the instruction set encoding permits the XOR swap to be encoded in a smaller number of bytes; In a region with high register pressure, it may allow the register allocator to avoid spilling a register. In microcontrollers where available RAM is very limited. Because these situations are rare, most optimizing compilers do not generate XOR swap code.

http://en.wikipedia.org/wiki/XOR_swap_algorithm

此外，如果将相同的变量作为两个参数传递，您的异或交换实现也会失败。正确的实现(来自同一个链接)是:

void xorSwap (int *x, int *y) {
     if (x != y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

Note that the code does not swap the integers passed immediately, but first checks if their addresses are distinct. This is because, if the addresses are equal, the algorithm will fold to a triple *x ^= *x resulting in zero.