哈嘍，大家好，我是阿Q。前幾天有個(gè)小伙伴去面試，被面試官的一個(gè)問題勸退了：請(qǐng)說出幾種不使用第三方變量交換兩個(gè)變量值的方法。

問題有點(diǎn)繞，好不容易縷清了面試官的問題，卻發(fā)現(xiàn)答不上來。一時(shí)間尷尬無比，只能硬著頭皮說不會(huì)。

image

遇到交換變量值的問題，通常我們的做法是：定義一個(gè)新的變量，借助它完成交換。

代碼如下：

t = a;
a = b; 
b = t;

但問題的重點(diǎn)是“不使用第三方變量”，那就變得“可愛”起來了。思考過后，拋出以下四種方法來解決該問題：

• 變量本身交換數(shù)值；
• 算術(shù)運(yùn)算；
• 指針地址操作；
• 位運(yùn)算；

變量本身交換數(shù)值

b = (a + b) - (a = b);

首先執(zhí)行 a + b 操作，然后將 b 賦值給 a，則 b = a + b - b = a，這就完成了 ab 的互換操作。

算術(shù)運(yùn)算

image

如圖所示： OA = a; OB = b; AB = b - a;

首先我們把 AB 之間的距離 b - a 賦值給 a，此時(shí) AB = a, OB = b 。

image

由于要達(dá)到 ab 交換的目的，所以 OA 要等于 b，而此時(shí) OA 的距離為 b - a ，所以得將 b - a 賦值給 b ，此時(shí) OA = b， AB = a 。

image

很容易從圖中看出，OB 的距離為 b + a，所以我們只需要將 b + a 賦值給 a 就可以完成兩者的交換了。

image

綜上所述，我們的步驟為

int a = 10;
int b = 15;
a = b - a; //b=15;a=5;
b = b - a; //b=10;a=5;
a = b + a; //b=10;a=15;

該算法只能用于整型類型。

指針地址操作

image

我們可以把 a 和 b 想象為內(nèi)存中的地址值，假設(shè) a 為 0x01ff5e70 ，b 為 0x01ff5e90 ，而 b - a 表示兩個(gè)變量在內(nèi)存中的儲(chǔ)存位置隔了多少個(gè)字節(jié)。所以我們理論上也可以按算術(shù)運(yùn)算的邏輯來交換兩個(gè)變量的值。

代碼如下（此處是 c 語言）：

//其中 a 和 b 都是指針變量，里邊存儲(chǔ)著10和20的地址
int *a = new int(10); //a=0x01ff5e70 ，此處代表a中存儲(chǔ)的地址
int *b = new int(20); //b=0x01ff5e90 ，此處代表b中存儲(chǔ)的地址

//指針變量相減得到20和10的地址間隔了多少個(gè)字節(jié)，然后轉(zhuǎn)為指針變量
a = (int*)(b-a);  //b=0x01ff5e90;a=0x8
b = (int*)(b-a);  //b=0x01ff5e70;a=0x8
a=(int*)(b+long(a));//b=0x01ff5e70;a=0x01ff5e90

b - a = 0x01ff5e90 - 0x01ff5e70 = 0x20，0x20 轉(zhuǎn)換為十進(jìn)制為 32 位，因?yàn)橐粋€(gè) int 占4位，所以這里是 0x8 。

以上只是理論狀態(tài)下的執(zhí)行過程，如果直接執(zhí)行是不能實(shí)現(xiàn)交換的。因?yàn)樯线叺拇a忽略了一個(gè)問題：代碼編譯之后，變量都是存在內(nèi)存中的，而內(nèi)存區(qū)都會(huì)存在基地址。

基地址可以理解為某塊內(nèi)存的起點(diǎn)。上邊的數(shù)據(jù)都是在基地址的基礎(chǔ)上做了偏移。

變量的地址 = 變量的基地址 + 變量的偏移地址

當(dāng)我們進(jìn)行 b - a 操作的時(shí)候，得到結(jié)果為 8 ，然后轉(zhuǎn)化為指針變量的時(shí)候就會(huì)給 8 自動(dòng)添加基地址，此時(shí)的結(jié)果就不是 0x8 了，所以會(huì)導(dǎo)致結(jié)果錯(cuò)誤。

另外，地址運(yùn)算不能出現(xiàn)負(fù)數(shù)，即當(dāng) a 的地址大于 b 的地址時(shí)，b - a < 0 ，系統(tǒng)自動(dòng)采用補(bǔ)碼的形式表示負(fù)的位移，也會(huì)產(chǎn)生錯(cuò)誤。

為了解決這個(gè)問題，我們只需要保證 b - a 得到的結(jié)果不受基地址的影響即可，所以給出以下解決方案。

int *a = new int(10);
int *b = new int(20); 
cout << a << "`````";
cout << b << "`````";
if(a < b){
 a = (int*)(b-a); 
 cout << a << "`````";

 b=(int*)(b-(long(a)&0x0000ffff));
 cout << b << "`````";

 a=(int*)(b+long(a));
 cout << a << "`````";
} else {
 b = (int*)(a-b); 
 cout << b << "`````";

 a=(int*)(a-(long(b)&0x0000ffff));
 cout << a << "`````";

 b=(int*)(a+long(b));
 cout << b << "`````";
}

執(zhí)行結(jié)果:

0x8dbe70`````0x8dbe90`````0x8`````0x8dbe70`````0x8dbe90`````

看到這，不知道大家是否真的看懂了。反正我第一次看到這兒時(shí)，感覺非常清晰（其實(shí)完全沒有理解），第二次看的時(shí)候懵逼了，完全不懂，所以還得大家仔細(xì)思考一下才行。

image

b=(int*)(b-(long(a)&0x0000ffff)); 指令的精妙之處就在于采用了位運(yùn)算中的與運(yùn)算，將 a 和 0x0000ffff 進(jìn)行與運(yùn)算后，b - a 的基地址計(jì)算結(jié)果被屏蔽，只保留了偏移地址的計(jì)算結(jié)果，也就是我們需要的字節(jié)數(shù)。

在交換很大的數(shù)據(jù)類型時(shí)，該方法執(zhí)行速度比算術(shù)算法快。因?yàn)樗粨Q的是地址，而變量值在內(nèi)存中是沒有移動(dòng)過的。

位運(yùn)算

既然上邊用到了位運(yùn)算，那我們?cè)僬f一種直接通過“異或“完成交換的方法。

簡單介紹一下異或的規(guī)則：

• 如果a、b兩個(gè)值不相同，則異或結(jié)果為1；
• 如果a、b兩個(gè)值相同，異或結(jié)果為0。

代碼如下

int a=10, b=12;//二進(jìn)制：a=1010;b=1100;
a = a^b;//a=0110;b=1100
b = a^b;//a=0110;b=1010
a = a^b;//a=1100;b=1010
System.out.println("a="+ a +",b="+ b);

執(zhí)行結(jié)果

a=12,b=10

異或運(yùn)算能夠使數(shù)據(jù)中的某些位翻轉(zhuǎn)，其他位不變。這就意味著任意一個(gè)數(shù)與任意一個(gè)給定的值連續(xù)異或兩次，值不變。

簡單總結(jié)

以上四種方法均實(shí)現(xiàn)了不借助第三方變量來完成兩個(gè)變量值的交換：

• 算術(shù)運(yùn)算和位運(yùn)算計(jì)算量相當(dāng)，只能進(jìn)行整形數(shù)據(jù)的交換；
• 地址運(yùn)算中計(jì)算較復(fù)雜，可以很輕松的實(shí)現(xiàn)大類型（比如自定義的類或結(jié)構(gòu)）的交換；
• 理論上重載 “^” 運(yùn)算符，也可以實(shí)現(xiàn)任意結(jié)構(gòu)的交換；

以上就是今天的全部內(nèi)容了，如果你有不同的意見或者更好的idea，歡迎聯(lián)系阿Q，添加阿Q可以加入技術(shù)交流群參與討論呦！