另一个视角解读计算机编码-补码编码

长平狐 发布于 2012/09/03 12:54
阅读 51
收藏 0

数学是一个完全抽象的学科,而计算机是这个学科的一种形象化的实现,显然无法处理一些仅在抽象意义上有意义的特殊“数字”,比如无穷之类的东西,。像数学中的加法,乘法这样运算,计算机必须给与实现,然而由于数学中的实数加法(以及别的运算)是建立在实数域上的,而实数域又是无限的,而计算机只能处理有限域的运算,因此必须给定一个范围,一种方案是在这个范围内保证运算的正确性,超出范围的结果给出错误提示,然而这样的计算机不是很完美,毕竟它能力太有限了,仅仅给出错误提示是不能让人满意的,如果能在有限的编码上实现诸如实数运算那样“无错误”运算就更好了,毕竟给出错误提示并不是一个很合理的计算结果,我们不需要一个提示,而是在任何情况下(包括超出范围)都可以得到一个“能够自圆其说的正确”结果,因此计算机采用了在有限域上的加法运算后再次取模的方式将结果控制在一个有限的范围内。
     计算机是基于模运算来进行加法和乘法运算的,在实现编码之前,必须有一个理论支撑,对于加法,必须实现一个阿贝尔群,它要满足交换率,拥有一个“零”,每一个元素都存在一个逆,相加后等于零,并且结果也应该在该群中,只要按照如此的规则设计一个编码,那么对于计算机而言就非常圆满了,对于任何数字的加法,我们都不会得到一个“错误”,而是很实在的得到一个正确的结果,如果实数可以表示在数轴上,那么计算机处理的数就可以表示在一个圆环上。为了方便,以下将计算机表示数的范围仅考虑成字节,实际上现在计算机表示8字节的数已经不是什么稀罕事了。
     一个字节可以表示从00000000到11111111范围内的256个数字,由于计算机编码不区分有符号和无符号数,按照和实数的一致性,我们将其视为有符号数, 这样的话负数和正数应该各占一半,它们中间有一个0,由于十进制数和二进制数仅仅是数制的不同,不管在什么数制下,0都是不变的,那么显然需要将0编码为00000000。现在考虑一下这样做的后果,8位二进制数的最小值被编码成了0,那么负数怎么办呢?毕竟没有比0更小的数字了啊!想象一下,我们现在做的事是“编码”,一个数字的编码只是一种表示方式,它真正的含义是其字面上的值,而不是编码的值,比如说,我们可以将数字1编码成“0”,而将数字0编码为“123”,仅此而已。为了表示负数,我们先从-1开始考虑,在字面上,-1加上1就是0,而1的二进制编码就是00000001(二进制和十进制仅仅数制不同,编码正数和0当然就是完全按照字面意义进行数制转换编码的,编码负数其实就是编码一个符号“-”),其最低位就是1,根据二进制加法,要想x+00000001的结果为00000000,x的值必然是11111111,但是不对啊,8位的1和00000001加在一起是100000000而不是00000000,也就是说,结果是9位,超出了一个字节。不过这没有关系,我们的前提是计算机只能表示8位的数字,那么最高位的1当然算是溢出了,我们得到的结果就是00000000,因此-1的编码就是11111111,接下来-2呢?很显然-2+1=-1,因此-2为11111110,依次类推,我们得到的最小的负数为10000000,这是为什么呢?设想还能表示比它小1的负数x,则x+1=100000000,这样的话x的值就是01111111了,我们姑且将这个数看成是比10000000还小1的一个负数,接下来考虑一下正数,我们知道1的编码是00000001,2的编码是00000010,依次类推,我们也得到了01111111这个数,这是因为计算机将它能表示的数字编码在一个圆环上而不是一个数轴上,那么01111111到底是正数还是负数呢?这时候考虑一下阿贝尔群的性质,如果将01111111编码为负数,那么它将和它的逆元相加结果为00000000,既然计算机算术仅仅最后做了取模操作,其它的群性质和实数域的是一样的,因此01111111的逆肯定是正数,我们求出它的逆是10000000,而这个数是我们从-1开始的负数编码推导出来的一个负数编码,因此这样的假设不正确,所以01111111必然属于一个正数的编码,它的十进制数是127,它是计算机能表示的最大的整数,而10000000则是计算机能表示的最小的负数,它的十进制值是-128。
     如果最大的正数01111111加1的结果是什么呢?结果是10000000,变成了最小的负数,这也是合理的,因为计算机将数字编码在了一个圆环上。既然计算机将数字编码在一个圆环上,那么如果我们将此圆环从10000000处劈开并拉直,将得到一个线段,上面编码的数字从10000000开始是递增的,直到01111111。有了这个形象化的概念之后,下面看一下加法的实质,一个数x在圆环上,另一个数y肯定也在圆环上,x+y的计算过程则是维持x不变,将00000000到y的这一段圆弧ar摘下来,拼接到x处,最终的ar的终点处的编码就是结果,事实上ar有两种摘取方式-顺时针和逆时针,不管哪种方式,最后结果落到同一处。计算机加法的结果左后按照圆环的周长取模,并不是说先得到实数域的字面结果,然后再执行取模操作,而是按照前面设计的圆环,二进制加法最后的取模是自动进行的,本质上说这个“自动”是通过高位的溢出来实现的。注意,我们现在讨论的是编码,而不涉及有无符号,具体有符号还是无符号,就看指令的解释了,10000000可以是有符号的-128,也可以是无符号的128,同样,11111111可以是有符号的-1,也可以是无符号的255。
     编码和符号是无关联的,那么取模是如何自动实现的呢?设想250+10的操作,字面操作的结果是260,可是计算机最大只能由8位来表示,因此按照无符号解释最大也只能表示为11111111,也就是255,可是260和255还相差5,显然结果需要在255的基础上再加上5,根据刚才的形象化的圆环加法,加上5之后落到了00000100这个位置,也就是十进制数4,这个4就是就是最后的结果,一个圆环的周长是256,4正好是260除以256的余数,而取余数就是取模。在计算机硬件上,这是通过溢出来实现的,255的二进制表示为11111111,它加上1之后就发生最高位溢出到第9位,由于计算机只能表示8位的数字,因此丢弃最高位,结果为[1]00000000([]中的被丢弃),一切从0开始,再加上4,结果就是4。不管在这个圆环上绕几圈,最终的落点都在圆环上,每绕一圈就会发生最高位的溢出,然后从00000000开始,这就是取模的实质。
       对于乘法,这个圆环依然使用,两个数相乘,只要有一个数是正数,那么就可以用上述的圆弧不断拼接来得到答案,比如3*2就是用2个3这个圆弧拼接两次,-2*4就是拿4个-2这个圆弧拼接四次,对于两个负数相乘,比如-a*-b,总是可以拆成a*b*-1*-1,只需要计算-1*-1即可,也就是11111111*11111111,列出递等式进行计算,最终的结果是[xxx]00000001,高位全部溢出了,结果就是正数1,在实数乘法中,我们依靠了一个规定“负负得正”,然而在计算机编码中,负号本身和数字一起被编码,依靠溢出竟然可以推导出“负负得正”这个所谓的规定,显然,计算机是不能被“规定”的,只有在纯抽象的领域才能规定,在计算机上,必须实现这个规定,将负号和数字一起编码可以解决这个问题,直接了当的推导出了一切在实数域上的异号数字乘法的性质。
     加法和乘法都套入这个“圆环+溢出”模型之后,最后再来看一下0这个特殊的数字,在实数域上,-x+x=0也是一个规定,一个群的性质,然而在计算机,它却是被真实地实现的,也是依靠溢出,不失一般性,以-1+1为例,1的编码为00000001,要想得到-1的编码和1加和等于00000000,同时又没有对计算机的行为进行“规定”,根据二进制加法,只要能得到[x[y]]00000000就可以了,8位以上的不用管,由于计算机只能表示8位,8位以上的全部溢出即可,比如11111111+00000001=[1]00000000,就这样实现了群性质中的逆元加和等于零元的这个性质。
      教科书上经常说原码,反码,补码之类的概念,还说计算机一律使用补码编码,正数和0的补码等于原码,负数的补码等于负数相反数的原码的反码加1。其实根本不需要这么复杂的概念,仅靠以上的“圆环+溢出”模型就能说明一切,什么原码,补码之类的概念根本就没有必要引出来,之所以这么引出来是为了符合科学精神,任何事物都要有概念,概念的导出是一个分析和综合的过程,在形成概念之前必然需要归纳出一个一般结论,接下来才可以形成概念,由此可以想象,当初的编码设计者也是先想到了上述的“圆环+溢出”这个形象化的模型,进而才引出“原码,反码,补码”这些抽象的概念的,有了形象模型,再解释为何负数的补码是其相反数的反码加1就简单多了,首先要明白负数和其相反数相加等于00000000,而由于计算机没有被“规定”而是真实实现了群的性质,因此这个00000000实际上应该是100000000,溢出了一个1到第9位,我们知道一个正数和该正数取反之后相加,会得到11111111这个数字,然而再加上1则会得到[1]00000000这个所谓的0,正数的二进制编码完全按照数制的转换机制由十进制(或者其它进制)数转化而来,因此它不能变,而负数由于需要编码一个“负号”,因此它需要被改成别的,因此就由“去掉负号的该数按位取反然后加上1”来表示负数,其中包含了两个部分,第一部分是负号,第二部门为该负数的相反数。最终,表示负数的时候,其相反数就成了“原码”,得到负数编码的中间步骤-按位取反操作的结果显然就是“反码”,而结果加1则称作补码,为了一致性,正数的补码就是原码!按照有符号数据解释,所有的负数的最高位都是1,而所有的正数最高位都是0,因此最高位也就成了负号位,注意,负号“-”的编码已经隐藏在了“取相反数-按位取反-结果加1”的整个过程中了,因此最高位虽然是符号位,它却不是负号“-”的编码,你不能说负号的编码是10000000。
      如果教科书上不是先从原码,反码,补码这类概念讲起,而是先引出一个“圆环+溢出”的模型,最后通过这个模型自然而然导出这些概念的话,我想很多学生就不会被这些概念搞得糊涂且无助了。文艺复兴以来,西方科学精神风靡,要知道这种精神的本质和古代纯思辨推理精神的本质只差那么一点点,那就是“概念”要通过“现实的实现”来检验,任何概念都是通过归纳法得到感性认识,然后再通过推理得到一般性的表述,对于计算机编码以及任何其它的工程学原理而言,熟悉这个归纳的过程是最重要的,要比你熟练得掌握概念要有益得多,只有当你理解了这个归纳的过程,再去深入这些概念才会觉得轻松,理解概念的目的是将知识体系化,而只要理解归纳的过程才能真正学会这个概念。
