在不使用第三个变量的情况下交换两个变量值

Question

在不使用第三个变量的情况下交换两个变量值在采访中提出的一个非常棘手的问题。交换两个变量的值，如a=10和b=15。通常要交换两个变量值，我们需要第三个变量，如：temp=a;a=b;b=temp;现在的要求是，在不使用第三个变量的情况下交换两个变量的值。

Answer 1

使用xor交换算法

void xorSwap (int* x, int* y) {
    if (x != y) { //ensure that memory locations are different
       *x ^= *y;
       *y ^= *x;
       *x ^= *y;
    }}

为什么要测试？

测试是为了确保x和y具有不同的内存位置（而不是不同的值）。这是因为(p xor p) = 0如果x和y共享相同的内存位置，当一个设置为0时，两者都设置为0.当* x和* y都为0时，* x和* y上的所有其他xor操作将相等0（因为它们是相同的），这意味着该函数将* x和* y都设置为0。

如果它们具有相同的值但不是相同的内存位置，则一切都按预期工作

*x = 0011*y = 0011//Note, x and y do not share an address. x != y*x = *x xor *y  //*x = 0011 xor 0011//So *x is 0000*y = *x xor *y  //*y = 0000 xor 0011//So *y is 0011*x = *x xor *y  //*x = 0000 xor 0011//So *x is 0011

应该使用吗？

一般情况下，没有。编译器将优化掉临时变量，并且假设交换是一个常见的过程，它应该为您的平台输出最佳的机器代码。

以这个用C编写的快速测试程序为例。

#include <stdlib.h>#include <math.h>#define USE_XOR 

void xorSwap(int* x, int *y){
    if ( x != y ){
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }}void tempSwap(int* x, int* y){
    int t;
    t = *y;
    *y = *x;
    *x = t;}int main(int argc, char* argv[]){
    int x = 4;
    int y = 5;
    int z = pow(2,28); 
    while ( z-- ){#       ifdef USE_XOR
            xorSwap(&x,&y);#       else
            tempSwap(&x, &y);#       endif
    }
    return x + y;    }

编译使用：

gcc -Os main.c -o swap

xor版本需要

real    0m2.068suser    0m2.048ssys  0m0.000s

带临时变量的版本在哪里：

real    0m0.543suser    0m0.540ssys  0m0.000s

Answer 2

一般形式是：

A = A operation B
B = A inverse-operation B
A = A inverse-operation B

但是，您必须注意溢出，并且并非所有操作都具有针对定义操作的所有值明确定义的逆。例如*和/工作直到A或B为0

xor特别令人满意，因为它是针对所有整数定义的，并且是它自己的逆

Answer 3

a = a + b
b = a - b // b = a
a = a - b