CSAPP(一):数字的计算机表示

  在计算机中，使用位来存储信息。相同的位级表示，改变其解释方式，则表达出不同的信息。

0.位级运算中的异或

    位级运算中需要注意的是异或这个运算，x^y异或的含义是：对于第i位，x，y在i位上的值不同时，结果为1；这意味着，在第i位上，x，y有且仅有一个1时，结果为1；有且仅有一个0时，结果为1；两者的值相同时，结果为0；异或的变化及其灵活：1）x^y = x|y – x&y;2） x^y = x&~y | ~x&y;  3）x^00..00=x;  x^11..11=~x;所以我们可以在全0或全1的位向量里插入一两个1或0，来改变x或~x中的一两位； （别的变化再补充）。

一、无符号整数及编码

    位向量x=[x_w-1,...,x₀],用它来表示一个无符号整数，则整数值为：

                                                 B2U_w(x)=∑x_i2ⁱ; (i=0 to w-1)

    B2U 即Binary to Unsigned，此函数将一个长度为w的0、1串映射为非负整数。其中位向量x能表示的非负整数范围是[0, 2^w-1]；这种编码方式下文称之为“无符号编码”。

二、无符号编码VS补码： 模运算

    无符号编码正如其名称所示，只能编码无符号数(非负数)；那么，如何表示有符号整数呢? 我们可以用位向量的最高位表示符号位:0表示正数，1表示负数，其余各位表示数值本身，这种编码方式称为原码（Sign-Magnitude），对于位向量x，其整数值为:

     这么做有两个问题：

    1）[100] 和 [000]都表示0，即：有正0和负0之分；

    2）当计算机进行加减运算的时候，符号位不能参加运算，这样会使得计算机系统变得复杂。

    为了解决这两个问题，尤其是问题2，引进了补码。什么是补码？这还得从计算机的特性说起：

    对于无符号编码，位向量x（这里令w=3）的所有位都是1，那么此时它表示的无符号整数值是：2³-1=7， 此时此整数值再加1，会发生什么？整数值变为8。8的位级表示是[1000]，但是x只有3位，所以x=[000], 其整数值为0！！这意味着计算机中的整数运算都是取模运算。对于x来说，当其表示整数值大于2^w-1时，将自动舍去一个2w，即：对于无符号整数x，其位向量x等同于无符号整数（x mod 2^w）的位向量。譬如时钟，现在钟表是3点整，若想将其调成1点，可以倒拨2小时（减法）；也可以正拨10小时（加法；（3+10） mod 12 =1）。

    以w=3为例，1+（-1）=1+（-1 mod 8）= 1+7 =[001]+[111]= [000] =0.

    我们可以使用[111]来表示-1，使得符号位参与运算。化有符号运算为“无符号运算”的关键是：利用mod特性，将有符号的负整数转化为无符号的正整数：-x（x为正数）对应无符号整数等于2^w-x。这样就解决了原码的两个问题：

    1）对于0，-0=2^w-0=2^w，w位的位向量x无法表示-0，即：在补码中没有-0；

    2）既然有符号数转化为了无符号数，那么“符号位”自然可以参加运算了。

三、有符号整数及补码

    那么补码的数学特性是什么呢？位向量x=[x_w-1,...,x₀],用它来表示一个有符号整数，则整数值为：

                                    B2T_w(x)=-x_w-12^w-1+∑x_i2ⁱ; (i=0 to w-2)

    B2T 即Binary to Two's-complement，此函数将一个长度为w的0、1串映射为有符号整数。其中位向量x能表示的整数范围是[-2^w-1, 2^w-1]；

