深入理解计算机系统(2.6)---二进制整数的乘、除法运算(重要)【困难度高】

发布时间:2013-09-30 02:39:00作者:左潇龙阅读(2041 )评论(6)

      2.5我们着重介绍了二进制整数的加、减运算,本次我们继续介绍乘、除运算。本章是迄今为止最难的一章,希望各位猿友有所收获,也别忘了“点个推荐哦”。

     

    引言

     

      运算一直是程序运行当中一个重要的环节,而在二进制的运算过程当中,加法运算又是重中之重,它基本上奠定了二进制运算的基础。因为无论是减法还是乘法,都可以由加法运算来替代,唯有除法不能由加法替代。

      了解计算机运算的规律,可以有助于我们理解很多程序代码上无法理解的内容。比如上章提到的溢出问题,在了解了加法运算的原理之后,相信猿友们都可以轻松的知道为何有些运算会得到意想不到的结果。

      这里还需要提一点的是,不同的处理器所采取的运算方式可能是有细微的差别的,因此也不能一概而论。因此我们大多时候会尽量讨论运算的抽象数学特性,抽象的东西大部分时候总是可靠的,这种特性为跨平台提供了基础,不过也并非总是如此,毕竟LZ只听说过浮点数运算标准,还没听说过整数运算标准,不知道究竟是LZ孤陋寡闻了,还是确无此物。

      正因如此,我们了解一下这些运算的抽象性,会有助于我们理解程序代码级无法理解的东西。

     

    无符号乘法

     

      无符号的乘法与加法类似,它的运算方式是比较简单的,只是也可能产生溢出。对于两个w位的无符号数来说,它们的乘积范围在0到(2w-1)2之间,因此可能需要2w位二进制才能表示。因此由于位数的限制,假设两个w位的无符号数的真实乘积为pro,根据截断的规则,则实际得到的乘积为 pro mod 2w

     

    补码乘法

     

      与加法运算类似,补码乘法也是建立在无符号的基础之上的,因此我们可以很容易的得到,对于两个w位的补码数来说,假设它们的真实乘积为pro,则实际得到的乘积为 U2Tw(pro mod 2w)。

      上面的式子我们有一个假设,就是假设对于w位的两个补码数来说,它们的乘积的低w位与无符号数乘积的低w位是一样的。这意味着计算机可以使用一个指令执行无符号和补码的乘法运算。

      在书中给出了这一过程的证明,我们来大概看一下,这里主要应用了无符号编码和补码编码的关系,其中x’和y’分别代表x和y的补码编码。

                                   

      这里运用的主要技巧就是2w mod 2w = 0。

     

    乘法运算的优化

     

      根据我们小学所学的乘法运算,我们知道,假设两个w位的二进制数相乘,则需要进行w次与运算,然后进行w - 1次加法运算才能得到结果。从此不难看出,乘法运算的时间周期是很长的。因此计算机界的高手们想出了一种方式可以优化乘法运算的效率,就是使用移位和加法来替代乘法。

      上述优化的前提是对于一个w位的二进制数来说,它与2k的乘积,等同于这个二进制数左移k位,在低位补k个0。在书中对这一等式进行了证明,过程如下。

                                       

     

      这个过程主要应用了无符号编码的公式,各位猿友应该不难看懂。

      有了上面的基础,我们就可以使用移位和加法对乘法优化了。对于任意一个整数y,它总能使用二进制序列表示(假设不超过二进制的表示范围),因此我们可以将x和y乘积的二进制序列表示为如下形式(此公式在书中没有展现)。

                                           x * y = x * (yw-12w-1 + ... + y020) =  (x << w-1) * yw-1 +....+ (x << 0 ) * y0

      我们举个例子,对于x * 17,我们可以计算x * 16 + x = (x << 4) + x ,这样算下来的话,我们只需要一次移位一次加法就可以搞定这个乘法运算。而对于x * 14,则可以计算 x * 8 + x * 4 + x * 2 = (x << 3) + (x << 2) + (x << 1) ,更快的方式我们可以这么计算,x * 16 - x * 2 = (x << 4) - (x << 1) 。

      这里最后需要提一下的是,加法、减法和移位的速度并不会总快于乘法运算,因此是否要进行上面的优化就取决于二者的速度了。

     

    无符号除法

     

      除法与乘法不同,它不满足加法的分配律,也就是设y = m + n , x/y != x/m + x/n。而且不幸的是,它有时候会比乘法运算更慢,但是我们只能针对除数可表示为2k的除法运算进行优化,转换为算数右移或者逻辑右移k位的运算(无符号数为逻辑右移,为正数时,逻辑右移与算术右移效果一样)。

      由于是除法,因此我们会涉及到舍入的问题。这里定义└x/y┘的值为a",x/y为a,则对于a",它是唯一一个整数,满足 a" =< a < a"+1。

      比如└2.1┘的值就为2,而对于└-2.1┘则为-3,如果本身就是整数,则等于自身。

      书中给出了无符号数除以2k等价于右移k位(w > k >= 0)的证明,这一证明过程相对比较复杂一点,LZ这里给出一个相对简单的证明方式,不采用书上的证明。如果各位看LZ的证明看不懂的话,也可以参照一下书上的方式。

      我们假设对于一个w位的无符号数来说,假设它的位表示为[xw-1....x0],则x = xw-12w-1 + .... + x020 。因此就有以下结果。

                              x/2k = xw-12w-1-k +... + xk20 + xk-12-1 +...+ x02-k = B2Uw-k([xw-1....xk]) + xk-12-1 +...+ x02-k

      由于xk-12-1 +...+ x02-k <= 2-1 + .... 2-k = (1-(1/2)k) < 1 (这里是证明的关键一步,先假设所有位为1,则利用等比数列求和公式即可得到),因此有└xk-12-1 +...+ x02-k┘ = 0。

      因此我们可以得到└x/2k┘ = └B2Uw-k([xw-1....xk])┘ + └xk-12-1 +...+ x02-k┘ = └B2Uw-k([xw-1....xk])┘ = B2Uw-k([xw-1....xk]) = x >> k。

      更直观的,我们可以使用程序验证这一结果,看下面的Java代码。

    public class Main {
        
        public static void main(String[] args) {
            int a = 17;
            int b = 8;
            int c = a/b;
            System.out.println("a:" + Integer.toBinaryString(a));
            System.out.println("b:" + Integer.toBinaryString(b));
            System.out.println("c:" + Integer.toBinaryString(c));
            System.out.println("a >> 3:" + Integer.toBinaryString(a >> 3));
        }
    }

      这段程序的结果如下,可以看出a/b的结果就是a右移3位的结果,也就是结果等于a >> 3。

      

    补码除法

     

      由于刚才我们的程序使用的都是正数,因此虽然Java中没有无符号数,不过我们可以模拟出无符号数的效果。也可以认为,补码除法在被除数为正数的情况下,与无符号编码是一样的效果(我们不考虑除数为负的情况,因为被除数与除数的符号位可以相互抵消,以下也一样),不过当被除数为负数时就不同了。这里在介绍补码除法之前,我们先来看一下,当a为负数时的结果,也就是此时会采用补码编码。

      我们将刚才的程序稍微修改一下,如下。

    public class Main {
        
        public static void main(String[] args) {
            int a = -17;
            int b = 8;
            int c = a/b;
            System.out.println("a:" + Integer.toBinaryString(a));
            System.out.println("b:" + Integer.toBinaryString(b));
            System.out.println("c:" + Integer.toBinaryString(c));
            System.out.println("a >> 3:" + Integer.toBinaryString(a >> 3));
            System.out.println("c:" + c);
            System.out.println("a >> 3:" + (a >> 3));
        }
    }

      它得到的结果如下,有点出乎意料。

      这次为了便于观看,我们将c和a >> 3的整数值打印了出来,发现移位运算的结果是-3,而a/b的结果为-2。可以看出我们a/b的结果是我们所期望的,可是移位的运算结果似乎在舍入的时候出现了问题。

      其实这个问题出现的原因很简单,补码编码与无符号编码类似,对于位表示都有└x/2k┘= B2Tw-k([xw-1....xk]) = x >> k。不过此时由于是负数,所以采取了向下舍入。上面已经提到过└-2.1┘的值为-3。

      因此,我们得到这样一个结论,当有舍入发生时,将一个负数右移k位不等价于把它除以2k

     

    除法的补救

     

      既然在舍入时,一个负数右移k位不等价于把它除以2k。那么为了使用这种优化,计算机界的大神们自然要想办法解决这个问题。于是他们想出了一个办法,即“偏置”这个值(不得不佩服这些大神们)。

      首先我们定义┌x/y┐的值为a",x/y为a,则对于a",它是唯一一个整数,满足 a"-1 < a <= a"。

      在上面的定义基础上,“偏置”的含义就是,我们有┌x/y┐ = └(x+y-1)/y┘。这一过程的证明不难理解,我们假设x = ky + r(我们考虑r > 0 ,此时会有舍入发生),则有。

                       └(x+y-1)/y┘ = └(ky+r+y-1)/y┘ = k + └(r+y-1)/y┘ = k + 1

      可以看出在做了这个处理之后,也就是将x加上y-1的偏移量,此时在舍入时,结果会在原来的基础上加1。这也正是“偏置”的含义所在,它会将舍入“偏置”到向上舍入。

      下面我们将补码除法当中的程序按照这种方式修复一下,看是不是这个结果,如下。

    public class Main {
        
        public static void main(String[] args) {
            int a = -17;
            int b = 8;
            int c = a/b;
            System.out.println("a:" + Integer.toBinaryString(a));
            System.out.println("b:" + Integer.toBinaryString(b));
            System.out.println("c:" + Integer.toBinaryString(c));
            System.out.println("(a+b-1) >> 3:" + Integer.toBinaryString((a+b-1) >> 3));
            System.out.println("c:" + c);
            System.out.println("(a+b-1) >> 3:" + ((a+b-1) >> 3));
        }
    }

      此处我们将a“偏置”,也就是加上b-1的偏移量,我们来看结果。

      可以看出,在偏置之后,在负结果舍入时,移位运算的结果将会是我们期望得到的,这样我们便可以使用这一技巧进行优化了。

     

    文章小结

     

      到这里,二进制整数的运算就介绍完了,本章难度较高,因此各位猿友可能要费点力气了。下一章我们将进入浮点数的世界,一起期待吧。


    版权声明:本文版权归作者(左潇龙)所有,欢迎转载。但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

    3
    精彩
    0
    感动
    0
    搞笑
    0
    开心
    0
    愤怒
    0
    无聊
    0
    灌水
    0
    惊讶