附:关于编码的符号
c语言中提供了有符号和无符号两种类型的数据类型,其实这仅仅指示如何解释这个数据类型,对于汇编层次的编码来说是不区分符号的,比如11111111可以解释成无符号的255,也可以解释成有符号的-1。那么c语言的关于有无符号的数据类型是给谁看的呢?其实是给指令看的,指令负责解释一个数据是有符号的还是无符号的,和大部分人的想象不一样,这种指令非常少,按照常理,理应每个算术指令都应该提供两套才对,一套针对有符号数据,另一套针对无符号数据,实则没有这个必要。这是因为计算机的数字编码不区分符号,甚至没有大小,它完全是一个封闭的阿贝尔群,两个数相加前怎么解释,它们的和就怎么解释,因此完全没有必要设计两套指令,加法的过程完全符合正文中的圆弧拼接法则。正文中假设计算机最多用8位编码数据,然而如今的计算机可以用8位,16位,32位等不同的位数来编码数据,那么就涉及到“将一个x位的数据放到一个y位的空间中”这种事情,在计算机中,实际上每一种数据都表示一个圆环,如果系统中有8位,16位,32位三种数据的话,系统中就有三个圆环,只有将一个数据从一个圆环放到另一个圆环的指令才会考虑符号,比如现有8位编码为11111111,现将其放入16位的圆环中,如果它是无符号数,显然它是255,因此16位编码为0000000011111111,然而如果它是有符号数,那么它就是-1,它的16位编码就是1111111111111111,可见放到16位圆环中的位置是不同的,因此只有在这种情况下才需要考虑符号,故计算机硬件在这种情况下提供了指令组,比如movzx/movsx等等,在同一圆环上进行的运算根本没有必要考虑符号,因此也就不需要提供两套指令。


原文链接:http://blog.csdn.net/hanchaoman/article/details/6190946
加载中
返回顶部
顶部