补码一位乘法-一般乘法与Booth的证明与原理
本文主要介绍补码一位乘法的一般解法（校正法）与Booth算法（比较法）的原理，大家如果有什么不同的见解欢迎评论
补码一位乘法
为什么要使用补码乘法？
在计算机中，使用一般乘法的话，对符号位还要重新进行异或操作，这样会大大降低运算速度，而使用补码乘法运算，就可以找到一种通用的解法来解决符号位的重复计算，而将符号位作为数字一起带入运算器进行计算
补码一位乘法规则
首先说明一下，为了便于证明，下面的证明都是在小数的基础上进行的，小数证明以后便可以直接推广整数
假设被乘数为
[
x
]
补
[x]_补
[x]补
[
x
]
补
=
x
0
x
1
x
2
x
3
.
.
.
x
n
[x]_补=x_0x_1x_2x_3...x_n
[x]补=x0x1x2x3...xn
乘数为
[
y
]
补
[y]_补
[y]补
[
y
]
补
=
y
0
y
1
y
2
y
3
.
.
.
y
n
[y]_补=y_0y_1y_2y_3...y_n
[y]补=y0y1y2y3...yn
两者均为任意的符号位，则有补码乘法公式：
[
x
∗
y
]
补
=
[
x
]
补
∗
y
[x*y]_补=[x]_补*y\\
[x∗y]补=[x]补∗y
而由补码与其真值的关系：
[
y
]
补
=
2
+
y
(
m
o
d
2
)
y
=
−
y
0
+
∑
i
=
1
n
y
i
2
−
i
[y]_补=2+y\ \ (mod\ \ 2)\\ y=-y_0+\sum_{i=1}^ny_i2^{-i}
[y]补=2+y (mod 2)y=−y0+i=1∑nyi2−i
(这个还是比较好证明的，对于正数，前面+2直接溢出了，所以还是等于y，而对于负数，第一次+1相当于是进行了一次模1运算，使其数值位跟补码一致，第二次+1相当于纠正了符号位为负数)
我们可以得到：
[
x
∗
y
]
补
=
[
x
]
补
∗
(
−
y
0
+
∑
i
=
1
n
y
i
2
−
i
)
[x*y]_补=[x]_补*(-y_0+\sum_{i=1}^ny_i2^{-i})\\
[x∗y]补=[x]补∗(−y0+i=1∑nyi2−i)
在此我们可以对以上的补码乘法公式进行证明
[
x
]
补
=
x
0
x
1
x
2
.
.
.
x
n
=
(
2
x
0
+
x
)
m
o
d
2
=
(
2
n
+
1
x
0
+
x
)
m
o
d
2
[
y
]
补
=
0
y
1
y
2
.
.
.
y
n
=
y
∴
[
x
]
补
∗
y
=
(
2
n
+
1
x
0
+
x
)
y
=
2
n
+
1
x
0
y
+
x
y
∵
y
=
(
−
y
0
+
∑
i
=
1
n
y
i
2
−
i
)
∴
[
x
]
补
∗
y
=
(
−
2
n
+
1
x
0
y
0
+
2
x
0
∑
i
=
1
n
y
i
2
n
−
i
)
+
x
y
(
m
o
d
2
)
=
2
+
x
y
(
m
o
d
2
)
【
这
里
要
根
据
模
2
性
质
进
行
推
导
】
=
[
x
y
]
补
\begin{aligned} &\ \ \ [x]_补=x_0x_1x_2...x_n=(2x_0+x)\ \ mod\ \ 2=(2^{n+1}x_0+x)\ \ mod\ \ 2\\ &\ \ \ [y]_补=0y_1y_2...y_n=y\\ \therefore&\ \ \ [x]_补*y=(2^{n+1}x_0+x)y=2^{n+1}x_0y+xy\\ \because&\ \ \ y=(-y_0+\sum_{i=1}^ny_i2^{-i})\\ \therefore&\ \ \ [x]_补*y=(-2^{n+1}x_0y_0+2x_0\sum_{i=1}^ny_i2^{n-i})+xy\ \ (mod\ \ 2)\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =2+xy \ \ \ (mod\ \ 2)【这里要根据模2性质进行推导】\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =[xy]_补 \end{aligned}
∴∵∴ [x]补=x0x1x2...xn=(2x0+x) mod 2=(2n+1x0+x) mod 2 [y]补=0y1y2...yn=y [x]补∗y=(2n+1x0+x)y=2n+1x0y+xy y=(−y0+i=1∑nyi2−i) [x]补∗y=(−2n+1x0y0+2x0i=1∑nyi2n−i)+xy (mod 2) =2+xy (mod 2)【这里要根据模2性质进行推导】 =[xy]补
其实由上面的共识我们可以很容易得到公式：
[
x
y
]
补
=
[
x
]
补
(
0
y
1
y
2
.
.
.
y
n
)
−
[
x
]
补
∗
y
0
[xy]_补=[x]_补(0y_1y_2...y_n)-[x]_补*y_0
[xy]补=[x]补(0y1y2...yn)−[x]补∗y0
使用这样的公式来求补码乘法，我们称之为校正法
对了，记住在使用校正法时应该是使用算数右移,即移动的时候ACC寄存器中补位的数应该跟ACC寄存器中的第一位一致
为什么要用Booth算法？
在一般的补码乘法中，我们进行加法运算的次数和加法中1的个数存在直接关系，而对于乘数中1比较多的情况，如果还是采用一般的补码乘法运算显然就比较低效，因此我们使用的Booth算法，这样只有在前后两位产生01的变化时才需要进行加法（或者减法，但是计算机中的减法其实就是加法，所以不用细究）运算。这样就可以大大提高运算效率了
Booth算法规则
第一，我们需要知道补码的运算规律是使用n轮加法与移位，最后在多进行一次加法，关于为什么要多一次加法，如果大家使用乘法分配律来理解就很容易知道了，因为最后一定会加一个数，不要问为什么，只要理解了乘法分配律就知道了
其次，补码一位乘法中，每次加法加的可能是 0 、 [ x ] 补 、 [ − x ] 补 0、[x]_补、[-x]_补 0、[x]补、[−x]补，这又与原码移位算法不一样了
还有，对于补码一位乘法，每次移位只能是算数移位，也就是在前面补位时，补的位和符号位一样（只有第一位才是符号位嗷）
最最最关键的一点，在补码一位运算中，符号位也会参与运算！！！
符号位参与运算❓
大家一定会疑惑，为什么符号位也能参与运算？
原因很简单，在补码中，符号位并不是真的没有意义的，因为我们会发现，在真值跟补码的关系中，我们是可以找到一种方式将他们联系起来的
补码只对负数存在特别之处，但是对于正数跟原码是没有区别的，我们会发现，比如-1，他的补码其实就是 11111111 11111111 11111111
当我们对他进行+1操作以后，它就会变成100000000，但是由于最大表示位只有八位（在例子中），所以最后的结果会默认变成00000000也就是0
所以说，我们可以认为对于负数t来说，补码就是 2 n + t 2^n+t 2n+t的二进制位（要去掉超出的位数，n为最大位数），而我们会发现，对于0和正数来说，这个规律同样适用
所以我们会发现，这个所谓的符号位其实也可以当作数来计算，但是它同样担负着确认正负的重要职责，所以在转化的时候，我们只会将符号位转化为正负，而不会转化成数值
但是我们在计算过程中其实可以将它当作数值来看待，反正超出的位对我们没有什么影响（电路自动进行模运算）
运算法则
首先，在运算过程中，我们在MQ中会多使用一位来作为辅助位，以决定我们当前这一步到底进行加法还是减法运算，也因为MQ多了一位，所以其他寄存器也要跟着多添加一位
运算法则如上图，其实翻译过来就是，算上辅助位，
当在MQ寄存器中最后两位是01时就进行加x的补码，再进行右移位
当是10时就进行减x的补码的操作，也就是加 [ − x ] 补 [-x]_补 [−x]补的操作，再进行右移位
其余的时候只要直接进行右移位就行了
WHY？
这里我不确保我能讲的明白，其实理解上就是一种乘法分配律，如果看不懂的可以看这篇博客
对于任意一个数，我们在小学的时候经常会学习使用一种办法化繁为简，比如计算 9 ∗ 99 9*99 9∗99时，我们会将其拆分成 9 ∗ ( 100 − 1 ) 9*(100-1) 9∗(100−1)
这里我们其实用的是一个道理，比如对于010111110，我们可以拆分成（100000000-01000000+001000000-000000010）
这样我们就可以使用更少的加法来简化运算了，可以观察到，本来我们要使用6次加法运算，现在我们只需要使用4次加法运算即可（计算机中减法也是通过加法完成的）
这里其实在数学上也是存在证明的，对于一个数A来说，我们可以写成下面的形式：
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
)
这
里
我
们
不
妨
虚
构
出
一
个
x
−
1
=
0
,
以
便
得
到
通
用
结
论
∴
原
式
=
∑
i
=
1
n
2
i
−
1
∗
(
x
i
−
2
−
x
i
−
1
)
\begin{aligned} 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)\\ 这&里我们不妨虚构出一个x_{-1}=0,以便得到通用结论\\ \therefore原式&=\sum_{i=1}^n2^{i-1}*(x_{i-2}-x_{i-1}) \end{aligned}
A这∴原式=−xn−1∗2n−1+xn−2∗2n−2+...+x0∗20=−xn−1∗2n−1+xn−2∗(2n−1−2n−2)+...+x0∗(21−20)=2n−1∗(xn−2−xn−1)+2n−2∗(xn−3−xn−2)+21(x0−x1)+20(0−x0)里我们不妨虚构出一个x−1=0,以便得到通用结论=i=1∑n2i−1∗(xi−2−xi−1)
由此我们得证上面式子的正确性
于是我们便可以直接使用上面的结论进行Booth算法的计算，这里我直接饮用了王道的ppt，大家可以试着自己算一下
如果说实在想不起来Booth算法的规则，我们也可以使用化繁为简的方法
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
12
0- 0
已为社区贡献1条内容
所有评论(0)