補碼一位乘法

為什么要使用補碼乘法？

在計算機中，使用一般乘法的話，對符號位還要重新進行異或操作，這樣會大大降低運算速度，而使用補碼乘法運算，就可以找到一種通用的解法來解決符號位的重復計算，而將符號位作為數(shù)字一起帶入運算器進行計算

補碼一位乘法規(guī)則

首先說明一下，為了便于證明，下面的證明都是在小數(shù)的基礎上進行的，小數(shù)證明以后便可以直接推廣整數(shù)

假設被乘數(shù)為$[x{]}_{補}$
$$[x{]}_{補}=x_0{x}_1{x}_2{x}_3...x_n$$
乘數(shù)為$[y{]}_{補}$
$$[y{]}_{補}=y_0{y}_1{y}_2{y}_3...y_n$$

兩者均為任意的符號位，則有補碼乘法公式：
$$[x?y{]}_{補}=[x{]}_{補}?y$$
而由補碼與其真值的關系：
$$\begin{gathered} [y{]}_{補}=2+y(mod2) \\ y=?y_0+\sum _{i=1}^n{y}_i{2}^{?i} \end{gathered}$$
(這個還是比較好證明的，對于正數(shù)，前面+2直接溢出了，所以還是等于y，而對于負數(shù)，第一次+1相當于是進行了一次模1運算，使其數(shù)值位跟補碼一致，第二次+1相當于糾正了符號位為負數(shù))

我們可以得到：
$$[x?y{]}_{補}=[x{]}_{補}?(?y_0+\sum _{i=1}^n{y}_i{2}^{?i})$$
在此我們可以對以上的補碼乘法公式進行證明
$$\begin{array}{rl}& [x{]}_{補}=x_0{x}_1{x}_2...x_n=(2x_0+x)mod2=(2^{n+1}{x}_0+x)mod2\\ & [y{]}_{補}=0y_1{y}_2...y_n=y\\ \therefore & [x{]}_{補}?y=(2^{n+1}{x}_0+x)y=2^{n+1}{x}_{0}y+xy\\ \because & y=(?y_0+\sum _{i=1}^n{y}_i{2}^{?i})\\ \therefore & [x{]}_{補}?y=(?2^{n+1}{x}_0{y}_0+2x_0\sum _{i=1}^n{y}_i{2}^{n?i})+xy(mod2)\\ & =2+xy(mod2)【這里要根據(jù)模2性質(zhì)進行推導】\\ & =[xy{]}_{補}\end{array}$$
其實由上面的共識我們可以很容易得到公式：
$$[xy{]}_{補}=[x{]}_{補}(0y_1{y}_2...y_n)?[x{]}_{補}?y_0$$
使用這樣的公式來求補碼乘法，我們稱之為校正法

對了，記住在使用校正法時應該是使用算數(shù)右移,即移動的時候ACC寄存器中補位的數(shù)應該跟ACC寄存器中的第一位一致

為什么要用Booth算法？

在一般的補碼乘法中，我們進行加法運算的次數(shù)和加法中1的個數(shù)存在直接關系，而對于乘數(shù)中1比較多的情況，如果還是采用一般的補碼乘法運算顯然就比較低效，因此我們使用的Booth算法，這樣只有在前后兩位產(chǎn)生01的變化時才需要進行加法（或者減法，但是計算機中的減法其實就是加法，所以不用細究）運算。這樣就可以大大提高運算效率了

Booth算法規(guī)則

第一，我們需要知道補碼的運算規(guī)律是使用n輪加法與移位，最后在多進行一次加法，關于為什么要多一次加法，如果大家使用乘法分配律來理解就很容易知道了，因為最后一定會加一個數(shù)，不要問為什么，只要理解了乘法分配律就知道了

其次，補碼一位乘法中，每次加法加的可能是$0、[x{]}_{補}、[?x{]}_{補}$，這又與原碼移位算法不一樣了

還有，對于補碼一位乘法，每次移位只能是算數(shù)移位，也就是在前面補位時，補的位和符號位一樣（只有第一位才是符號位嗷）

