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 + 1 = 0
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0
很明顯這幾個(gè)表達(dá)式可以用位運(yùn)算的“^”來(lái)代替，如下
復(fù)制代碼 代碼如下:
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
這樣我們就完成了簡(jiǎn)單的一位數(shù)加法，那么要進(jìn)行二位的加法，這個(gè)方法可行不可行呢？肯定是不行的，矛盾就在于，如何去
獲取進(jìn)位？要獲取進(jìn)位我們可以如下思考：
復(fù)制代碼 代碼如下:
0 + 0 = 0
1 + 0 = 0
0 + 1 = 0
1 + 1 = 1
//換個(gè)角度看就是這樣
復(fù)制代碼 代碼如下:
0 & 0 = 不進(jìn)位
1 & 0 = 不進(jìn)位
0 & 1 = 不進(jìn)位
1 & 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é)束。
相關(guān)文章
C++實(shí)現(xiàn)string存取二進(jìn)制數(shù)據(jù)的方法
這篇文章主要介紹了C++實(shí)現(xiàn)string存取二進(jìn)制數(shù)據(jù)的方法,針對(duì)STL中string的用法進(jìn)行了較為詳細(xì)的分析,需要的朋友可以參考下2014-10-10
OpenCV實(shí)現(xiàn)無(wú)縫克隆算法的步驟詳解
借助無(wú)縫克隆算法，您可以從一張圖像中復(fù)制一個(gè)對(duì)象，然后將其粘貼到另一張圖像中，從而形成一個(gè)看起來(lái)無(wú)縫且自然的構(gòu)圖。本文將詳解OpenCV實(shí)現(xiàn)無(wú)縫克隆算法的步驟，需要的可以參考一下
2022-06-06 
VS2019添加引用出錯(cuò)：對(duì)COM組件的調(diào)用返回了錯(cuò)誤HRESULT E_FAIL（未能完成操作未指定的錯(cuò)誤）
這篇文章主要介紹了VS2019添加引用出錯(cuò)：對(duì)COM組件的調(diào)用返回了錯(cuò)誤HRESULT E_FAIL（未能完成操作。未指定的錯(cuò)誤）,需要的朋友可以參考下
2020-07-07 
分支結(jié)構(gòu)的執(zhí)行是依據(jù)一定的條件選擇執(zhí)行路徑，而不是嚴(yán)格按照語(yǔ)句出現(xiàn)的物理順序。分支結(jié)構(gòu)的程序設(shè)計(jì)方法的關(guān)鍵在于構(gòu)造合適的分支條件和分析程序流程，根據(jù)不同的程序流程選擇適當(dāng)?shù)姆种дZ(yǔ)句
2021-10-10 
C語(yǔ)言實(shí)現(xiàn)排序算法之歸并排序詳解
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)排序算法之歸并排序,對(duì)歸并排序的原理及實(shí)現(xiàn)過(guò)程做了非常詳細(xì)的解讀,需要的朋友可以參考下
2014-07-07 
這篇文章主要介紹了C++結(jié)構(gòu)體用法,實(shí)例分析了默認(rèn)構(gòu)造函數(shù),復(fù)制構(gòu)造函數(shù),運(yùn)算符重載等使用技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
2015-01-01 
C++設(shè)計(jì)模式之策略模式（Strategy）
這篇文章主要為大家詳細(xì)介紹了C++設(shè)計(jì)模式之策略模式Strategy
，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2018-04-04 
本文主要介紹了c++實(shí)現(xiàn)哈希桶的步驟，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2023-07-07 
在 C 語(yǔ)言中，字符串實(shí)際上是使用空字符 \0 結(jié)尾的一維字符數(shù)組。因此，\0 是用于標(biāo)記字符串的結(jié)束?？兆址∟ull character）又稱(chēng)結(jié)束符，縮寫(xiě) NUL，是一個(gè)數(shù)值為 0 的控制字符，\0 是轉(zhuǎn)義字符，意思是告訴編譯器，這不是字符 0，而是空字符
2022-04-04