如何不使用第三方變量交換兩個變量的值

2019-11-10 18:46:06

字體：大中小

供稿：網(wǎng)友

三種算法來實(shí)現(xiàn)：1）算術(shù)運(yùn)算；2）指針地址操作；3）位運(yùn)算1）算術(shù)運(yùn)算簡單來說，就是通過普通的+和-運(yùn)算來實(shí)現(xiàn)。代碼如下： int a,b; a=10;b=12; a=b-a; //a=2;b=12 b=b-a; //a=2;b=10 a=b+a; //a=12;b=10 通過以上運(yùn)算，a和b中的值就進(jìn)行了交換。表面上看起來很簡單，但是不容易想到，尤其是在習(xí)慣標(biāo)準(zhǔn)算法之后。它的原理是：把a(bǔ)、b看做數(shù)軸上的點(diǎn)，圍繞兩點(diǎn)間的距離來進(jìn)行計(jì)算。具體過程：第一句“a=b-a”求出ab兩點(diǎn)的距離，并且將其保存在a中；第二句“b=b-a”求出a到原點(diǎn)的距離（b到原點(diǎn)的距離與ab兩點(diǎn)距離之差），并且將其保存在b中；第三句“a=b+a”求出b到原點(diǎn)的距離（a到原點(diǎn)距離與ab兩點(diǎn)距離之和），并且將其保存在a中。完成交換。此算法與標(biāo)準(zhǔn)算法相比，多了三個計(jì)算的過程，但是沒有借助臨時(shí)變量。（以下稱為算術(shù)算法）2）指針地址操作因?yàn)閷Φ刂返牟僮鲗?shí)際上進(jìn)行的是整數(shù)運(yùn)算，比如：兩個地址相減得到一個整數(shù)，表示兩個變量在內(nèi)存中的儲存位置隔了多少個字節(jié)；地址和一個整數(shù)相加即“a+10”表示以a為基地址的在a后10個a類數(shù)據(jù)單元的地址。所以理論上可以通過和算術(shù)算法類似的運(yùn)算來完成地址的交換，從而達(dá)到交換變量的目的。即： int *a,*b; //假設(shè) *a=new int(10); *b=new int(20); //&a=0x00001000h,&b=0x00001200h a=(int*)(b-a); //&a=0x00000200h,&b=0x00001200h b=(int*)(b-a); //&a=0x00000200h,&b=0x00001000h a=(int*)(b+int(a)); //&a=0x00001200h,&b=0x00001000h 通過以上運(yùn)算a、b的地址真的已經(jīng)完成了交換，且a指向了原先b指向的值，b指向原先a指向的值了嗎？上面的代碼可以通過編譯，但是執(zhí)行結(jié)果卻令人匪夷所思！原因何在？首先必須了解，操作系統(tǒng)把內(nèi)存分為幾個區(qū)域：系統(tǒng)代碼/數(shù)據(jù)區(qū)、應(yīng)用程序代碼/數(shù)據(jù)區(qū)、堆棧區(qū)、全局?jǐn)?shù)據(jù)區(qū)等等。在編譯源程序時(shí)，常量、全局變量等都放入全局?jǐn)?shù)據(jù)區(qū)，局部變量、動態(tài)變量則放入堆棧區(qū)。這樣當(dāng)算法執(zhí)行到“a=(int*)(b-a)”時(shí)，a的值并不是0x00000200h，而是要加上變量a所在內(nèi)存區(qū)的基地址，實(shí)際的結(jié)果是：0x008f0200h，其中0x008f即為基地址，0200即為a在該內(nèi)存區(qū)的位移。它是由編譯器自動添加的。因此導(dǎo)致以后的地址計(jì)算均不正確，使得a,b指向所在區(qū)的其他內(nèi)存單元。再次，地址運(yùn)算不能出現(xiàn)負(fù)數(shù)，即當(dāng)a的地址大于b的地址時(shí)，b-a<0，系統(tǒng)自動采用補(bǔ)碼的形式表示負(fù)的位移，由此會產(chǎn)生錯誤，導(dǎo)致與前面同樣的結(jié)果。有辦法解決嗎？當(dāng)然！以下是改進(jìn)的算法： if(a<b) { a=(int*)(b-a); b=(int*)(b-(int(a)&0x0000ffff)); a=(int*)(b+(int(a)&0x0000ffff)); } else { b=(int*)(a-b); a=(int*)(a-(int(b)&0x0000ffff)); b=(int*)(a+(int(b)&0x0000ffff)); } 算法做的最大改進(jìn)就是采用位運(yùn)算中的與運(yùn)算“int(a)&0x0000ffff”，因?yàn)榈刂分懈?6位為段地址，后16位為位移地址，將它和0x0000ffff進(jìn)行與運(yùn)算后，段地址被屏蔽，只保留位移地址。這樣就原始算法吻合，從而得到正確的結(jié)果。此算法同樣沒有使用第三變量就完成了值的交換，與算術(shù)算法比較它顯得不好理解，但是它有它的優(yōu)點(diǎn)即在交換很大的數(shù)據(jù)類型時(shí)，它的執(zhí)行速度比算術(shù)算法快。因?yàn)樗粨Q的時(shí)地址，而變量值在內(nèi)存中是沒有移動過的。（以下稱為地址算法）3）位運(yùn)算通過異或運(yùn)算也能實(shí)現(xiàn)變量的交換，這也許是最為神奇的，請看以下代碼： int a=10,b=12; //a=1010^b=1100; a=a^b; //a=0110^b=1100; b=a^b; //a=0110^b=1010; a=a^b; //a=1100=12;b=1010; 此算法能夠?qū)崿F(xiàn)是由異或運(yùn)算的特點(diǎn)決定的，通過異或運(yùn)算能夠使數(shù)據(jù)中的某些位翻轉(zhuǎn)，其他位不變。這就意味著任意一個數(shù)與任意一個給定的值連續(xù)異或兩次，值不變。即：a^b^b=a。將a=a^b代入b=a^b則得b=a^b^b=a;同理可以得到a=b^a^a=b;輕松完成交換。以上三個算法均實(shí)現(xiàn)了不借助其他變量來完成兩個變量值的交換，相比較而言算術(shù)算法和位算法計(jì)算量相當(dāng)，地址算法中計(jì)算較復(fù)雜，卻可以很輕松的實(shí)現(xiàn)大類型（比如自定義的類或結(jié)構(gòu)）的交換，而前兩種只能進(jìn)行整形數(shù)據(jù)的交換（理論上重載“^”運(yùn)算符，也可以實(shí)現(xiàn)任意結(jié)構(gòu)的交換）。

上一篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)之串一：KMP簡單應(yīng)用

下一篇：Linux常用命令總結(jié)