补码一位乘法.docx

在定点乘法运算中，补码乘法分为补码一位乘法和补码两位乘法而补码一位乘法又分 为较正法和比较法（Booth算法）两种其中，较正法是比较法的基础因此，掌握较正法 是学习补码一位乘法的关键下面，我们就对较正法进行深入分析一、 较正法公式区幻补=［X］补*（°・丫1，丫2,…,丫丿+ ［-X］补*Y其中，X、Y是两个定点数的真值，［丫］补=Y0.Y］'Y2,…,Yn，Y0是符号位 为了推导出此公式，我们分情况来进一步分析1 、 Y=0在这种情况下，［丫］补=丫=0.0,0,…，°=°［XY］补=0=［X］补*（0.0,0,…，0）+［-X］补*0= ［X］补*（0・丫1，丫2,…,Yn）+［-X］补*Y°2、 X>=0, Y>0在这种情况下，［X］补=X，［Y］补=丫，且丫0=0不难看出，［XY］补=乂丫=［X］补*Y=凶补*（丫丫1，丫2,…,丫丿+［-幻补*0=［X］补*（0.丫1，丫2,…,Yn）+［-X］补*Y°到此为止，我们还有两种情况尚未讨论，一种情况是X<0, Y>0，一种情况是YvO前 一种情况是本文讨论的重点与很多教材上的推导方法不同，本文采用与原码一位乘法相对 照来证明此种情况。

此方法用到的知识点有原码一位乘法和补码移位规则首先，我们先来 回顾一下这两个知识点二、 原码一位乘法 原码一位乘法基本上是从手算法则演变过来的我们知道，两个数相乘的手算法则是“绝对值相乘；同号得正，异号得负”原码一位乘法也采用这种方法设凶原=Xs・X1，X2,…，Xn［Y］原=Ys"Y!，Y2,…,人因为［X］原=乂，［丫］原=丫，［XY^=XY所以［XY］原=［X］原*［Y］原则P=|［XY］原曰区］原鬥［丫］原1符号位Ps=Xs㊉Ys下面，我们对P进一步分析设 A=I［X ］原1则P=I［X］原旳［丫］原1=A*( 0.Y1,Y2, … ,Yn)=0.1{ Y1A+(0. Y2, … ,Yn)}=0.1{ Y1A +0.1{ Y2 A +(0.Y3, … , Yn)}}=0.1{ Y］A +0.1{ 丫2 A + …+0.1{Yn (A+0)}...}}这样，我们就得到了原码一位乘法的公式：P=0.1{ Y_A +0.1{ Y2 A + …+0.1{Y (A+0)}...}}1 2 nP=X ㊉Ys s s其中，P=I［XY］原1 , Ps为乘积的符号位，A=I［X］原1 , ［X］原=X .X ,X ,…,X ［Yh=Y .Y ,Y ,…,Y X 和 Y 是符号位 s 1' 2' ' n，L」原 s 1' 2' ' n， s和 s疋付号位。

三、补码移位规则 对于一个数的补码来说，左移一位相当于该数真值乘以2，右移一位相当于该数真值乘以 1/21、 非负数补码移位规则：除符号位外剩余部分作相应移位后空位补0 因为非负数补码与原码相同，所以其移位规则也相同，这很容易理解2、 负数移位规则：除符号位外剩余部分作相应移位后，左移空位补0，右移补 1 因为补码一位乘法只涉及到补码右移，所以这里只给出负数补码右移规则证明证明如 下：设［X］补= X0.X1,X2,…,Xn因为［X］补= 2+X则 X = ［X ］补一2=观活兀,…,观―2因为X为负数，所以X0=1，则x=—X0+O.X］,X2,…,Xn （注］）1/2X=-1/2 X0+1/2 （O.X X …,X ）0 1 2 n=—X0+1/2 X0+1/2 （O.X X …,X ）0 0 1 2 n=—X0+1/2（X0.X］,X2,…,Xn）一Xo+O.Xo,沁…,Xn-1写成补码形式，即得［1/2X］补吕兀,…,Xn-i即［1/2X］补= 0・1［X ］补（0.1可以看成是右移一位操作）四、较正法公式（续）3、XO证法1：前面已经讲过，原码一位乘法的公式为P=0.1{ Y_A +0.1{ Y2 A + …+0.1{Y （A+0）}...}}1 2 n不难发现，这个式子里包含着一个递归操作，递归因子是R=0.1{Y （A+Z）}m所以，我们只需证明下面这个式子即可：0.1{Ym （［B］补+［Z ］补）} = ［ 0.1{Ym （B+Z）}］补证明如下：0.1{Ym （［B］补+［Z ］补"F^Ym （［B+Z ］补）}= °.1{［Ym （B+Z）］补} （Ym只有0、1这两种可能）=［°.1{Ym （B+Z）}］补（补码右移一位）这里需要注意一点，如果两个数相加得到的结果发生溢出，若结果向右移动一位，则原 码空位补1，补码空位补0。

对上面式子的两端进行同等递归后可得［X］补*Y=［XY ］补所以［XY］补=［X］补*（0.丫1，丫2,…，Yn）+ ［-X］补*Y0证法 2：［X］补*（°.丫1，丫2,…,Yn）+ ［-X］补*Y0二［X］补*(0・丫1，丫2,…弋)= 0.1Y1［X］补+0.01Y2［X］补 + …+0.00 …01Yn［X］补= ［0.1Y1X］补+［0.01Y2X］补+ …+［0.00 …01YnX］补(°.…°】可以 看成是右移n位操作)= ［XY ］补简单来说，因为补码和原码一样支持相加和右移操作，所以补码也支持非负乘操作4、Y<0前面已经证明X=-X+0.X ,X ,…,X0 1 2 n所以，当Y<0时,Y=0.Y］,Y2,…,Yn-1XY=X (0.Y Y …,Y ) -X1 2 n［XY］补=匡(0.Y］,Y2,…,Yn)-X］二［X］补(0.丫1，丫2,…,Yn)+［-X］补二［X］补*(0.丫1，丫2,…，丫丿 + ［-X］补*Y° 证毕五、常见证法存疑与解惑在证明X<0, Y>0的情况时，有些书上是这样证明的：因为［X］补hZ+X^Zn+WX (mod 2)所以［X］补*［丫］补二［X］补*Yh( 2+X)*Y ( mod 2)h(2n+1+X)*Y ( mod 2)h2n+1Y+XY (mod 2)h2n+1(0.Y1,Y2, … ,Yn)+XY (mod 2)1 2 n因为2n (0.丫］,丫2, ,Yn)是个大于或等于1的正整数，所以2n+1 (0.Y Y …,Y ) =2 (mod 2)1 2 n所以［X］补*［Y］补= 2+XY (mod 2)FY ］补我的第一个疑问是：当2+X=2n+1+X (mod 2)时，(2+X) *Y=(2n+i+X) *Y (mod 2)吗？显然，左右两边不是恒等的。

因为Y为小数，所以在模2的情怳下，2Y不恒等于2n+1 丫，所以上式不成立我的第二个疑问是：［X］补*Y=(2+X) *Y (mod 2)吗？我们很容易产生这样的误区，认为上式是相等的但是仔细推敲一下，便会发现，上式 左边是补码运算，遵守补码运算法则而右边是真值运算，可以看作原码运算，遵守原码运 算法则更细一步说，在进行右移运算时，上式左边空位补1，右边空位补0所以，上式 不成立我的第三个疑问是：［X］补*丫到底等于什么呢？下面我们就来解决这一疑问设［X］补=(11...1) X0.X1?X2,…,Xn设 2+X=(00..0) X0.X1?X2,…,Xn上面括号里的1或0是为该数右移时补空位用的，遵守原码空位补0、补码空位补1原 则因为X是负数，所以X0=1，对于原码范畴的2+X来讲，发生溢出，右移一位时 空位补 1 所以：右移 1 位时，［X］补=(11...1) 1.x0,X］,x2,…,Xn2+X=(00..0) 0.X X X …,X0 1 2 n两者相差 1右移 2 位时，［X］补=(11...1) 1.1,X0,X］,X2,…,Xn2+X=(00..0) 0.0,X X X …,X0 1 2 n两者相差 1.1。

• • • • • •又［X］补*YFJYJX］补+0・01丫2匡］补 + …+0.00 …01Yn［X］补(2+X) *Y=0.1Y1 (2+X) +0.01Y (2+X) + ... +0.00 …01Y1 2 n( 2+X)两者相差 1 Yi+1」Y2+1.11 Y3+……所以［X］补*丫=(2+乂)*Y+1 Y1+1.1 Y2+1.11 Y3+ (mod 2)= 2(0.Y Y …,Y ) +XY+1 Y1+1.1 Y2+1.11 Y3+ (mod1 2 n 1 2 32)=2 (Y+Y + …+Y ) +XY (mod 2)1 2 n因为y1+y2+…+Yn是大于或等于1的正整数，所以上式= 2+XY ( mod 2)=［XY ］补这里需要说明一下，因为［X］补*丫过程中一直在进行模2运算，所以后面必须有模2 操作六、结束语由于本文采用Word2003格式编写，不便举例，还望谅解注1：这是补码的真值表示公式，同样适用于非负数，这里不再证明 参考文献1、 计算机组成原理PPT —刘子良2、 补码一位乘法的证明一quzy。