内容简介:科普文章-另一个视角解读计算机编码(修订版)
我不知道本文该作为原创发布还是作为转载发布,因为本文是《 另一个视角解读计算机编码-补码编码 》的“排版后的版本”,内容几乎没有变,除了增加了一系列的图解。
后来想了下,还是作为原创吧,毕竟《 另一个视角解读计算机编码-补码编码 》也是我自己写的,而我的版权声明:
让我自己可以任意把转载当原创,我的版权声明的受益人竟然是我自己:-)。
为什么要整理这篇文章
时间过得太快,在我写下《 另一个视角解读计算机编码-补码编码 》的时候,我记得是带着老婆去做完产检之后,我那天请了一天的假,从妇幼保健院回到家里,我利用下午的时间写了那篇文章…如今,小小都已经要上小学了,一转眼六年就这么过去了,我清晰地记得当时小小还在老婆肚子里的时候,我经常用摇滚乐和古罗马的历史故事作为胎教在家里胡吼乱叫…如今,我依然还是在家里胡吼乱叫,只不过是跟小小一起。
六年里,我自我感觉进步了很多,至少是精通了Netfilter,OpenVPN这两样吧,其次我对一些基本概念的理解也有了新的认识,在我重读我那篇讲补码编码的文章后,我第一感觉就是要重构它,我仔细看了文章下面的评论,几乎都是在说排版乱的问题,我是个完美主义者,容不得瑕疵,所以我必须花点时间把这篇文章重新整理一遍,并把它作为本文的第一部分。
文章的第一部分内容我是照搬原文的,段落间加了一些分割,并且突出显示了些核心的内容。仅仅是重新排版就完事了吗?显然是不够的。我必须增加点什么才好,作为本文的第二部分,我增加了自己对补码编码的最新解释,可能这个解释可以完爆第一部分的内容,事实上也
确实,人总是要自我超越的吧。
作为本文的第三部分,我以自己的理解尝试去解释为什么离散对数求解是一个难题,而实数域上的对数求解却很容易。这个看似与本文无关的话题,其实在我的眼里,还是有关联的。
第一部分 另一个视角解读计算机编码-补码编码
数学的计算机表示
数学是一个完全抽象的学科,而计算机是这个学科的一种形象化的实现,显然无法处理一些仅在抽象意义上有意义的特殊“数字”,比如无穷之类的东西,。像数学中的加法,乘法这样运算,计算机必须给与实现,然而由于数学中的实数加法(以及别的运算)是建立在实数域上的,而实数域又是无限的,而计算机只能处理有限域的运算,因此必须给定一个范围,一种方案是在这个范围内保证运算的正确性,超出范围的结果给出错误提示,然而这样的计算机不是很完美,毕竟它能力太有限了,仅仅给出错误提示是不能让人满意的,如果能在有限的编码上实现诸如实数运算那样“无错误”运算就更好了,毕竟给出错误提示并不是一个很合理的计算结果,我们不需要一个提示,而是在任何情况下(包括超出范围)都可以得到一个“能够自圆其说的正确”结果,因此计算机采用了在有限域上的加法运算后再次取模的方式将结果控制在一个有限的范围内。
计算机是基于模运算来进行加法和乘法运算的,在实现编码之前,必须有一个理论支撑,对于加法,必须实现一个阿贝尔群,它要满足交换率,拥有一个“零”,每一个元素都存在一个逆,相加后等于零,并且结果也应该在该群中,只要按照如此的规则设计一个编码,那么对于计算机而言就非常圆满了,对于任何数字的加法,我们都不会得到一个“错误”,而是很实在的得到一个正确的结果,如果实数可以表示在数轴上,那么计算机处理的数就可以表示在一个圆环上。为了方便,以下将计算机表示数的范围仅考虑成字节,实际上现在计算机表示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等等,在同一圆环上进行的运算根本没有必要考虑符号,因此也就不需要提供两套指令。
第二部分 图解有限长度二进制运算与补码编码
准备工作
计算机无法表示整个抽象的实数域,我们实际使用的计算机是现实的,而非抽象的,计算机可以表示的数字是有固定长度的,比如4bit,8bit,16bit,32bit…简单期间,本文接下来以4bit为例进行讲解,首先我们定义一个初始值, 0000 ,然后让其不断加1,看看最后会发现什么:
0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111,?到1111后,再加1会怎样?很显然,再加1的话会变成 10000 ,然而我们假设我们只能表示4bit的数据,那么最高的第5bit的1将会溢出而被丢弃,所以最终的结果是 1111+0001=0000.
于是我们就有了下面的序列:
0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111,0000,0001,0010…也就是说,无论怎么加1,加多少个1,4个bit的二进制数,只能表示16个元素,它们构成一个集合:
{0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111}
时钟上的运算
是不是很像我们平时看到的时钟呢?我们的时钟上有12个刻度,当指针指向12的时候,接下来没有13,而是重新从1开始,只不过在我们的4bit例子中,刻度为16个,其它的都一样:
虽然我们是以4bit作为例子,但这并不失一般性,其实哪怕是64bit的数据,也是一样的道理,除了我这里无法给出图示…
时钟加法的物理含义
在彻底理解时钟加法的物理含义之前,我们先看一下在这个钟表式的刻度盘上如何表示一个任意的4bit集合中的数a。很简单,a的物理含义就是从刻度 0000 作为起点,刻度a最终终点的一段圆弧:
现在假设两个数相加,加数分别是x和y,那么 x+y 的物理含义就是,x维持不变,顺时针移动圆弧y,直到圆弧y的起点与圆弧x的终点重合,即将圆弧y的起点顺时针移动到圆弧x的终点,设移动后的圆弧为y’:
这样,y’的终点就是x+y的结果。OK,这很容易,不是吗?
时钟减法的物理含义
理解了加法,我们再来看看时钟减法的物理含义。
现在假设两个数相减, x-y 的物理含义相比加法来讲略微复杂,它分为两步操作:
- 先将圆弧y逆时针旋转,使其终点移动到 0000 的位置,设新的圆弧为y’:
2.然后再将圆弧x逆时针旋转,使其起点 0000 移动到圆弧y’的起始位置,设新的圆弧为x’:
这样x’的终点就是 x-y 的结果。
然而为了统一起见,我们用哥伦布航海的思路达到同样的目标,即将圆弧x和圆弧y顺时针旋转而非逆时针旋转,达到同样的效果。依然分两步:
1.先将圆弧y顺时针旋转,使其终点和 0000 重合,并翻转起点和终点,设为圆弧y’,作为基调:
2.再将圆弧x顺时针旋转,使其起点和圆弧y’的终点重合,设为x’:
圆弧x’的终点就是结果!只看上面的步骤2,你就会发现,这个和上一小节讲的加法物理意义是一致的,即都是“移动一条圆弧,使其起点与另一条圆弧的终点重合”,我们把逆时针旋转全部统一成了顺时针旋转,这就是把减法全部统一成了加法,即将 x-y 转换为了 x+(-y) 。
也许你要问,第一步中为啥要反转起点和终点呢?因为在加法中,任何圆弧的起点都是 0000 ,换句话说,你把一段圆弧理解成一个在“时钟坐标系”中以 0000 为起点的一个向量就好了。
阶段性总结
到目前为止,我们理解了在这个时钟上的加法和减法运算的物理含义,总结下来无外乎:
- 加法就是顺时钟圆弧拼接;
- 减法就是逆时针圆弧拼接;
- 由于时钟表盘是个圆,按照哥伦布的思路,从一个方向能到的地方,从另一个方向也能到。
【 避开好望角和印度洋的他国军舰与海盗,从另一个方向到达印度显然是个黑科技… 】
到目前为止,我还没有涉及任何关于二进制,编码这些概念,不急,慢慢道来。
阿贝尔群对称性–x与-x在时钟上的表示
通过对时钟加法/减法物理意义的理解,我们知道了x和-x的表示法,如下所示:
在数学上,我们知道-x是x的相反数, x+(-x) 的结果是 0 ,按照上述的物理含义,操作一遍,我们可以很显然看到这一点。
接下来有点意思了啊,为了节省篇幅,我不得不引出阿贝尔群的概念了。
阿贝尔群是什么意思,请自行wiki,我这里只说结论,上面展示的这个4bit所能表示的16个元素的集合就是一个阿贝尔群,确切的说是一个有限群,因为它只有有限的16个元素,它满足以下的性质:
- 任意的在集合中x,y之和 x+y 依然在集合中,这个已经通过上述时钟加法一目了然;
- 集合中存在一个 0元 ,即 0000 ,满足任意的x与其相加均等于x本身: x+0000=x ;
- 集合中任意一个元素x均有一个 逆元-x ,满足 x+(-x)=0000 ;
- 集合中任意两个元素x,y之和满足交换律,即 x+y=y+x
这意味着,任何元素x的相反数( 群加法里的逆元即相反数,0元为0;群乘法的逆元即倒数,0元为1 )-x在时钟圆弧表示上均相对 0000 点对称,二者的加和为 0000 ,这个不再赘述。
这里我们得到一个群对称性,即一个值和它的相反数关于 0000 对称,显然 0000 的相反数是它本身,这是阿贝尔群的性质决定的。
下面要涉及二进制编码的东西了,我们为上述的物理操作赋予二进制的意义。让我们继续。
二进制编码对称性–反码的表示
我们将4bit能表示的所有数刻在那个时钟上,再次展示出本节最初的那个图:
实际上任意长度bit的二进制都可以刻在那个时钟上。不失一般性,我们仍以4bit来讨论。
我们知道4bit(任意长度的bit)能表示的数值个数为偶数个,这个不解释。而且我们知道它们的极端在哪里,一个极端是 0000 ,另一个极端是 1111 ,对于任意长度bit表示的数,极端永远都是 00…00 和 11..11 ,一个全0,一个全1。如果我们把它们顺序排在钟表上,拿 1111 做二进制递减,拿 0000 做递增,很显然它们成对的两个值按位或的结果都是 1111 ,:
因此我们得到了另一个对称性,即反码对称性,和阿贝尔群对称不同, 0000 的反码对称是 1111 ,而不是它本身,因此它的对称轴线与阿贝尔群对称轴线有偏差:
这一切
0+(-0)=0 —> 0000+0000=0000 1+(-1)=0 —> 0001+?1=0000; 2+(-2)=0; —> 0010+?2=0000; …上述的?x该是多少?我们从上一小节的两种对称性的对比就能知道答案!
很显然,?1就是 1110 ,而?2就是 1101 ,就是与固定加数在关于群对称位置的另一个值。然而我们怎么去定义它?!这是关键!总不能每次都摆出这个表盘来,正确的科学的做法是找出一个规律,然后以此规律做出定义,也许这个定义没有任何物理含义,但它是必要的,仅为定义。
我们发现上述两种物理意义对称(群对称和反码对称)的对称轴 仅仅偏差0.5 ,因此便可以定义补码了,即一个数字在时钟上位置关于 0000 群对称的位置就是其补码,它恰好表示为该数值关于 反码对称轴对称的位置所表示的值加上0001 :
然而这个补码只是个侠义的补码,为了更加不失一般性,将概念提升,规定在反码对称轴右边的数值编码的补码是其本身,而反码对称轴左边的数值编码的补码为其位置编码加1,因为:
- 按照阿贝尔加法群,x与-x的和必须是 0000 , 0000 的对称数值为其本身 0000 ;
- 按照反码对称, 0000 的对称位置为 1111 ,不再是 0000 ,它和其本身相差 0001 。
这就是一切的意义吗?是的,这就是意义。
我的图解基本也就能到这里了,其实很简单,我相信任何没有数学基础的人都能搞得定。如有不解就自己动手画一下,真相即在眼前。关于反码,补码的概念就是这么简单,关于为什么补码是反码加1,通过上面的图解应该可以看出本质了,就是适配两种对称的不相容问题,事实上,它们是相容的…But why?
回到现实
回到现实,让我们看看现实世界。
-4,-3,-2,-1,0,1,2,3… 谁是谁的反码?这是个简单的问题。如果没有反码,何谈补码?!按照二进制的方法, -3 的补码是什么?是 -4 吗?是 -2 吗?都不是!
直接给出结论,除了二进制,别的数制没有反码,这要从状态谈起。所谓反码就是非此即彼, 0 和 1 正好有次特质。我们看十进制,与“ 0 ”相“反”的是“ 1,2,3,4,5,6,7,8,9 ”,到底是哪一个是不确定的,所以在十进制里,数值是没有反码的,既然没有反码,也就不存在“反码对称轴”了。
不存在对称轴,也就没法定义操作…是这样吗?非也!
我们可以在群环域里定义所有的这些!然而你知道为什么在实数域里不存在“补码等于反码加1”这种命题吗?因为实数域不需要编码!因为实数域的处理者是人的大脑而不是规程化的计算机,所以人可以动用任何抽象的逻辑思维来搞定这一切。当有人说出1.234这个数的时候,人脑并不需要对其进行固定格式的编码就可以理解这个数字的含义,这就是本质。
编码是为了什么?编码是为了处理现实世界的数据。然而在抽象世界,根本就不需要编码,或者说编码本身就是抽象的。
随意说,“定义一个数”和”表示一个数“是完全不同的两个概念,定义一个数是抽象的,而表示一个数则不然,数学可以定义一个数,但是要表示一个数,即必然借助人脑或者计算机,而人脑和计算机对数的表示有所有不同,基本就是这样。
对于学习者,到底是先学定义还是先学表示重要,我个人倾向于要先学会定义,你要先理解群,环的概念,才可能知道”负负得正“是必然,才会知道很多自认为神奇之处(让你说,哇,太妙了!)其实是定义之内就可以推导出来的结论,然而如果你试图首先理解Howto,即如何表示,那么很多细节会从你眼前飘走。以我个人为反面教材,我起初看到计算机可以自动处理”负负得正“(参见本文第一部分)之后兴奋不已,然而那其实只是有限域的一个根本结论,我兴奋说明我发现了美妙之处,然而在一个懂理论概念的人看来,这没什么好兴奋的,这是必然。
第三部分 离散对数难
今天是6月17号,你能快速说出30天以后是几月几号吗?很显然,很多人都可以,但我不行,我总是处理不好边界,我知道肯定是7月17号附近的某天,但我不能快速确定到底是哪天。下一个问题,现在是下午3点,你能快速说出38个小时以后是几点吗?很显然,这个问题并不难,但是如果时钟不是24小时制的,而是可以无限延展的,假设现在依然是下午3点,问你38个小时以后是几点,你会更快地回答出来,因为只要3+38就好了,即41点。那为什么24小时制约束下同样的问题就比较难?
常规的答案也许是“24小时制要做加法,然后再除法,余数什么的”…但其实从这个问题我们可以看到一个更加普遍的结论。
…
在一个无限的没有边界的空间中,所有的物体都将做匀速直线运动,这里的关键在直线运动,所以我们很容易算出物体的位置和画出它运动的轨迹,然而在一个封闭的空间中,你将很难跟踪物体的运动轨迹,当物体撞到边界之后便会弹回,如果仅仅是这么弹来弹去,那么轨迹还是有迹可循的,但是如果再考虑到多个物体之间的碰撞,那就是完全是类似布朗运动了。
如果我们把数域看作是物体运动的空间,把数元素看作是物体,那么实数域上的运算就相当于无限空间里的物体运动,匀速直线运动且遵循动量守恒,反过来看离散对数的运算,这是类似在一个mod N的封闭空间做类似布朗运动的物体了,求解离散对数就是预测物体的轨迹。连续的实数域可以做连续积分,所以对数函数可以展开成级数,但在离散的mod N中,却不行!
积分和西格玛加和并不等同。
值得注意的是,所谓的难题并不是完全不可解的,即便在无限空间中做匀速直线运动且遵循动量守恒的物体,考虑到碰撞,想追踪其轨迹也并不容易,但正如拉普拉斯妖怪所述,相对于在封闭的空间中做同样的事,要容易的多。
以上我将数域比做空间,把数值间的计算比做运动和碰撞,解释了一个观点,即封闭空间追踪物体轨迹会更难。接下来我举一个现实中的例子。那就是绕线问题。
一条或者若干条没有互相缠绕的线是多么优美,然而人们总是很难欣赏这种美。耳机听完摘下往包里一放,再用时就要捋半天,电脑电源线,网线也是一样,再牛逼的笔记本电脑,其最大的败笔都是电源线…为什么?如果把所有的线缆都捋直了,还会有问题吗?还会有烦恼吗?原因就在于,我们把线缆揉在了一个相对封闭的空间中,难免会产生死结,而解开这些死结,就类似于求解离散对数问题。
最后,我想介绍一下今天我本来要玩的一个我自己设计的游戏。我来介绍一下。
一个骰子,一张资金足够的公交卡,以及足够的1元硬币。
游戏过程:
- 出门,在最近的公交站坐上首先到来的公交车;
- 投骰子,显示的数字代表坐几站,然后根据结果N在坐完N站后下车;
- 再次投骰子,根据结果N,等待接下来到来的第N辆公交车,上车;
- 重复2,3…
这是一个非常好玩的游戏,最终你会画出一个你所在城市的地图,非常有意思,如果没有画出,那就是这个城市规划的有问题或者公交系统规划有问题。我在哈尔滨,长春,郑州,上海这四个城市均玩过这个游戏的初级版本,没有骰子,只是盲目坐到终点站…昨天跟同事闲聊说到了这个游戏,同事提到了用骰子增加随机性的想法,并且告诉我在深圳的话,一旦上了宝安大道-深南大道,基本就不是布朗运动了,而是简谐振动…因为深圳的公交系统主干就是东西向的宝安/深南大道…
这个游戏今天最终没有完成,因为今天下了一天的大雨。
我介绍的这个游戏和离散对数有什么关系呢?其实,如果我们把固定时间段内行驶的路程作为度量标准的话,我一天大概能玩80到100公里左右,然而买一张高铁票跑80到100公里,奔到广州,却是一个轨迹十分确定的路线…也许你已经知道我想表达的意思了吧。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
编程之美:微软技术面试心得
《编程之美》小组 / 电子工业出版社 / 2018-9 / 79
《编程之美:微软技术面试心得》收集了约60道算法和程序设计的题目,这些题目大部分在微软的笔试、面试中出现过,有的曾被微软员工热烈地讨论过。作者试图从书中各种有趣的问题出发,引导读者发现问题、分析问题、解决问题,寻找更优的解法。《编程之美:微软技术面试心得》内容分为以下几个部分。 游戏之乐:从游戏和其他有趣问题出发,化繁为简,分析总结。 数字之魅:编程的过程实际上就是和数字及字符打交道的......一起来看看 《编程之美:微软技术面试心得》 这本书的介绍吧!