深入理解计算机系统(2.5)---二进制整数的加、减法运算(重要)

发布时间:2013-09-28 17:52:00作者:左潇龙阅读(1128 )评论(2)

                 2.3我们介绍了无符号编码和补码编码,本次我们来看一下在这两种编码下,整数的运算是如何进行的。看后之余,别忘了“点个推荐哦。”

     

    引言

     

                 平时的编程过程中,当进行整数运算时,经常会遇到一些奇怪的结果,比如两个正数加出负数,两个负数可以加出一个正数,这些都是由于数值表示的有限性导致的。下面我们来看看C语言和Java语言当中的例子。

        public static void main(String[] args) {
            int a = 0x7FFFFFFF;
            int b = 0x7FFFFFFF;
            System.out.println(a);
            System.out.println(b);
            System.out.println( a + b );
        }

                 程序当中的a和b都是很大的正整数,结果它们相加会得到一个负数。

                  接下来我们再来看看C语言当中的例子,它也会具有同样的特性。

    #include <stdio.h>
    
    int main(){
        int a = 0x7FFFFFFF;
        int b = 0x7FFFFFFF;
        printf("%d",a);
        printf("%d",b);
        printf("%d",a+b);
    }

                 我们来看看这个程序的结果,是否与Java一致。

                 可以看到,在C于Java当中,结果都是一样的,所以我们有必要对二进制整数的运算做一些简单的了解。

     

    无符号加法

     

                 这里LZ不想按照书中的方式去介绍,我们换一种思路,来简单的了解一下吧。

                 小时候学习加法时,我们都是使用的画表式,就是上面是被加数,下面是加数,然后左边写一个加号,逢10就进1,然后下面画一条横线,横线下面就是我们的结果。

                 对于我们的二进制整数来说,其实也可以使用这种最原始的方式去计算,由此也可以认识到,二进制整数的加法也是非常简单的。只不过它与我们平时的十进制算法有一个最大的区别,那就是我们在计算机当中进行计算时,结果的位数都是有限制的因此在我们计算过后,可能需要对结果进行截断操作。

                 前面一章我们已经讲过有关截断的内容,那么很明显这里就可以用上了。这里使用的时候有一个前提,我们可以假设是进行w位的二进制运算,那么在运算之后的实际结果也一定是w位的。这里有两种情况,一种是结果依然是w位的,也就是w+1位为0。第二种则是达到了w+1位,这个时候我们需要将结果截断到w位。

                 第一种情况则属于正常的加法运算,对于第二种来说,我们根据上一章的结论可以得到,假设完整的结果为sum,则实际的结果最终为 sum mod 2w

                 在书中则是给出了一个公式,它得到这个结果的一个前提是两个操作数都满足小于2w,它与我们上面取模的结果其实是一样的。

                                           

     

                 这里LZ再稍微解释一下,对于第一种情况,x+y < 2w,则sum mod 2w是与sum一致的。对于第二种来说,当 2=< x+y < 2w+1,对 x + y 进行2w的取模运算,与 x + y - 2w是等价的。

     

    无符号的非

     

                 无符号的加法会形成一个阿贝尔群,这意味着无符号加法满足一些特性。比如可交换,可结合等等。在这个群中,单位元为0,那么每一个群中的元素,也就是每一个无符号数u,都会拥有一个逆元u-1,满足 u+ u-1 = 0。这个结论的来源是,对于w位上的无符号运算来讲,倘若两个无符号数的加法运算结果为2w,也就是1后面跟w个0,此时截断之后的结果则为0。

                 从以上的简单分析,我们可以很容易的得到一个无符号数的逆元满足以下公式(公式中的左边就是LZ写的u-1,由于图中的符号在博文中不好编辑,所以LZ以u-1替代)。

                                            

                 

    补码加法

     

                 对于补码的加法来讲,我们会建立在无符号加法的基础上来进行,这么做的一个重要前提是,它们的位表示都是一样的。

                 这里书上写的比较复杂,LZ这里稍微介绍的简单一点,其实补码加法就是先按照无符号加法进行运算,而后在进行无符号和有符号的转换。因此我们根据上面的结论可以得到,对于两个补码编码的有符号数来说,他们进行加法运算的最终结果为,假设实际的无符号结果为sum,那么最终的实际结果为 U2Tw(sum mod 2w)

                 上面的这个结果看起来很简单,但实际上它的运算结果还是比较复杂的,书中给出了四种情况的分析,采用数学推导和证明的方式来说明,估计对一部分数学基础较差的猿友来讲,这是一种折磨,因此LZ这里将会省去这部分分析,如果有兴趣的猿友可以私底下看一下书中的原版内容。

                 与无符号加法不同的是,这里会出现三种结果,一种是正常的结果,一种是正溢出,一种是负溢出

                 对于当正溢出的时候,我们的结果与无符号数类似,取模之后等价于减去2w。而当负溢出的时候,则刚好相反,取模之后的结果等价于加上2w。更直观的,由于我们最终可表示的补码数范围在-2w-1(包含)到2w-1之间,所以我们总是要试图将最终的实际结果保持在这个范围之内。于是我们可以直观的得到下面的结果。

                                  

                 

    补码的非

     

                  对于补码来说,它同样的与无符号有一样的特性,也就是对于任意一个w位的补码数t来说,它都有唯一的逆元t-1,使得t + t-1 = 0。

                  一个w位的补码数的范围在-2w-1(包含)到2w-1之间,直观的可以看出,对于不等于-2w-1的补码数x来说,它的逆元就是-x。而对于-2w-1来说,它的二进制位表示为1后面跟着w-1个0,我们需要找到一个数与其相加之后结果为0。

                  这种时候我们需要考虑的是,如果是-x,也就是2w-1,则它的位表示需要w+1位,是不存在的。因此我们需要考虑溢出的情况,对照上面的公式2.14,负溢出的时候需要加上2w,因此-2w-1的逆元就是-2w + 2w-1 = -2w-1,也就是它本身。

                  综合上面的情况,最终我们可以得到补码的逆元满足以下公式(这里与上面一样,公式左边是LZ所说的逆元t-1)。

                                   

     

    二进制整数的减法

     

                 这一部分内容在书中没有介绍,而且书中也没有提及为什么没有介绍,因此LZ在这里简单的提上几句。

                 减法运算其实是可以由加法运算替代的,我们上面已经介绍过了无符号和补码的非,其实很多CPU是没有减法运算器的,它们都是将减数进行逆运算以后送入加法器,然后进行加法运算,这样得出来的结果就是减法运算最终的结果。

                 比如我们考虑一种简单的情况,当w = 4时的无符号减法运算,对于 5 - 4这个减法运算来说,我们可以由 5 + 4-1(其中4-1是4的逆元的意思,不是1/4的意思)来替代这个减法运算。

                 为了更加直观,LZ带各位来算一下,首先4的逆元根据上面的公式可以得到为 4-1 = 24 - 4 = 12 。那么我们现在需要对5和12进行加法运算,它们的位表示分别为 0101和1100,结果为10001,也就是十进制17的位表示。不过由于我们的w = 4,因此截断之后结果为0001,也就是十进制的1。最终可以得到 5 - 4 = 1。

                 对于5 - 4来说,是考虑的结果为正的情况。或许有的猿友会对结果为负或者说是无符号数溢出的情况下有疑问,因此LZ这里对这种情况也做一个简单的介绍。我们考虑一个简单的计算 0 - 1,我们可以得到1-1 = 24 - 1 = 15。此时对0和15进行加法运算,他们的位表示分别为0000和1111,结果为1111。

                 看到这里估计有的猿友会奇怪了,这怎么回事,0 - 1 = 15?

                 当然不是,这个结果其实是正确的。考虑使用补码编码来解析1111这个位表示,它代表的值就是-1。15是1111这个位表示在无符号编码情况下的解析结果。

                 因此LZ这里也给出一个公式,就是对于两个整数x和y来说,x - y = x + y-1。这里需要特别说明的是,这个公式代表的意义是位表示,而不是实际的数值。

     

    文章小结

     

                 本次我们主要介绍了二进制整数的加法运算,除此之外LZ还多加了一部分,就是减法的简单介绍。下一章我们将继续讲解整数的乘除法运算。


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

    4
    精彩
    0
    感动
    0
    搞笑
    0
    开心
    0
    愤怒
    0
    无聊
    0
    灌水
    0
    惊讶
#1楼     时间:2013-09-28 17:54:00      来源:唐小喵
#2楼     时间:2013-09-28 20:18:00      来源:codezyc
来晚了,沙发没了,谢谢分享。
发表评论

站内搜索

最新评论