补码乘法原理

大家都来学习booth算法了，那么补码的加法一定了解了。即
[ X ] 补 + [ Y ] 补 = [ X + Y ] 补 [X]_补+[Y]_补=[X+Y]_补 [X]补​+[Y]补​=[X+Y]补​
那么乘法同样的，我们也想用补码来表示，但是
[ X ] 补 ∗ [ Y ] 补 ≠ [ X ∗ Y ] 补 [X]_补*[Y]_补\neq[X*Y]_补 [X]补​∗[Y]补​​=[X∗Y]补​
现在我们需要知道补码的定义，对于n位的补码，定义如下：
[ Y ] 补 = − y n − 1 ∗ 2 n − 1 + ∑ i = 0 n − 2 y i ∗ 2 i [Y]_补=-y_{n-1}*2^{n-1}+\sum_{i=0}^{n-2}y_i*2^i [Y]补​=−yn−1​∗2n−1+i=0∑n−2​yi​∗2i
是不是有点晕，别急，我们举两个例子：
正 数 ： 0101 = − 0 ∗ 2 3 + 1 ∗ 2 2 + 0 ∗ 2 1 + 1 ∗ 2 0 = 0 + 4 + 0 + 1 = 5 正数：0101=-0*2^3+1*2^2+0*2^1+1*2^0=0+4+0+1=5 正数：0101=−0∗23+1∗22+0∗21+1∗20=0+4+0+1=5
负 数 ： 1011 = − 1 ∗ 2 3 + 0 ∗ 2 2 + 1 ∗ 2 1 + 1 ∗ 2 0 = − 8 + 0 + 2 + 1 = − 5 负数：1011=-1*2^3+0*2^2+1*2^1+1*2^0=-8+0+2+1=-5 负数：1011=−1∗23+0∗22+1∗21+1∗20=−8+0+2+1=−5
通过例子大家应该懂了，那么开始补码乘法原理的介绍

如图：

booth算法

上述的补码乘法原理是基础，booth算法就是在其基础的拓展。

booth一位一乘算法

y i y_i yi​	y i − 1 y_{i-1} yi−1​	操作
0	0	+0
0	1	+ [ X ] 补 +[X]_补 +[X]补​
1	0	− [ X ] 补 -[X]_补 −[X]补​
1	1	+0

举例（记得在y拓展一位 y − 1 y_{-1} y−1​,且每次看两位）：

booth两位一乘算法

同样是要变换一下，公式变换如下：
这次变成每次看三位了，如下：
举例（记得在y拓展一位 y − 1 y_{-1} y−1​,且每次看三位）：

OK,这就是booth算法喽????

Wallace树