最最最關鍵的一點，在補碼一位運算中，符號位也會參與運算！！！

符號位參與運算?

大家一定會疑惑，為什么符號位也能參與運算？

原因很簡單，在補碼中，符號位并不是真的沒有意義的，因為我們會發(fā)現(xiàn)，在真值跟補碼的關系中，我們是可以找到一種方式將他們聯(lián)系起來的

補碼只對負數(shù)存在特別之處，但是對于正數(shù)跟原碼是沒有區(qū)別的，我們會發(fā)現(xiàn)，比如-1，他的補碼其實就是$11111111$

當我們對他進行+1操作以后，它就會變成100000000，但是由于最大表示位只有八位（在例子中），所以最后的結(jié)果會默認變成00000000也就是0

所以說，我們可以認為對于負數(shù)t來說，補碼就是$2^n+t$的二進制位（要去掉超出的位數(shù)，n為最大位數(shù)），而我們會發(fā)現(xiàn)，對于0和正數(shù)來說，這個規(guī)律同樣適用

所以我們會發(fā)現(xiàn)，這個所謂的符號位其實也可以當作數(shù)來計算，但是它同樣擔負著確認正負的重要職責，所以在轉(zhuǎn)化的時候，我們只會將符號位轉(zhuǎn)化為正負，而不會轉(zhuǎn)化成數(shù)值

但是我們在計算過程中其實可以將它當作數(shù)值來看待，反正超出的位對我們沒有什么影響（電路自動進行模運算）

---

運算法則

首先，在運算過程中，我們在MQ中會多使用一位來作為輔助位，以決定我們當前這一步到底進行加法還是減法運算，也因為MQ多了一位，所以其他寄存器也要跟著多添加一位

運算法則如上圖，其實翻譯過來就是，算上輔助位，

當在MQ寄存器中最后兩位是01時就進行加x的補碼，再進行右移位

當是10時就進行減x的補碼的操作，也就是加$[?x{]}_{補}$的操作，再進行右移位

其余的時候只要直接進行右移位就行了

WHY？

這里我不確保我能講的明白，其實理解上就是一種乘法分配律，如果看不懂的可以看這篇博客

對于任意一個數(shù)，我們在小學的時候經(jīng)常會學習使用一種辦法化繁為簡，比如計算$9?99$時，我們會將其拆分成$9?(100?1)$

這里我們其實用的是一個道理，比如對于010111110，我們可以拆分成（100000000-01000000+001000000-000000010）

這樣我們就可以使用更少的加法來簡化運算了，可以觀察到，本來我們要使用6次加法運算，現(xiàn)在我們只需要使用4次加法運算即可（計算機中減法也是通過加法完成的）

這里其實在數(shù)學上也是存在證明的，對于一個數(shù)A來說，我們可以寫成下面的形式：
$$\begin{array}{rl}A& =?x_{n?1}?2^{n?1}+x_{n?2}?2^{n?2}+...+x_0?2^0\\ & =?x_{n?1}?2^{n?1}+x_{n?2}?(2^{n?1}?2^{n?2})+...+x_0?(2^1?2^0)\\ & =2^{n?1}?(x_{n?2}?x_{n?1})+2^{n?2}?(x_{n?3}?x_{n?2})+2^1(x_0?x_1)+2^0(0?x_0)\\ 這& 里我們不妨虛構(gòu)出一個x_{?1}=0,以便得到通用結(jié)論\\ \therefore 原式& =\sum _{i=1}^n{2}^{i?1}?(x_{i?2}?x_{i?1})\end{array}$$
由此我們得證上面式子的正確性

于是我們便可以直接使用上面的結(jié)論進行Booth算法的計算，這里我直接飲用了王道的ppt，大家可以試著自己算一下

如果說實在想不起來Booth算法的規(guī)則，我們也可以使用化繁為簡的方法

總結(jié)

以上是生活随笔為你收集整理的补码一位乘法-一般乘法与Booth的证明与原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。