四、有符号数与无符号数之间的转换

    对于位向量x，使用无符号编码得到的数值，与使用补码得到的数值完全不同。然而，位向量x的位级表示并没有发生变化。这样，就引出了一个问题；位向量x表示的无符号整数值位u，将其转换为有符号整数t，则t为多少？

   将无符号数转换为有符号数（Unsigned to Two’s-complement），这个过程要用位向量x做媒介，因为x是不变的。已知无符号数x，我们可以假设其位向量为x，则有

    当x<2^w-1时，则有x_w-1=0，当x>=2^w-1，有x_w-1=1,所以：

    类似的：

    如下图所示：

    当使用C语言时，尤其是涉及比较大小和数学运算时，混用有符号数和无符号数时，C语言会将有符号数隐式地转换为无符号数，这很容易会导致错误或程序漏洞。因此，建议绝不使用无符号！！！使用无符号数时仅仅将其作为位向量使用。

    （关于整数的截断和扩展，有一点需要注意：先改变大小，再改变符号。）

五、整数运算（1）：加法

    假设x与y都是w位的位向量，计算机的整数运算，最重要的特性是模运算特性。

    对于无符号整数，很容易有以下公式：

    当执行C程序时，不会将溢出作为错误而发出信号。我们如何得知是否发生了溢出？假设s=x+y;如果发生了溢出，则有s=x+y-2^w,x,y<2^w,所以有s<x(等价的s<y)。（注意：此方法仅仅针对无符号运算）

    对于补码加法，有如下推导（在已知无符号运算的基础上，下面所有的补码运算都是在相应的无符号运算的基础上推导）：

    根据令z=(x+y) mod 2w,可将x+y分成[-2^w, 0)和[0,2^w-1)两个部分；根据U2T函数的分段特性，又可以将z分成[0, 2^w-1)和[2^w-1,2^w)两部分，所以：

    当执行C程序时，如何得知是否发生了溢出？当x和y都是负数，结果是非负数（包含0），那么就是负溢出；如果x和y都是非负数，结果是负数，那么就是正溢出。

    提到加法，与之关联的减法：x-y=x+(-y);所以对于x，我们经常需要求其加法逆元。对于x不等于-2^w-1,其加法逆元是-x；对于x=-2^w-1,-x并不能用一个w位的向量来表示，所以其逆元正是其本身，因为，此时2x=2^w =2^w mod 2^w=0：

    那么，在位级上怎么求解呢？即：对于补码来说，已知x及其w位的位向量x，值-x对应的位向量y是什么？根据我们对于补码的模特性可知，我们可将有符号数转化位无符号数（根据第二节内容）进行表示。如果x是[0, 2^w-1-1]，根据T2U公式，那么-x=2^w-x=(2^w-1)+1-x, y=[11..11]+[00..01]-x; 对于x是[-2^w-1,0）,根据T2U公式，那么-x=2^w-(x+2^w)=0-x,y=[00..00]-x;无论是11..11]+[00..00]-x 还是[00..00]-x,他们都是等于将x每一位取反然后对结果加1。

六、整数运算（2）：乘法

    对于无符号乘法，有 x*y=(x*y) mod 2^w。

    对于补码乘法，有：

   我们可以得知：无符号乘法和补码乘法的低位时相同的（上式第二行和第四行）。

    如何判断乘法是否溢出？对于p=x*y,如果有x等于0（y等于0）,或者p/x==y则没有溢出（练习题2.35).

   当编译器进行乘法的时候，会试着使用移位和加法运算来代替乘以常数因子的乘法。对于x*k，首先将常数K表达为一组0和1交替的序列：[(0…0)(1…1)(0…0)…(1…1)]。例如14可以写成[(0..0)(111)(0)]。考虑一组从位位置n到位位置m的连续的1（对于14，n=3，m=1），我们可以有：

    1）(x<<n)+(x<<n-1)+…+(x<<m);

    2) (x<<n+1)-(x<<m);

    关于移位：对于c语言来说，移动k位，但是k>=w,会出现什么结果？注意：C语言标准规避了说明这种情况下怎么做。所以如果32位的x需要左移32位怎么办？可以(x>>31)>>1：将移位数k拆解成几个小于w的数。

   进行除以2的幂常数时，可以通过右移来代替，然而计算机进行右移时，会导致向下舍入，例如：-7/2会得到-4。然而，规则要求我们向零舍入，即-7/2应该等于-3。如何实现呢？我们可以在移位之间偏置（biasing）这个值，即（x<0? (x+(1<<k)-1) : x)>>k;  这种用右移代替除法的方法并不能推广到除以任意常数。

七、浮点数规则

    浮点表示对形如V=x*2^y 的有理数进行编码，它对执行涉及非常大的数字（|V|>>0）、非常接近于0（|V|<<1）的数字，以及更普遍地作为实数运算的近似值的计算，是很有用的。小数的二进制表示法只能表示那些能够写成x*2^y 的数，其他的值只能够近似地表示。

    IEEE浮点标准用V=(-1)^s * M * 2^E的形式来表示一个数：

其中s是符号位（sign）；尾数（significand）：M是一个二进制小数，范围是[1,2)或者[0,1); 阶码（exponent）：E的作用是对浮点数加权。如下图所示：最高位是符号位，中间段是阶码段，最后一段是尾数段。

浮点数分为三种情况：1.规格化的值，2.非规格化的值，3.特殊值

Case1：规格化的值

   中间的阶码段（exp）的位模式既不全是0，也不全是1时。此时，阶码段被解释为以偏置形式表示的有符号整数，即：E=e-Bias, 其中e是由阶码段表示的无符号数，Bias=2^k-1-1，所以，对于k（阶码段的位数）=8来说，E的取值范围是-126~127（因为阶码段不等于0也不等于255）；

    小数段f有0<=f<1,其小数点在f段最高有效位的左边，，尾数M=1+f；

Case2： 非规格化的值

当阶码段全为0时，表示非规格化的值。此时阶码值为E=1-Bias，而尾数值M=f;非规格化数有两个用途：1）提供了一种表示数值0的方法，（IEEE标准）有正0负0之分；2）表示那些非常接近于0的数，它们提供了一种属性，称为逐渐溢出（gradual underflow）。

Case3： 特殊值

此时阶码值全为1.当小数域全为0时，得到的值表示无穷；当小数域为非零，结果值称为“NaN”。

  1.注意非规格化的数阶码值是E=1-Bias而不是-Bias，以单精度为例，最小的规格化数的E=-126，M=1.0；最大的非规格化数E=-126（所以的非规格化数都是如此），M是[0.11..11]2。正是非规格化数的E的定义，实现了最大非规格化数到最小规格化数的平滑转变；

    2.上图的位表达式解释为无符号整数的话，他们就是按升序排列，就像它们表示的浮点数一样，这并不是偶然，IEEE如此设计就是为了浮点数能够使用整数排序函数进行排序。当然负数要进行额外处理。

几点结论（k个阶码位，n个小数位）：

    1.最小的正非规格化值的位表示（除零之外），尾数位最低有效位为1，其余全为0，具有M=f=2^-n，和 E=2-2^k-1；

    2.最大的非规格化数，尾数位全为1，具有M=f=1-2^-n，和E=2-2^k-1；

    3.最小规格化数，阶码位最低有效位为1，其余全为0；尾数位全为0，具有M=1,E=2-2^k-1;

    4.值1.0的位表示，阶码位最高有效位为0，其余全为1；尾数位全为0，具有M=1，E=0；

    5.最大规格化数，阶码位最低有效位为0，其余全为1；尾数位全为1，具有M=2-2^-n,E=2^k-1-1.

八、浮点数的一些说明

   舍入，因为浮点数只能近似的表示实数运算，所以哦我们想用一种系统的方法，能够找到“最接近的”匹配值，IEEE定义了四种舍入方式，向偶数舍入，向零舍入，向上舍入，向下舍入。

    浮点加法不具有结合性。（3.14+le10）-1e10得到0.0，而3.14+(1e10-1e10)得3.14。对于科学计算程序员来说，缺乏结合性和分配性是很严重的问题，即使是为了在三维空间中确定两条线是否交叉而写代码这样看上去很简单的任务，也可能成为很大的挑战。

    将大的浮点数转换成整数是一种常见的程序错误来源。在C语言中，这样会导致向0舍入。