#1楼     时间:2013-09-30 16:23:00      来源:codezyc
确实比较困难。
#2楼     时间:2013-10-01 14:42:00      来源:简单地快乐
博主好 我看操作系统中实现补码乘法用的是比如booth算法这种东西,和你讲这个“无符号乘法、补码乘法”不是一个东西。能给理下思路么?望详解
#3楼     时间:2013-10-01 15:37:00      来源:左潇龙
@ 简单地快乐
这里的无符号及补码乘法是考虑的数学抽象性,但是实际上CPU当中的乘法是经过优化的,也就是采用的标题当中乘法优化的这一部分。实际上booth算法就是采用加减和移位去替代乘法的算法,也就是优化后的乘法。
不知道这样说,施主能明白否。
#4楼     时间:2013-10-01 15:43:00      来源:左潇龙
@ 简单地快乐
或者贫僧再换一种说法,数学抽象性是具体的乘法实现必须满足的特性。也就是说实际当中CPU的乘法运算的实现得出来的结果,必须满足我们上面无符号乘法和补码乘法的公式。在此基础上,如何实现最终得到结果,那就是具体CPU自己的事了,如果制造商不怕速度慢没人用的话,他完全可以是使用最原始的乘法算法去实现乘法运算。
但是无论你怎么实现,只要满足数学抽象性,那最终的结果肯定是一样的。这就是数学抽象性的作用,它就像一种规范一样。
因此可以把上面提到的无符号乘法和补码乘法看成是一种规范,而booth算法可以看作是一种具体的实现,是满足了抽象性的实现算法,是一种实际实现当中优化后的算法。
这里讨论的无符号乘法与补码乘法,它们与booth算法的关系,就有点类似于虚拟机规范以及具体的虚拟机实现的关系。
#5楼     时间:2013-10-08 11:34:00      来源:迹I柳燕
#6楼     时间:2017-01-24 12:05:00      来源:网站自由开发者
二进制的除法的乘法不难啊。知道规律就行了。楼主你这讲解你带坑吗?
发表评论

站内搜索

最新评论