在不使用第三個變量的情況下交換兩個變量值在采訪中提出的一個非常棘手的問題。交換兩個變量的值，如a=10和b=15。通常要交換兩個變量值，我們需要第三個變量，如：temp=a;a=b;b=temp;現在的要求是，在不使用第三個變量的情況下交換兩個變量的值。
3 回答
慕蓋茨4494581
TA貢獻1850條經驗 獲得超11個贊
使用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
海綿寶寶撒
TA貢獻1809條經驗 獲得超8個贊
一般形式是：
A = A operation B B = A inverse-operation B A = A inverse-operation B
但是，您必須注意溢出，并且并非所有操作都具有針對定義操作的所有值明確定義的逆。例如*和/工作直到A或B為0
xor特別令人滿意，因為它是針對所有整數定義的，并且是它自己的逆
- 3 回答
- 0 關注
- 1107 瀏覽
添加回答
舉報
0/150
提交
取消