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

Question

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

在采访中提出的一个非常棘手的问题。

交换两个变量的值，如a=10和b=15。

通常要交换两个变量值，我们需要第三个变量，如：

temp=a;a=b;b=temp;

现在的要求是，在不使用第三个变量的情况下交换两个变量的值。

Answer 1

使用xor交换算法void&nbsp;xorSwap&nbsp;(int*&nbsp;x,&nbsp;int*&nbsp;y)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(x&nbsp;!=&nbsp;y)&nbsp;{&nbsp;//ensure&nbsp;that&nbsp;memory&nbsp;locations&nbsp;are&nbsp;different &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*x&nbsp;^=&nbsp;*y; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*y&nbsp;^=&nbsp;*x; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*x&nbsp;^=&nbsp;*y; &nbsp;&nbsp;&nbsp;&nbsp;}}为什么要测试？测试是为了确保x和y具有不同的内存位置（而不是不同的值）。这是因为(p xor p) = 0如果x和y共享相同的内存位置，当一个设置为0时，两者都设置为0.当* x和* y都为0时，* x和* y上的所有其他xor操作将相等0（因为它们是相同的），这意味着该函数将* x和* y都设置为0。如果它们具有相同的值但不是相同的内存位置，则一切都按预期工作*x&nbsp;=&nbsp;0011*y&nbsp;=&nbsp;0011//Note,&nbsp;x&nbsp;and&nbsp;y&nbsp;do&nbsp;not&nbsp;share&nbsp;an&nbsp;address.&nbsp;x&nbsp;!=&nbsp;y*x&nbsp;=&nbsp;*x&nbsp;xor&nbsp;*y&nbsp;&nbsp;//*x&nbsp;=&nbsp;0011&nbsp;xor&nbsp;0011//So&nbsp;*x&nbsp;is&nbsp;0000*y&nbsp;=&nbsp;*x&nbsp;xor&nbsp;*y&nbsp;&nbsp;//*y&nbsp;=&nbsp;0000&nbsp;xor&nbsp;0011//So&nbsp;*y&nbsp;is&nbsp;0011*x&nbsp;=&nbsp;*x&nbsp;xor&nbsp;*y&nbsp;&nbsp;//*x&nbsp;=&nbsp;0000&nbsp;xor&nbsp;0011//So&nbsp;*x&nbsp;is&nbsp;0011应该使用吗？一般情况下，没有。编译器将优化掉临时变量，并且假设交换是一个常见的过程，它应该为您的平台输出最佳的机器代码。以这个用C编写的快速测试程序为例。#include&nbsp;<stdlib.h>#include&nbsp;<math.h>#define&nbsp;USE_XOR&nbsp; void&nbsp;xorSwap(int*&nbsp;x,&nbsp;int&nbsp;*y){ &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(&nbsp;x&nbsp;!=&nbsp;y&nbsp;){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*x&nbsp;^=&nbsp;*y; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*y&nbsp;^=&nbsp;*x; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*x&nbsp;^=&nbsp;*y; &nbsp;&nbsp;&nbsp;&nbsp;}}void&nbsp;tempSwap(int*&nbsp;x,&nbsp;int*&nbsp;y){ &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;t; &nbsp;&nbsp;&nbsp;&nbsp;t&nbsp;=&nbsp;*y; &nbsp;&nbsp;&nbsp;&nbsp;*y&nbsp;=&nbsp;*x; &nbsp;&nbsp;&nbsp;&nbsp;*x&nbsp;=&nbsp;t;}int&nbsp;main(int&nbsp;argc,&nbsp;char*&nbsp;argv[]){ &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;x&nbsp;=&nbsp;4; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;y&nbsp;=&nbsp;5; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;z&nbsp;=&nbsp;pow(2,28);&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(&nbsp;z--&nbsp;){#&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ifdef&nbsp;USE_XOR &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;xorSwap(&x,&y);#&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tempSwap(&x,&nbsp;&y);#&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;endif &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;x&nbsp;+&nbsp;y;&nbsp;&nbsp;&nbsp;&nbsp;}编译使用：gcc&nbsp;-Os&nbsp;main.c&nbsp;-o&nbsp;swapxor版本需要real&nbsp;&nbsp;&nbsp;&nbsp;0m2.068suser&nbsp;&nbsp;&nbsp;&nbsp;0m2.048ssys&nbsp;&nbsp;0m0.000s带临时变量的版本在哪里：real&nbsp;&nbsp;&nbsp;&nbsp;0m0.543suser&nbsp;&nbsp;&nbsp;&nbsp;0m0.540ssys&nbsp;&nbsp;0m0.000s

Answer 2

一般形式是：A&nbsp;=&nbsp;A&nbsp;operation&nbsp;B B&nbsp;=&nbsp;A&nbsp;inverse-operation&nbsp;B A&nbsp;=&nbsp;A&nbsp;inverse-operation&nbsp;B但是，您必须注意溢出，并且并非所有操作都具有针对定义操作的所有值明确定义的逆。例如*和/工作直到A或B为0xor特别令人满意，因为它是针对所有整数定义的，并且是它自己的逆

Answer 3

a&nbsp;=&nbsp;a&nbsp;+&nbsp;b b&nbsp;=&nbsp;a&nbsp;-&nbsp;b&nbsp;//&nbsp;b&nbsp;=&nbsp;a a&nbsp;=&nbsp;a&nbsp;-&nbsp;b