数字、基数及表示

整数

整数是这些熟悉的数字 …, -1, 0, +1, +2, …。整数值也被称作是‘完整的’,并且分为正数(1到无穷大),负数(-1到负无穷大),零(0),非负数(零或正数)和少有的非正数(零或负数)。正数和非负数间的差别通常非常重要,例如C语言典型地用非负数作为数组下标,明确地包括零。

基数

我们书写整数(和其它数字)时通常使用‘基数10’或‘十进制’算术。这是一种位置符号,每一个‘位置’的值比下一个大十倍。最后一个数字是一的个数,倒数第二个是10的个数,依此类推:因此数字序列593表示‘五个百,九个十和三个一’或者五百九十三。算数上我们有一个基数‘b’(典型地为一个正数,这里是10)和‘n’个数字序列an-1, an-2, …, a1, a0。这表示数值an-1*bn-1 + an-2*bn-2 + … + a1*b1 + a0*b0。(注意b1 = b及b0 = 1;我们可以简化这些,但是这种对称显得很好。)

注意在这种数学符号中,数字前面允许有多余的零,但不影响数值:0042有零个千,零个百,四个十和两个一,这个42是一样的。通常我们去掉前导零,因为它们不会带来任何有用的东西。

现代计算机内部使用二进制,或基数2。数字序列100110表示1*25 + 0*24 + 0*23 + 1*22 + 1*21 + 0*20或32 + 4 + 2或38。你可能需要熟悉二进制,至少一些较小的二的幂(1,2,4,8,16,32,64,128,256,等等)。

作为一个C程序员,你还需要熟悉另外两种基数:8(也成为‘八进制’)和16(‘十六进制’) 大于10的基数有一个符号表示的问题:单个的数字会超过9。C语言使用字母A(大小写均可)表示10,B表示11,直到F。

在C语言中表示数字四十二,你可以像通常一样用十进制,或者八进制、十六进制。在八进制中,42需要5个8和两个1,所以我们写成52而不是42。在十六进制中,我们需要两个十六和十个1,所以我们写成2A。当然如果你写‘52’,人们可能以为你是指五十二而不是四十二;像表示数字序列一样,我们需要一些方式清楚表示基数。在数学中我们使用脚标:4210 = 528 = 2A16;一些汇编语言使用后缀而不是脚标;C语言使用前缀。为了表示一个数字是十六进制,我们在其前面置上数字零和一个X(大小写均可)。为了表示它是八进制,我们在其前面置上数字零。因此在C语言中,42、052和0X2A都表示抽象数‘四十二’。

注意,数字本身没有改变,因为我们使用不同基数对它进行表示。这个事实是非常重要的:数字本身是一个抽象;不同的表示法是对抽象的具体展示。

二进制(以2为基数)数字的一个有用特性是,每位数字总是0或1。零乘任何数字为零,一乘任何其它数字就是那个数,所以只有1‘算数’,只有出现1的位置起作用。2的任何幂包括或不包括。当进位时,我们发现低位数字简单的来回跳动,高位数字在相邻的低位从1变为0时才跳进:0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, …。对于给定的二进制数字,最大可能的值是它们都是1时(最小值自然是都为0)。而且这个最大值简单地比2的下一个幂少1:例如,112 = 310,只比1002 = 410少1。如果你记住2的一些幂值,你可以立即说出表示一个给定的数值需要多少个二进制位。例如,因为211是2048及212是4096,一个大于或等于2048但是小于4096的整数,需要11位来表示它。(当然多余的位也是允许的:在前面的多余的位需要为0。)

C语言缺乏直接输出二进制数的能力,但是八进制和十六进制看起来足够了。

整数表示法

今天的计算机用二进制存储数值。它用这种方式易于表示非负整数,直到一个上限。如果一台计算机是8位字节,并且使用4个字节存储一个整数,它有32个有效位。如果我们再去到上面的位置表示法,能马上看出它能表示数值到231 + 230 + … + 21 + 20,或232-1,或(用十进制)4,294,967,295.

这对于非负整数不错,但是对于负数呢?随着时间增长,许多方案被用于二进制计算机中表示负整数。概念上最简单的一个可能是‘符号-大小’(原码),也称‘有符号大小’。其余的两个称为‘一的补码’(补码)和‘二的补码’(反码)。这三个方法在C语言中都是允许的。在这三种方法中,我们用一位表示符号,用其余的位表示数值。选择哪一位不重要,为了符号上的方便,我们倾向选择‘第一’位(这在后来当我们考虑机器的‘字节顺序’时,导致一些有趣的对抗,因为哪一位是‘第一’,依赖于你查看位和字节的位置——在低位还是高位一端)。

在符号大小表示中,你简单地从表示数字的所有‘数值’位获得数字的数值,如果符号位有效,称它为负数。因此数字1(表示符号),011(表示数值)的值是310,并且是负数,表示‘负三’。为了表示正数,我们关闭符号位,得到+3。这个方法的一个缺点是,存在两个零:常规的或‘表示正数的’零(符号位和数值位都是0),和一个‘负’零(数值位都是0,符号位被置上为1)。一个更严重的缺陷是,这种表示在计算时更复杂,拖慢计算机。在我们相加两个数之前,必须注意它们是否有相同的符号。如果不是,我们必须减去负数,而不仅仅是相加。(当然这给我们一个机会去发现溢出,但就像我们一再从计算中看到的,更重要的是尽快得到一个答案,即使它是错的。)

一的补码方法避免了第二种缺陷。在这里,为了表示一个负数,我们再次置上符号位,但这次我们也反转所有数值位(把1变为0,反之亦然)。现在为表示负三,我们设置符号位,但让数值位为空,给出1(表示符号位),100(表示数值)。当我们相加两个数,我们需要一个‘循环舍入进位’设备,把进位跳过符号位再加入数值位。

注意观察在我们相加-3加+2,-3加-1,-3加+4,这是如何工作的(下面的点表示需相加的进位):

     1100 (-3)
   + 0010 (+2)
     ----
     1110 (-1)

     .  .
     1100 (-3)
   + 1110 (-1)
     ----
     1011 (-4)

     .  .
     1100 (-3)
   + 0100 (+4)
     ----
     0001 (+1)

前两种情况的和是负数,第三种是正数。第一次加法中没有进位,所以求和很容易。第二次加法中,两个最大数值位为1产生一个进位,它被加至两个符号位(两个开始时已被置上),所以最终的符号位仍被置上。两个符号位相加时也产生一个进位,并且这个进位被送至末尾,加至最低数值位(在此例中两个都是0),所以最后的和也置低位为1。最后的例子类似:两个最大数值位产生一个进位后为0。但这次进位于(一个)符号位相加,得到另一个进位但符号位被设为0。符号位产生的进位被送至末尾,加回最低位。

已看到对零有两种表示:普通的,通常的零;以及符号位(实际上每一位)被置上的‘负零’。这个值稍较少见,并且在大量使用一的补码的计算机上,使用‘-0’的企图会(有时可供选择)在运行时被捕捉,并因此捕捉使用未被设置‘正确’值的变量的企图,通过预先用‘全1位’简单地填充所有内存。(一个类似完全以另一种形式的窍门,在今天的计算机上被发现。)

在此,再看几个使用一的补码算术的求和例子。注意如果两方进行相加的低位数值位都是1,它们的和是0(向下一个数值位带入一个进位),但是一个循环舍入进位会导致低位再变为1:

     . ...
     11001 (-6)
   + 11011 (-4)
     -----
     10101 (-10)

(我们必须总共使用五个位——或者在这里是四次数值位) 类似如果只有一个低位为1,它们的和是1(没有进位),但是这次一个循环舍入进位导致一个进位,发生一连锁反应。最坏的情况在把‘负零’加到一个值时发生:

     .....
     00010 (+2)
   + 11111 (-0)
     -----
     00010 (+2)

特别地,把-0与+0以外的任何数得到原值,然而-0加+0得到-0。

使用五个位,允许的值域是-15到+15:

     .....
     10111 (-8)
   + 10000 (-15)
     -----
     01000 (+8)

在此,我们真的得到错误的答案,不是因为一的补码,因为实际上结果放不下了:它应该是-23。

最后一种表示负整数的方法是二的补码,实际上也是目前为止最常见的。(顺便提及,参看Knuth的著作了解关于一的补码和二的补码的缩写替代不同的理由。) 这个方法也很像一的补码,除了符号位被置上时,我们跳过其余的值并对它们加1,以得到被表示的值。因此当-3在四位一的补码是1100时,它在二的补码变成1101。额外的步骤——‘加1’——避免了循环舍入加一。现在我们可以相加任何两个值,简单地抛弃符号位的进位得到和:

     .
     11010 (-6)
   + 11100 (-4)
     -----
     10110 (-10)

这表示我们能使用与相加无符号整数同样的机器指令,来相加有符号整数。这不是使用一的补码的情况:考虑第一个-6加-4得到-10的例子。循环舍入进位产生正确的结果(-10),但是如果两个五位序列是无符号整数,它们的值分别是25和27,其和为52,或者用二进制表示为110100。当然这个值需要六位而不是五位,但是我们之前得到低位是10101而不是10100。在我们的第二个例子中,当我们相加-6和-4,它们的无符号相等表示不是25和27,而是26和28,它们的和是54,或用二进制表示为110110。现在我们得到正确的地位(和一个进位,它表示结果太大,不能放在无符号的五位序列)。这种计算方法用来实现C语言的无符号整数。

在大多数情况下,这些都是相当次要的问题,因为作为使用足够高级语言的程序员,我们并非不得不关心,机器内部是如何实现数字这等如砂砾般细节。在某些地方,这些缺口开始显现——它们在这些地方,理解这些表示和它们的不足变得至关重要。例如符号-大小和一的补码都有一个我们需要处理的‘负零’,二的补码有一个不同的问题:它能表示的负值个数比正数多一个。

在符号-大小中,‘全1’位模式是-1,但是一个符号位和全0是‘-0’。在一的补码,全1是‘-0’。在二的补码,全1也是-1——那么一个符号位和全0是什么呢?答案是,它是一个没有对应正值的负值。如果我们得到这些位模式1000…00,再加1,我们加1到0111…11结果又是1000…00。在十六位中,符号位是1再跟着全0表示-32768,但是最大的正数是+32767。负数。对-32768取负得到-32768(除非,几乎不会发生地,机器为你捕获这个错误;再说,通常尽快得到错误的答案更重要)。

因此,三种表示法都有缺陷:符号-大小容易理解,但是要求大量额外硬件,并且有一个‘负零’;一的补码要求较少些额外硬件(循环舍入进位),并且类似符号大小,需要单独的指令表示有符号和无符号数,以及仍然有一个‘负零’;二的补码有一个没有对应正值的负数。但是二的补码不需要额外硬件,能够非常快,以及能够使用一套简化的指令,尽快得到错误的答案,所以大多数现代计算机这样做。

顺便提及,注意我谈及用位反转来计算一个负数的正值(及可能加1)。对于上面的数字序列求和规则,我们有一个十分优雅的数学解释。然而不同于an-1乘2n-1,对二的补码和一的补码,这个最重要的‘符号’位,分别简单地有一个值-(2n-1)或-(2n-1-1)。例如对于一个4位二进制数,低3位表示4、2和1(所以三位的最大值是7)但是首位表示-8和-7而不是8。因此数字序列1001,用二的补码表示-8+1或-7,1000表示-8。这些序列用一的补码,分别表示-7+1或-6,和-7,并且全1在二的补码里是-8+7或-1,现在是-7+7或0(因为符号位,它是-1而不是+0)。

定点数

C语言没有内置的定点数类型,但可以很容易从整型构造出来。对于一个二进制定点数,我们简单地指定这个数字中一些位作为‘小数部分’。继续使用上面的数学符号,小数点前的数字表示2n-1,2n-2,等等,直到20。后续的数字表示2-1,2-2,等等。注意2-1是0.5,2-2是0.25,2-3是0.125,等等——所以我们可以表示4.5,4.25和4.75,但是根据我们能用的位数的多少,我们或不能准确地表示某些值。如果后两位‘越过小数点’,10000表示4.00,10001表示4.25,10010表示4.50以及10011表示4.75,但是没有位模式能表示4.10。我们仅能有效的‘预乘’(或按比例缩放)2k,这里k是小数点后的位数:4.5乘4是18,用二进制表示是10010。4.1乘4是16.4,‘点4’部分不能被表示。

C语言的无符号整数类型,可以很好用于定点数,理所当然它们是无符号的。如果你需要负的定点数,你可以简单地使用有符号算术。这在大多数情况下都工作的很好,但注意在你乘或除两个定点数时会发生的事:它们已经包括比例因子2k,所以两者的乘积包括一个22k的因子,并且除法会去除这个比例因子。根据结果的使用,你可能需要调整比例。可以使用移位操作常识达到这一点,但是移位操作只对无符号整数作出定义。如果底层硬件使用一的补码或符号大小表示法,你通常会得到一个错误的答案。甚至对于二的补码,移位一个负数有时可能产生错误的答案。(或者你能用尽可能快地得到错误答案的思想来安慰自己。)

浮点数

浮点数产生于令人困惑的多种多样的实现,至少在更老的硬件。C允许几乎所有这些硬件。关注所有这些细节,远远超出这页网文的范围,所以我会有意略过似IBM的‘十六进制浮点数’一类的惨事愁云,集中关注时至今日在大多数微处理器上都有的IEEE浮点数。

考虑一个典型的十进制的‘科学记数法’数字7.2345*1012。为了方便起见,它也常常不用上标写成7.2345E12。它由两部分组成,有效数字(亦常称‘尾数’,尽管严格来讲在这里尾数是0.2345,有效数字却是整个7.2345这部分)和指数——在这里是12。这种表示法有一些有用的特点,它们中仅有一些适用计算机表示。第一个特点是在这种常规格式中,小数点前只有一位数。我们随后可以用这个避免在计算机中存储‘小数点’字符。不适用的一个,或至少不能直接应用的是‘有效数字’的概念:数字7.2345有五个数字(我们没有计算小数点),所以这个数字被认为是精确到5位。如果这个数字精确到六位,我们要写成7.23450E12:这个额外的零不影响最终的值。第三个特点,现在也用不上的是,乘法和除法更容易——我们乘和除有效数字,然后简单地加或减指数。令人好奇的是,加法和减法变得更难了。因为1.4171901E7加3.3E1要求用我们称作的‘反规范化’(因为小数点不是紧挨着第一个数字)的格式,‘重新缩放’其中一个数字:3.3E1首先变成0.0000033E7,然后我们相加两个数字得到1.4171934E7。(反规范化另一个操作数也是可能的,或者甚至两个,在相加并规范化结果。然而在一些极端的指数下,情况会变得棘手。相减两个数值接近的数字也变得微妙。比如1.99999E5减1.99998E5得到0.00001E5。这不得不被重新规范化为1.00000E0。)

科学记数法是有效的浮点数十进制格式。在这里很容易陷入这个圈套:计算机算术常常被输出为十进制浮点数格式,致使容易相信那些数字一直都是如此格式。但实际上,今天大多数计算机使用一个二进制浮点数格式。

考虑二进制浮点数格式的数字4.5。类似上面提及的定点数4.5是22 + 2-1。用二进制表示,那么是‘100.1’。现在所有我们要做的是‘规范化’这个数字为(使用‘最新发明的’字符B符号代替E)‘1.001b+2’。换言之,我们现在有1个一,0个二分一,0个四分一,1个八分一(1.125),乘以二的平方或4。对于定点数我们简单地用4缩放——在这个例子中即是。定点数和浮点数之间的不同是比例因子发生改变。为表示9.0,我们将用8(23)放大:现在我们令1个一,0个二分一,0个四分一,一个8分一乘以九得到1.001b+3。

在科学记数法十进制浮点数中,按十的幂进行缩放是微不足道的:我们仅更改指数。类似地在二进制浮点数中,按二的幂缩放也是如此简单。既然9是4.5的两倍,我们仅把指数加一。为了得到18我们再递增指数。每次有效位都保持不变1.001;只有指数发生改变。

十分奇怪的是,二进制浮点数在表示类似十分之一的数字时,是绝对令人感到惊骇的。用十进制时这非常容易:1.0e-1。然而在二进制中,十分之一是1个十六分之一(0.0675)加上1个三十二分之一(0.03125)加上0个六十四分之一(0.015625;这令我们到下一个)加0个1/128(0.0078125;继续到下一个)加1个1/256加1个1/512加0个1/1024,并继续,得到1.100110011001100…b-4作为它的二进制表示。序列‘1100’永远重复,相当类似三分之一的十进制形式3.33333…e-1,具有无穷个‘3’。(实际上很容易得知,任何不以数字5结尾的十进制小数都有这个问题。) 幸运的是整数值,至少对于‘足够小的’整数,总能用二进制浮点数确切表示。

注意,如果我们总是用‘规范化’格式书写二进制浮点数,不仅二进制小数点总是第二个字符,而且第一个字符总是一个‘1’。它表示我们不仅能省略用于二进制小数点的存储空间,也能省略用于第一个数字的存储。所以在计算机内部,数字1.1011b+4(它表示16+8+2+1或27)能恰好表示为二进制数字序列‘1011’和指数(+4)。因此,在IEEE二进制浮点数里,存储被分为两部分:一部分为尾数(这个术语现在的使用恰如其分,因为首位数字不再存储)一部分为指数。当然我们还有需要处理的讨厌的符号问题:尾数和指数都是有符号的,因为数字可能有这样的形式-1.1011b-4和+1.1011b+4。在这里使用的IEEE格式的技巧,略为少见:对于更老的计算机和整数,尾数用符号-大小格式存储;但是指数用一种‘额外的’格式。在这里,负数会加上一个偏差,让它们非负。

在不牵涉更多细节的情况下,这表示浮点数有三个部分(而非四个):一个位用于表示尾数的符号;一些固定位表示尾数本身;其余的位表示指数,用额外的格式。‘额外’依赖所余位数。例如,IEEE单精度是一个32位格式,其中1位表示尾数符号,23个位表示尾数,8位表示指数。因为八个无符号位能表示0到255,指数在逻辑上存储于‘超出128’格式。因为我未打算解释的理由,然而真正的额度是127,所以一个为1的指数值表示21-127,即是2-126。像我们将看到的,一个为0的指数被用于另一个用途。

因为我们使用规范化格式,23个用于尾数的位实际上存储24位有效值,加上隐含的前导‘1’位和二进制小数点。我们的数字总是正-负(根据尾数符号)1.一些数字,b,正-负,一些数字(校正的指数)。或者更容易理解,如果真正的尾数值是m,真正的指数(未校正的)为e,表示的值为1.m*2e-127(如果符号位置上则为负数)。

如果你注意到,或熟悉这个情况,现在你会知道一个问题。如果尾数总是一——点——一些数字,我们如何表示0?最好的情况是,我们使用一个最小的常规指数(未校正的值1,表示2-126)是1.000…000b-126,它大约是1.17549435e-38。因此,我们通过声称一些指数为‘特殊情况’从尾端窃取一些值。特别地在这个例子中,一个应该表示b-127的全0位指数,被用于两种特例。为了(或是错误的)对称,一个应该表示b+128的全1位指数,被用于另两种。

首两个特别的情况是‘零’和未规范化(或非常规化)数字:尾数是一个全0位的值和一个0指数表示0.0(或者-0.0,如果设置了符号位),然而一个有同样非零尾数位的数被视为‘非规范化’。这个数字表示为0.m*2e-126而不是1.m*2e-127(或者你喜欢,把二进制小数点向右移一位,把指数减至-127)。当然这里的e是零,所以这恰好是0.m*2-126(或者小数点位于第一个m之后m.m*2-127)。最小的非零单精度数字因此是0.00000000000000000000001b-126(二进制小数点后有22个零,其后是1),这是2-149,或约为1.4e-45。

最后两个特例是,一个全1位指数表示无穷(如果所有尾数位为零)和‘不是数字’或者‘NaN’(如果某些尾数位被置上)。作为一个有用的技巧,如果所有位被置上,指数在定义上即为全1,尾数明显至少有一些非零位(实际上全为非零),所以这是一个NaN。设置内存为全1以捕获一些对未初始变量的使用。

注意无穷数是有符号数——正无穷数大于所有其它数,负无穷数小于其余数——但是尽管NaN有一个符号位,它们却不被视为有符号数。并非每一个实现总能把这个弄正确。更复杂一点,NaNs被分为‘安静(Quiet)NaNs’和‘信号(Signaling)NaNs’,QNaNs用于计算时只会令结果变成另一个QNaN,然而SNaNs被用于在运行时捕获错误。一再地,并非每个实现都把这个做对了。

结果超出最大可表示值的运算,会被转换为正无穷数:例如1e38乘以1e1会溢出,所以会得到正无穷数。超出最小负数的负数同样溢出变成负无穷数(所以-1e38*1e1是负无穷数)。

对于一个大小为b+127的指数,单精度数字最大约为1e38。(确切的数字为340282346638528859811704183484516925440或约为3.4e+38,即是1.m*2e-127的值,当m是全1位,e等于254)。双精度数通常使用64位,分为1位符号位,52位尾数和11个指数位(存储额度为1023,因为210是1024)。更大的指数大约为1e308。扩展精度,如果有的话,在一些系统包括IA-32上使用80位,其它系统上使用128位。尾数和指数都进行扩展,指数通常有15位,其余位为尾数(不尽相同);最大的数字约是1e4932。英特尔IA-32体系结构浮点数单元较罕见,它们内部使用80位表示全部数字,在装载或存储时转换为32位或64位。但是有一些控制位以补偿额外的有效数字精度,对于额外的指数范围则没有。这表示一些会溢出的计算,实际上得出并非无穷数的答案。例如相乘两个双精度数字1e200和1e200会溢出,结果不是1e400。用1e300除这个结果(正无穷数)得到无穷数。在许多英特尔芯片上,导致这个发生的唯一途径,是把运算再存储至内存,它会减慢运算速度。C代码是这样的:

    double a = 1.0e200, r;
    r = a * a;
    r = r / 1.0e300;
    printf("%g\n", r);

它应该打印‘无穷数’,但是实际上打印‘1.0e100’,在许多英特尔机器上的C编译器上。(我们再次看到,得到错误答案非常重要——至少是IEEE关心的错误——尽可能快的。当然有人会争论,它明显是正确的答案。然而C和IEEE的运算规则,指出这个结果应该是无穷的。)


(This Chinese translation isn't confirmed by the author, and it isn't for profits.)

Translator : jhlicc@gmai1.c0m
Origin : http://www.torek.net/torek/c/numbers.html