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

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.068s
user    0m2.048s
sys  0m0.000s

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

real    0m0.543s
user    0m0.540s
sys  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

Answer 4

没有人建议使用std::swap,但.

std::swap(a, b);

我不使用任何临时变量,并且取决于类型a和b实现可能有一个也没有的specalization.应该在知道"技巧"是否合适的情况下编写实现.试图再次猜测是没有意义的.

更一般地说,我可能想要做这样的事情,因为它适用于类类型,使ADL能够在可能的情况下找到更好的重载.

using std::swap;
swap(a, b);

当然,面试官对这个答案的反应可能会说明空缺.

Answer 5

正如manu已经指出的那样,XOR算法是一种流行的算法,适用于所有整数值(包括指针,运气和铸造).为了完整起见,我想提一下另外一个不那么强大的加法/减法算法:

A = A + B
B = A - B
A = A - B

在这里你必须小心溢出/下溢,但否则它的工作原理一样好.您甚至可以尝试使用浮点/双打,如果不允许XOR.

Answer 6

愚蠢的问题应该得到适当的答案:

void sw2ap(int& a, int& b) {
  register int temp = a; // !
  a = b;
  b = temp;
}

唯一很好用的register关键字.