[轉載] 用位運算實作加法運算(CPU内部實作)

用位運算實作加法也就是計算機用二進制進行運算，32位的CPU隻能表示32位内的數，這裡先用1位數的加法來進行，在不考慮進位的基礎上，如下

1 + 1 = 0

1 + 0 = 1

0 + 1 = 1

0 + 0 = 0

很明顯這幾個表達式可以用位運算的“^”來代替，如下

1 ^ 1 = 0

1 ^ 0 = 1

0 ^ 1 = 1

0 ^ 0 = 0

這樣我們就完成了簡單的一位數加法，那麼要進行二位的加法，這個方法可行不可行呢？肯定是不行的，沖突就在于，如何去

擷取進位？要擷取進位我們可以如下思考：

1 + 0 = 0

0 + 1 = 0

1 + 1 = 1

//換個角度看就是這樣

0 & 0 = 不進位

1 & 0 = 不進位

0 & 1 = 不進位

1 & 1 = 進位

正好，在位運算中，我們用“<<”表示向左移動一位，也就是“進位”。那麼我們就可以得到如下的表達式

//進位可以用如下表示：

(x&y)<<1

到這裡，我們基本上擁有了這樣兩個表達式

x^y //執行加法

(x&y)<<1 //進位操作

我們來做個2位數的加法，在不考慮進位的情況下

11+01 = 100  // 本來的算法

// 用推算的表達式計算

11 ^ 01 = 10

(11 & 01) << 1 = 10

//到這裡 我們用普通的加法去運算這兩個數的時候就可以得到 10 + 10 = 100

//但是我們不需要加法，是以要想别的方法，如果讓兩個數再按剛才的算法計算一次呢

10 ^ 10 = 00

(10 & 10) << 1 = 100

到這裡基本上就得出結論了，其實後面的那個 “00” 已經不用再去計算了，因為第一個表達式就已經算出了結果。

繼續推理可以得出三位數的加法隻需重複的計算三次得到第一個表達式的值就是計算出來的結果。

c代碼如下：

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;

}

計算機本質是二進制運算，許多高人和天書都展示了如何用位運算來實作讓人糾結卻又驚奇的事情。在豆瓣上看到一篇日志描述如何用位運算實作乘法，其實問題解決的關鍵是如何用位運算實作加法。覺得原文叙述不夠精确，現總結如下。

定理1：設a，b為兩個二進制數，則a+b = a^b + (a&b)<<1。

證明：a^b是不考慮進位時加法結果。當二進制位同時為1時，才有進位，是以 (a&b)<<1是進位産生的值，稱為進位補償。将兩者相加便是完整加法結果。

定理2：使用定理1可以實作隻用位運算進行加法運算。

證明：利用定理1中的等式不停對自身進行疊代。每疊代一次，進位補償右邊就多一位0，是以最多需要加數二進制位長度次疊代，進位補償就變為0，這時運算結束。

本文轉自 zhegaozhouji 51CTO部落格，原文連結:http://blog.51cto.com/1038741/1831824