第二章 信息的表示和处理
1 信息存储
·大多数计算机使用8位的块，或者字节（byte），作为最小的可寻址的内存单位，而不是访问内存中单独的位。
·机器级程序将内存视为一个非常大的字节数组，称为虚拟内存。内存的每个字节都由一个唯一的数字来标识，称为它的地址，所有可能地址的集合称为虚拟地址空间。（只是一个展现给机器级程序的概念性映像）
2 简单概念
1）十六进制（0x，0X）
2）字数据大小
每台计算机都有一个字长，指明指针数据的标称大小。因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。如某机器字长为w位，虚拟地址的范围为0~(2^w)-1（32位程序和64位程序区别：在于该程序时如何编译的，而不是其运行的机器类型）
3）寻址和字节顺序
·对象的地址以及如何排列
·例如：假设一个类型的int型的变量 x的地址为0x100，则x的（4）个字节将被存储在内存中的位置。
·小端法：最低有效字节在最前面的方式
·大端法：最高有效字节在最前面的方式
（二进制代码不兼容）
4）c语言中的运算
位级运算
逻辑运算
移位运算：机器支持两种形式的右移，即逻辑右移和算术右移。
逻辑右移：在左端补k个零。
算术右移：在左端补k个最高有效位的值。
（注：几乎所有的编译器/机器组合都对有符号数使用算术右移。对于无符号数，必须采用逻辑右移。）
3 整数表示
用位来编码整数的两种方式：一种只能表示非负数，而另一种能够表示负数，零和正数。负数的范围比正数的范围大一。
1）无符号数的编码
11--->[1011]; 双射；双向编码唯一性；
2）补码编码
最常见的有符号数的计算机表示方式就是补码，将字的最高有效位解释为负权。
B2T4([1011])=(-1)*2^3+0*2^2+1*2^1+1*2^0;
范围：-2^（w-1）~2^(w-1)-1;
双射，补码编码唯一性。
注：-1与Umax有同样的位表示----一个全1的串。数值0在两种表示方法中都是全0的串。
3）有符号数和无符号数之间的转换
强制类型转换的结果保持位值不变，只是改变了解释这些位的方式。即在c语言中，处理同样字长的有符号数和无符号数之间相互转换的一般规则是：数值可能会改变，但是位模式不改变。
1 原理：补码转换为无符号数：
对满足TMin<=x<=TMax的x有：T2Uw（x）={x+2^w,x<0},{x,x>=0};
（负数就被转换为了大的正数，而非负数会保持不变。）
2 原理：无符号数转换为补码：
对满足0<=u<=UMax的u有：
U2Tw(u)={u,u<=TMax},{u-2^w,u>TMax};
(对于小的数，从无符号数到有符号数的转换将保留数字的原值。对于大的数，数字将被转换为一个负值。)
4）c语言中的有符号数与无符号数
几乎所有的机器都使用补码，转换时大多数系统遵循的原则是底层的位保持不变。
c语言对同时包含有符号和无符号数表达式的处理方式：
当执行一个运算时，如果它的一个运算数是有符号的而另一个是无符号的，那么c语言会隐式地将有符号参数强制类型转换为无符号数，并假设这两个数都是非负的，来执行这个运算。
5）扩展一个数字的位表示
1 无符号数的零扩展
要将一个无符号数转换成一个更大的数据类型，只要简单地在表示的开头添加0，这种运算称为零扩展。
2 补码数的符号扩展
要将一个补码数转换成一个更大的数据类型，可以执行符号扩展，在表示中添加最高有效位的值。
注：c语言标准要求的规则：
从一个数据大小到另一个数据大小的转换，以及无符号和有符号数字之间的转换的相对顺序能够影响一个程序的行为。
例：当把short转换成unsigned时，我们先要改变大小，之后再完成从有符号到无符号的转换。也就是说
（unsigned）sx 等价于（unsigned)(int)sx，再求值。
6）截断数字
截断一个数字可能会影响它的值-----溢出的一种形式。
1 截断无符号数
x ：[Xw-1,Xw-2,……X0] ,x1表示x截断为k位的结果，则x1 :[Xk-1,Xk-2,……,X0]。则它们所表示的无符号值大小关系为：x1=x mod2^k。
2 截断补码数值
也具有相同的属性，只不过要将最高位转换为符号位。
x ：[Xw-1,Xw-2,……X0] ,x1表示x截断为k位的结果，则x1 :[Xk-1,Xk-2,……,X0]。x=B2Uw(x),x1=B2Tk(x1),则x1=U2Tk(x mod 2^k)；
例：将数值 x=53191从 int 转换为 short，由于2^16=65536>=x，所以有 x mod2^16 =x。第二步，把这个数转换为16位补码，
得到x2=53191-65536=(-)12345。
7）整数运算
1 无符号数加法
简单丢弃2^(w-1)位就可以计算出模2^w。
算术运算溢出：指完整的整数结果不能放到数据类型的字长限制中去。
x+y=【x+y或者x+y-2^w；（取决于有无溢出，溢出丢弃）】
检测有无溢出：结果小于其中一个加数
无符号数取反：-x=[x或者2^w-x];取决于x是否为0
2 补码加法
x+y=【x+y-2^w;x+y;x+y+2^w】(正溢出，正常，负溢出)
正溢出：x+y超过TMax。负溢出：x+y小于TMin。
检测有无溢出：x>0,y>0,s<0。或x<0,y<0,s>=0。
补码的非：对w位的补码加法；来说，TMin是自己的加法的逆，而对于其他任何数值，x都有-x作为其加法的逆。
3 无符号乘法
c语言中的无符号乘法被定义为产生w位的值，就是2w位的整数乘积的低w位来表示的值。
将一个无符号数截断为w位等价于计算该值模2^w。
x*y=（x*y）mod 2^w。
4 补码乘法
将一个补码说截断为w位相当于先计算该值，模2^w,再把无符号数转换为补码。
x*y=U2Tw【（x*y）mod 2^w】。
5 乘以常数
整数乘法指令相当慢，需要10个或者更多个时钟周期，然而其他整数运算（加法，减法，位级运算和移位）只需要一个时钟周期。因此，编译器使用了一项重要的优化，即试着用移位和加法运算组成的组合来代替乘以常数因子的乘法。
左移一个数值等价于执行一个与2的幂相乘的无符号乘法。补码乘法类似。
例：x*14 因为14=2^3+2^2+2^1，所以编译器会把乘法写为 （x<<3+x<<2+x<<1）,将一个乘法替换为三个移位和两个加法。
或者14=2^4-2^1，所以 x<<4-x<<1.两个移位和一个减法。
6 除以2的幂
整数除法要比整数乘法更慢-----需要30个或者更多的时钟周期。
除以2的幂，用右移。
1 无符号除法 x>>k（逻辑移位）,产生的数值左趋近。
2 补码除法x>>k（算术移位），向下舍入。或者（x+(1<<k)-1）>>k 产生数值向上舍入。第二种方法相当于在执行算术右移之前加上一个适当的偏置量会导致结果正确舍入。
8）浮点数运算
1 二进制小数表示
2 浮点数表示
用V=（-1）^s * M * 2^E的形式表示一个数。
符号位：s决定是负数（s=1）还是正数（s=0）。
尾数：M是一个二进制小数，它的范围是1~2或者0~1。
阶码：E的作用是对浮点数加权，这个权重是2的E次幂。
即将浮点数的位表示划分为三个字段，分别对这些值进行编码：
·一个单独的符号位s直接编码符号s。
·k位的阶码字段exp=……编码E。
·n位小数字段frac=……编码尾数M，但是编码出来的值也依赖于阶码字段的值是否为0.
注：单精度float中，s、exp、frac字段分别为1位，k为8位，和n为23位，得到了32位的表示。
注：双精度double中，s、exp、frac字段分别为1位，k为11位，和n为52位，得到了64位的表示。
三种情况：
1、 规格化的值
最普遍情况。当exp的位模式既不全为0，也不全为1,。在这种情况中，阶码字段被解释为以偏置形式表示的有符号整数，也就是说，阶码的值是
E=e-Bias，其中e是无符号数，其位表示为ek-1ek-2……e0,而Bias是一个等于2^(k-1)-1的偏置值，（127or1023）。
小数字段frac被解释为f，尾数定义为M=1+f。即隐含的以1开头的表示。这种表示方法，是一种轻松的获得一个额外精度的技巧。既然第一位总是1，那么我们就不需要显式的表示它。
2、 非规格化的值
当阶码域为全0时，所表示的数是非规格化形式。阶码值是E=1-Bias，而尾数的值是M=f，也就是小数字段的值，不包含隐式地开头的1。
两个功能：表示0和那些非常接近0的数。
3、特殊值
最后一类数值是阶码全为1的时候出现的。当小数域全为0时，得到的值表示无穷。当小数域为非零时，结果值被称为“NaN”，即“不是一个数”。
3 舍入
因为表示方法限制了浮点数范围与精度，所以浮点运算只能近似地表示实数运算。
关键问题是在两个可能值的中间确定舍入方向。
向偶数舍入，即向最近的值舍入，是默认的方式。向偶数舍入的方式采用的方法是：它将数字向上或者向下舍入，使得结果的最低有效数字是偶数。这种方法将1.5和2.5都舍入为2，避免了一定的统计误差。向0舍入方式是把正数向下舍入，把负数向上舍入。向下舍入，向上舍入。
4 浮点数运算
运算不可结合。
浮点加法不具有结合性。满足单调性。满足交换律
浮点乘法可交换，不具有可结合性。浮点乘法在加法上不具备分配性。
例：使用单精度浮点，表达式（3.14+le10）-le10求值得到0.0。（因为舍入，值3.14会丢失）另一方面，表达式3.14+（le10-le10）得出值3.14。
例：单精度浮点情况：表达式 le20*(le20-le20)求值为0.0,而le20*le20-le20*le20会得到NaN。
[第二章完]
