快捷導(dǎo)航

c語(yǔ)言中用位運(yùn)算實(shí)現(xiàn)加法技巧介紹

更新時(shí)間：2012年11月24日 15:10:03 作者：

用位運(yùn)算實(shí)現(xiàn)加法也就是計(jì)算機(jī)用二進(jìn)制進(jìn)行運(yùn)算，32位的CPU只能表示32位內(nèi)的數(shù)，這里先用1位數(shù)的加法來(lái)進(jìn)行,需要的朋友可以參考下

用位運(yùn)算實(shí)現(xiàn)加法也就是計(jì)算機(jī)用二進(jìn)制進(jìn)行運(yùn)算，32位的CPU只能表示32位內(nèi)的數(shù)，這里先用1位數(shù)的加法來(lái)進(jìn)行，在不考慮進(jìn)位的基礎(chǔ)上，如下

復(fù)制代碼代碼如下:

 
+ 1 = 0 
+ 0 = 1 
+ 1 = 1 
+ 0 = 0 

很明顯這幾個(gè)表達(dá)式可以用位運(yùn)算的“^”來(lái)代替，如下

復(fù)制代碼代碼如下:

 
^ 1 = 0 
^ 0 = 1 
^ 1 = 1 
^ 0 = 0 

這樣我們就完成了簡(jiǎn)單的一位數(shù)加法，那么要進(jìn)行二位的加法，這個(gè)方法可行不可行呢？肯定是不行的，矛盾就在于，如何去
獲取進(jìn)位？要獲取進(jìn)位我們可以如下思考：

復(fù)制代碼代碼如下:

 
+ 0 = 0 
+ 0 = 0 
+ 1 = 0 
+ 1 = 1 

//換個(gè)角度看就是這樣

復(fù)制代碼代碼如下:

 
& 0 = 不進(jìn)位 
& 0 = 不進(jìn)位 
& 1 = 不進(jìn)位 
& 1 = 進(jìn)位 

正好，在位運(yùn)算中，我們用“<<”表示向左移動(dòng)一位，也就是“進(jìn)位”。那么我們就可以得到如下的表達(dá)式

復(fù)制代碼代碼如下:

 
//進(jìn)位可以用如下表示： 
(x&y)<<1 

到這里，我們基本上擁有了這樣兩個(gè)表達(dá)式

復(fù)制代碼代碼如下:

 
x^y //執(zhí)行加法 
(x&y)<<1 //進(jìn)位操作 

我們來(lái)做個(gè)2位數(shù)的加法，在不考慮進(jìn)位的情況下

復(fù)制代碼代碼如下:

 
11+01 = 100 // 本來(lái)的算法 
// 用推算的表達(dá)式計(jì)算 
11 ^ 01 = 10 
(11 & 01) << 1 = 10 
//到這里 我們用普通的加法去運(yùn)算這兩個(gè)數(shù)的時(shí)候就可以得到 10 + 10 = 100 
//但是我們不需要加法，所以要想別的方法，如果讓兩個(gè)數(shù)再按剛才的算法計(jì)算一次呢 
10 ^ 10 = 00 
(10 & 10) << 1 = 100 

到這里基本上就得出結(jié)論了，其實(shí)后面的那個(gè) “00” 已經(jīng)不用再去計(jì)算了，因?yàn)榈谝粋€(gè)表達(dá)式就已經(jīng)算出了結(jié)果。
繼續(xù)推理可以得出三位數(shù)的加法只需重復(fù)的計(jì)算三次得到第一個(gè)表達(dá)式的值就是計(jì)算出來(lái)的結(jié)果。
c代碼如下：

復(fù)制代碼代碼如下:

 
int Add(int a,int b) 
{ 
int jw=a&b; 
int jg=a^b; 
while(jw) 
{ 
int t_a=jg; 
int t_b=jw<<1; 
jw=t_a&t_b; 
jg=t_a^t_b; 
} 
return jg; 
} 

計(jì)算機(jī)本質(zhì)是二進(jìn)制運(yùn)算，許多高人和天書(shū)都展示了如何用位運(yùn)算來(lái)實(shí)現(xiàn)讓人糾結(jié)卻又驚奇的事情。在豆瓣上看到一篇日志描述如何用位運(yùn)算實(shí)現(xiàn)乘法，其實(shí)問(wèn)題解決的關(guān)鍵是如何用位運(yùn)算實(shí)現(xiàn)加法。覺(jué)得原文敘述不夠精確，現(xiàn)總結(jié)如下。
定理1：設(shè)a，b為兩個(gè)二進(jìn)制數(shù)，則a+b = a^b + (a&b)<<1。
證明：a^b是不考慮進(jìn)位時(shí)加法結(jié)果。當(dāng)二進(jìn)制位同時(shí)為1時(shí)，才有進(jìn)位，因此 (a&b)<<1是進(jìn)位產(chǎn)生的值，稱(chēng)為進(jìn)位補(bǔ)償。將兩者相加便是完整加法結(jié)果。
定理2：使用定理1可以實(shí)現(xiàn)只用位運(yùn)算進(jìn)行加法運(yùn)算。
證明：利用定理1中的等式不停對(duì)自身進(jìn)行迭代。每迭代一次，進(jìn)位補(bǔ)償右邊就多一位0，因此最多需要加數(shù)二進(jìn)制位長(zhǎng)度次迭代，進(jìn)位補(bǔ)償就變?yōu)?，這時(shí)運(yùn)算結(jié)束。

您可能感興趣的文章: