补码一位乘法之较正法的公式推导

在定点乘法运算中,补码乘法分为补码一位乘法和补码两位乘法。而补码一位乘法又分为较正法和比较法(Booth算法)两种。其中,较正法是比较法的基础。因此,掌握较正法是学习补码一位乘法的关键。下面,我们就对较正法进行深入 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 。 一、较正法公式 [XY]补= [X]补*(0.Y1,Y2, … ,Y n) + [-X]补*Y0 其中,X、Y是两个定点数的真值,[Y]补=Y0.Y1,Y2, … ,Y n,Y0是符号位。 为了推导出此公式,我们分情况来进一步分析。 1、Y=0 在这种情况下,[Y]补=Y=0.0,0, … ,0=0。 [XY]补=0 =[X]补*(0.0,0, … ,0)+[-X]补*0 =[X]补*(0.Y1,Y2, … ,Y n)+[-X]补*Y0 2、X>=0, Y>0 在这种情况下,[X]补=X,[Y]补=Y,且Y0=0。不难看出, [XY]补=XY =[X]补*Y =[X]补*(Y0.Y1,Y2, … ,Y n)+[-X]补*0 =[X]补*(0.Y1,Y2, … ,Y n)+[-X]补*Y0 到此为止,我们还有两种情况尚未讨论,一种情况是X<0, Y>0,一种情况是Y<0。前一种情况是本文讨论的重点。与很多教材上的推导方法不同,本文采用与原码一位乘法相对照来证明此种情况。此方法用到的 知识点 高中化学知识点免费下载体育概论知识点下载名人传知识点免费下载线性代数知识点汇总下载高中化学知识点免费下载 有原码一位乘法和补码移位规则。首先,我们先来回顾一下这两个知识点。 二、原码一位乘法 原码一位乘法基本上是从手算法则演变过来的。我们知道,两个数相乘的手算法则是“绝对值相乘;同号得正,异号得负”。原码一位乘法也采用这种方法。 设[X]原=X s.X1,X2, … ,X n [Y]原=Y s.Y1,Y2, … ,Y n 因为[X]原=X,[Y]原=Y,[XY]原=XY 所以[XY]原=[X]原*[Y]原 则P=|[XY]原|=|[X]原|*|[Y]原| 符号位P s=X s⊕Y s 下面,我们对P进一步分析。 设A=|[X]原| 则P=|[X]原|*|[Y]原| =A*( 0.Y1,Y2, … ,Y n) =0.1{ Y1A+(0. Y2, … ,Y n)} =0.1{ Y1A +0.1{ Y2 A +(0.Y3, … , Y n)}} =0.1{ Y1A +0.1{ Y2 A + … +0.1{Y n (A+0)}…}} 这样,我们就得到了原码一位乘法的公式: P=0.1{ Y1A +0.1{ Y2 A + … +0.1{Y n (A+0)}…}} P s=X s⊕Y s 其中,P=|[XY]原|,P s为乘积的符号位,A=|[X]原|,[X]原=X s.X1,X2, … ,X n,[Y]原=Y s.Y1,Y2, … ,Y n,X s和Y s是符号位。 三、补码移位规则 对于一个数的补码来说,左移一位相当于该数真值乘以2,右移一位相当于该数真值乘以1/2。 1、非负数补码移位规则:除符号位外剩余部分作相应移位后空位补0。 因为非负数补码与原码相同,所以其移位规则也相同,这很容易理解。 2、负数移位规则:除符号位外剩余部分作相应移位后,左移空位补0,右移补1。 因为补码一位乘法只涉及到补码右移,所以这里只给出负数补码右移规则证明。证明如下: 设[X]补=X0.X1,X2, … ,X n 因为[X]补=2+X 则X=[X]补-2 =X0.X1,X2, … ,X n-2 因为X为负数,所以X0=1, 则X=-X0+0.X1,X2, … ,X n (注1) 1/2X=-1/2 X0+1/2(0.X1,X2, … ,X n) =-X0+1/2 X0+1/2(0.X1,X2, … ,X n) =-X0+1/2(X0.X1,X2, … ,X n) =-X0+0.X0, X1,X2, … ,X n-1 写成补码形式,即得 [1/2X]补=X0.X0, X1,X2, … ,X n-1 即 [1/2X]补=0.1[X]补(0.1可以看成是右移一位操作) 四、较正法公式(续) 3、X<0, Y>0 证法1: 前面已经讲过,原码一位乘法的公式为 P=0.1{ Y1A +0.1{ Y2 A + … +0.1{Y n (A+0)}…}} 不难发现,这个式子里包含着一个递归操作,递归因子是 R=0.1{Y m (A+Z)} 所以,我们只需证明下面这个式子即可: 0.1{Y m ([B]补+[Z]补)}=[ 0.1{Y m (B+Z)}]补 证明如下: 0.1{Y m ([B]补+[Z]补)}=0.1{Y m ([B+Z]补)} =0.1{[Y m (B+Z)]补} (Y m只有0、1这两种可能) =[ 0.1{Y m (B+Z)}]补(补码右移一位) 这里需要注意一点,如果两个数相加得到的结果发生溢出,若结果向右移动一位,则原码空位补1,补码空位补0。 对上面式子的两端进行同等递归后可得 [X]补*Y=[XY]补 所以[XY]补= [X]补*(0.Y1,Y2, … ,Y n) + [-X]补*Y0 证法2: [X]补*(0.Y1,Y2, … ,Y n) + [-X]补*Y0 =[X]补*(0.Y1,Y2, … ,Y n) =0.1Y1[X]补+0.01Y2[X]补+ … +0.00 … 01Y n[X]补 =[0.1Y1X]补+[0.01Y2X]补+ … +[0.00 … 01Y n X]补(0.00 … 01可以看成是右移n位操作) =[XY]补 简单来说,因为补码和原码一样支持相加和右移操作,所以补码也支持非负乘操作。 4、Y<0 前面已经证明 X=-X0+0.X1,X2, … ,X n 所以,当Y<0时, Y=0.Y1,Y2, … ,Y n-1 XY=X(0.Y1,Y2, … ,Y n)-X [XY]补=[X(0.Y1,Y2, … ,Y n)-X]补 =[X]补(0.Y1,Y2, … ,Y n)+[-X]补 =[X]补*(0.Y1,Y2, … ,Y n) + [-X]补*Y0 证毕。 五、常见证法存疑与解惑 在证明X<0, Y>0的情况时,有些 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 上是这样证明的: 因为[X]补=2+X=2n+1+X (mod 2) 所以[X]补*[Y]补=[X]补*Y =(2+X)*Y (mod 2) =(2n+1+X)*Y (mod 2) =2n+1Y+XY (mod 2) =2n+1(0.Y1,Y2, … ,Y n)+XY (mod 2)因为2n(0.Y1,Y2, … ,Y n)是个大于或等于1的正整数, 所以2n+1(0.Y1,Y2, … ,Y n)=2 (mod 2) 所以[X]补*[Y]补=2+XY (mod 2) =[XY]补 我的第一个疑问是:当2+X=2n+1+X (mod 2)时, (2+X)*Y≡(2n+1+X)*Y (mod 2)吗? 显然,左右两边不是恒等的。因为Y为小数,所以在模2的情怳下,2Y不恒等于 2n+1 Y,所以上式不成立。 我的第二个疑问是:[X]补*Y=(2+X)*Y (mod 2)吗? 我们很容易产生这样的误区,认为上式是相等的。但是仔细推敲一下,便会发现,上式左边是补码运算,遵守补码运算法则。而右边是真值运算,可以看作原码运算,遵守原码运算法则。更细一步说,在进行右移运算时,上式左边空位补1,右边空位补0。所以,上式不成立。 我的第三个疑问是:[X]补*Y到底等于什么呢? 下面我们就来解决这一疑问。 设[X]补=(11…1)X0.X1,X2, … ,X n 设2+X=(00..0)X0.X1,X2, … ,X n 上面括号里的1或0是为该数右移时补空位用的,遵守原码空位补0、补码空位补1原则。 因为X是负数,所以X0=1,对于原码范畴的2+X来讲,发生溢出,右移一位时空位补1。所以: 右移1位时, [X]补=(11…1)1.X0,X1,X2, … ,X n 2+X=(00..0)0.X0,X1,X2, … ,X n 两者相差1。 右移2位时, [X]补=(11…1)1.1,X0,X1,X2, … ,X n 2+X=(00..0)0.0,X0,X1,X2, … ,X n 两者相差1.1。 …… 又[X]补*Y=0.1Y1[X]补+0.01Y2[X]补+ … +0.00 … 01Y n[X]补 (2+X)*Y=0.1Y1(2+X)+0.01Y2(2+X)+ … +0.00 … 01Y n (2+X) 两者相差1 Y1+1.1 Y2+1.11 Y3+…… 所以[X]补*Y=(2+X)*Y+1 Y1+1.1 Y2+1.11 Y3+……(mod 2) =2(0.Y1,Y2, … ,Y n)+XY+1 Y1+1.1 Y2+1.11 Y3+……(mod 2) =2(Y1+Y2+ … +Y n)+XY (mod 2) 因为Y1+Y2+ … +Y n是大于或等于1的正整数,所以 上式=2+XY (mod 2) =[XY]补 这里需要说明一下,因为[X]补*Y过程中一直在进行模2运算,所以后面必须有模2操作。 六、结束语 由于本文采用Word2003格式编写,不便举例,还望谅解。 注1:这是补码的真值表示公式,同样适用于非负数,这里不再证明。 参考文献 1、计算机组成原理 ppt 关于艾滋病ppt课件精益管理ppt下载地图下载ppt可编辑假如ppt教学课件下载triz基础知识ppt -刘子良 2、补码一位乘法的证明-quzy