TA貢獻(xiàn)1850條經(jīng)驗(yàn) 獲得超11個(gè)贊
使用xor交換算法
void xorSwap (int* x, int* y) {
if (x != y) { //ensure that memory locations are different
*x ^= *y;
*y ^= *x;
*x ^= *y;
}}
為什么要測(cè)試？
測(cè)試是為了確保x和y具有不同的內(nèi)存位置（而不是不同的值）。這是因?yàn)?code>(p xor p) = 0如果x和y共享相同的內(nèi)存位置，當(dāng)一個(gè)設(shè)置為0時(shí)，兩者都設(shè)置為0.當(dāng)* x和* y都為0時(shí)，* x和* y上的所有其他xor操作將相等0（因?yàn)樗鼈兪窍嗤模?，這意味著該函數(shù)將* x和* y都設(shè)置為0。
如果它們具有相同的值但不是相同的內(nèi)存位置，則一切都按預(yù)期工作
*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
應(yīng)該使用嗎？
一般情況下，沒有。編譯器將優(yōu)化掉臨時(shí)變量，并且假設(shè)交換是一個(gè)常見的過程，它應(yīng)該為您的平臺(tái)輸出最佳的機(jī)器代碼。
以這個(gè)用C編寫的快速測(cè)試程序?yàn)槔?/p>
#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
帶臨時(shí)變量的版本在哪里：
real 0m0.543suser 0m0.540ssys 0m0.000s
TA貢獻(xiàn)1809條經(jīng)驗(yàn) 獲得超8個(gè)贊
一般形式是：
A = A operation B B = A inverse-operation B A = A inverse-operation B
但是，您必須注意溢出，并且并非所有操作都具有針對(duì)定義操作的所有值明確定義的逆。例如*和/工作直到A或B為0
xor特別令人滿意，因?yàn)樗轻槍?duì)所有整數(shù)定義的，并且是它自己的逆
舉報(bào)