补码乘法运算的原理
补码的出现统一了计算机运算中的加减法操作，那对于补码的乘法该如何操作呢？
补码表示法
纯小数补码的定义
[x]补={x1>x≥02+x0>x≥−1(mod2)[x]_{补}=\left\{
\begin{aligned}
x &&&&& 1> x \geq0 \\
2+x &&&&& 0>x \geq -1
\end{aligned}
\right.(mod \quad 2)
[x]补={x2+x1>x≥00>x≥−1(mod2)
比如两个小数分别为
x1=−0.0010x2=+0.1101x_1 = -0.0010 \\
x_2=+0.1101x1=−0.0010x2=+0.1101
则根据补码表示法
[x1]补=2+x1=2+(−0.0010)=1.1110000[x2]补=x2=0.1101000[x_1]_{补}=2+x_1=2+(-0.0010)=1.1110000\\ [x_2]_{补}=x_2=0.1101000[x1]补=2+x1=2+(−0.0010)=1.1110000[x2]补=x2=0.1101000
以上字长均为八位。
纯整数的补码定义
[x]补={x2n>x≥02n+1+x0>x≥−2n(mod2)[x]_{补}=\left\{
\begin{aligned}
x &&&&& 2^n> x \geq0 \\
2^{n+1}+x &&&&& 0>x \geq -2^n
\end{aligned}
\right.(mod \quad 2)
[x]补={x2n+1+x2n>x≥00>x≥−2n(mod2)
比如两个整数分别为：
x1=1101x2=−0011x_1=1101 \\
x_2 = -0011x1=1101x2=−0011
根据补码表示法
[x1]补=x1=1101[x_1]_{补}=x_1 =1101[x1]补=x1=1101
[x2]补=x2+28=10000000+(−0011)=11111101[x_2]_{补}=x_2+2^8=10000000+(-0011)=11111101[x2]补=x2+28=10000000+(−0011)=11111101
定点补码一位乘法——校正法
先给公式：
对于纯小数
[x]补=x0.x1x2…xn[y]补=y0.y1y2…yn[x]_{补}= x_0.x_1x_2\dots x_n \\
[y]_{补}=y_0.y_1y_2\dots y_n[x]补=x0.x1x2…xn[y]补=y0.y1y2…yn
其中x0x_0x0和y0y_0y0分别是被乘数与乘数xxx与yyy的符号位
[x∗y]补=x补∗(0.y1y2…yn)−[x]补∗y0[x*y]_{补}=x_补*(0.y_1y_2\dots y_n)-[x]_{补}*y_0[x∗y]补=x补∗(0.y1y2…yn)−[x]补∗y0
下来证明这一结论：
首先考虑乘数yyy为正数的情形
假定被乘数xxx也为正数，则此时是两个正数相乘。
对于正数，它的原码，补码，反码是相同的，所以根据原码乘法的正确性可以得到这种情形也是正确的。
假定被乘数xxx是负数，
则有
[x]补=x0.x1x2…xn=2+x=2n+1+x[y]补=y0.y1y2…yn=y[x]_{补}=x_0.x_1x_2\dots x_n=2+x = 2^{n+1}+x \\
[y]_{补}=y_0.y_1y_2\dots y_n=y
[x]补=x0.x1x2…xn=2+x=2n+1+x[y]补=y0.y1y2…yn=y
这一步中的2+x=2n+1+x2+x=2^{n+1}+x2+x=2n+1+x是根据mod 2的性质得到的，对于纯小数无论是+2还是+4或者是加2n2^n2n都只能保留小数点前一位的符号位，因此这些结果都是相同的。
所以有
[x]补∗[y]补=[x]补∗y=(2n+1+x)∗y=2n+1∗y+x∗y[x]_{补}*[y]_{补}=[x]_补*y\\=(2^{n+1}+x)*y=2^{n+1}*y+x*y[x]补∗[y]补=[x]补∗y=(2n+1+x)∗y=2n+1∗y+x∗y
其中
y=0.y1y2…yn=∑i=1nyi∗2−iy=0.y_1y_2\dots y_n=\sum_{i=1}^{n}y_i*2^{-i}y=0.y1y2…yn=i=1∑nyi∗2−i
所以
2n+1∗y=2∑i=1nyi∗2n−i2^{n+1}*y=2\sum_{i=1}^{n}y_i*2^{n-i}2n+1∗y=2i=1∑nyi∗2n−i
式中的n−i>=0n-i>=0n−i>=0因此
∑i=1nyi∗2n−i\sum_{i=1}^{n}y_i*2^{n-i}i=1∑nyi∗2n−i是一个整数。
所以
2n+1∗y2^{n+1}*y2n+1∗y是一个偶数。
所以
[x]补∗[y]补=[x]补∗y=(2n+1+x)∗y=2n+1∗y+x∗y=2+xy=[x∗y]补[x]_{补}*[y]_{补}=[x]_补*y\\=(2^{n+1}+x)*y=2^{n+1}*y+x*y\\=2+xy=[x*y]_补[x]补∗[y]补=[x]补∗y=(2n+1+x)∗y=2n+1∗y+x∗y=2+xy=[x∗y]补
这一步是根据x*y是负数所以有2+xy=[x∗y]补2+xy=[x*y]_补2+xy=[x∗y]补
接着考虑乘数yyy为负数的情形
在上一步中，我们证明了y是正数的情况，在证明y是负数是自然想到应该向y是正数靠拢。
考虑到：
[y]补=y0.y1y2…yn=y+2[y]_补=y_0.y_1y_2\dots y_n=y+2[y]补=y0.y1y2…yn=y+2
所以有
y=[y]补−2=1.y1y2…yn−2=0.y1y2…yn−1y=[y]_补-2=1.y_1y_2\dots y_n-2=0.y_1y_2\dots y_n -1y=[y]补−2=1.y1y2…yn−2=0.y1y2…yn−1
此时我们发现y被表示成一个正数的补码与1的差值的形式，那么我们就可以用第一问的结论：
[x∗y]补=[x∗(0.y1y2…yn)]补+[−x]补=[x]补∗(0.y1y2…yn)+[−x]补[x*y]_{补}=[x*(0.y_1y_2\dots y_n)]_补+[-x]_补\\=[x]_补*(0.y_1y_2\dots y_n)+[-x]_补[x∗y]补=[x∗(0.y1y2…yn)]补+[−x]补=[x]补∗(0.y1y2…yn)+[−x]补
结合第一种情形
[x∗y]补=[x]补∗(0.y1y2…yn)[x*y]_{补}=[x]_补*(0.y_1y_2\dots y_n)[x∗y]补=[x]补∗(0.y1y2…yn)
将两种情况统一，可得到：
[x∗y]补=[x]补∗(0.y1y2…yn)−[x]补∗y0[x*y]_{补}=[x]_补*(0.y_1y_2\dots y_n)-[x]_{补}*y_0[x∗y]补=[x]补∗(0.y1y2…yn)−[x]补∗y0
之所以称为校正法就是因为对于被乘数小于0的情形需要加上[−x]补[-x]_补[−x]补加以修正。
因为校正法需要首先判断乘数的正负，再确定是否需要加上[−x]补[-x]_补[−x]补加以修正，在这个过程中乘数的符号位不参与运算，且需要判断，所以在校正法的基础上提出了Booth乘法。
Booth乘法
[x∗y]补=[x]补(0.y1y2…yn)−[x]补∗y0[x*y]_{补}=[x]_{补}(0.y_1y_2\dots y_n)-[x]_{补}*y_0[x∗y]补=[x]补(0.y1y2…yn)−[x]补∗y0
[x∗y]补=[x]补(0.y1y2…yn)−[x]补∗y0=[x]补∗(−y0+y12−1+y22−2+…yn∗2−n)=[x]补∗[−y0+(y1−y1∗2−1)+(y2∗2−1−y2∗2−2)… ]=[x]补∗[(y1−y0)+(y2−y1)∗2−1…(yn−yn−1)∗2−(n−1)+(0−yn)∗2−n]\begin{aligned}
[x*y]_{补} &= [x]_{补}(0.y_1y_2\dots y_n)-[x]_{补}*y_0 \\
&= [x]_{补}*(-y_0+y_12^{-1}+y_22^{-2}+\dots y_n*2^{-n})\\
&= [x]_{补}*[-y_0+(y_1-y_1*2^{-1})+(y_2*2^{-1}-y_2*2^{-2})\dots]\\
&= [x]_{补}*[(y_1-y_0)+(y_2-y_1)*2^{-1}\dots (y_n-y_{n-1})*2^{-(n-1)}+(0-y_n)*2^{-n}]
\end{aligned}[x∗y]补=[x]补(0.y1y2…yn)−[x]补∗y0=[x]补∗(−y0+y12−1+y22−2+…yn∗2−n)=[x]补∗[−y0+(y1−y1∗2−1)+(y2∗2−1−y2∗2−2)…]=[x]补∗[(y1−y0)+(y2−y1)∗2−1…(yn−yn−1)∗2−(n−1)+(0−yn)∗2−n]
所以我们根据上式可以得到Booth乘法的递推公式：
[z0]C=0[z1]C=2−1{(yn+1−yn)[x]C+[z0]C}⋮[zn]C=2−1{(y2−y1)[x]C+[zn−1]C}\begin{aligned}&[z_0]_{C} = 0 \\
&[z_1]_{C} = 2^{-1}\{(y_{n+1}-y_n)[x]_C+[z_0]_{C}\}\\
& \vdots\\
&[z_n]_C= 2^{-1}\{(y_2-y_1)[x]_C+[z_{n-1}]_C\}
\end{aligned}[z0]C=0[z1]C=2−1{(yn+1−yn)[x]C+[z0]C}⋮[zn]C=2−1{(y2−y1)[x]C+[zn−1]C}
故最终的结果为：
[x∗y]补=[zn]补+(y1−y0)[x]补[x*y]_{补}=[z_n]_{补}+(y_1-y_0)[x]_{补}[x∗y]补=[zn]补+(y1−y0)[x]补
这里的zzz指的是从booth公式中最右端开始，每次加上它左边的项再乘1/2（右移一位）的临时的结果。
可将计算结果简化为如下表格
yiy_iyiyi+1y_{i+1}yi+1yi+1−yiy_{i+1}-y_{i}yi+1−yi操作000右移一位011+[x]补，右移一位+[x]_补，右移一位+[x]补，右移一位10-1−[x]补，右移一位-[x]_补，右移一位−[x]补，右移一位110右移一位这里特别需要注意的是无论是+[x]补+[x]_补+[x]补或者是−[x]补-[x]_补−[x]补都是对于高n位进行操作的。
