CSAPP-信息的表示和处理

编程/技术 更新时间: 2019-08-10 @ 16:19:53 创建时间: 2019-08-06 @ 08:10:32 浏览数: 247 净访问: 181 By: skyrover

本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议


信息存储

大多数计算机使用字节(8位的块)作为最小的可寻址的存储器单位,机器级程序将存储器视为一个非常大的字节数组,称为虚拟存储器,每个字节都有它的地址,地址的集合称为虚拟地址空间。

十六进制表示法(hexadecimal)

这个没啥说的,比较简单,二进制的4位表示十六进制的一位。书中介绍了一种特殊情况下的快速将二进制转换成十六进制的方法:

对于x=2^n,n可以表示为n=i+4*j,所以十六进制就可以表示为0x(2^i)(0)其中0的个数是j个,比如x=2048=2^11,其中11=3+4*2,所以十六进制就是0x800

原理就是x的二进制表示是1后面跟n个0,然后4个0就是十六进制的一个0,剩下的高位,可能有0,2,4,8,然后组合起来就是十六进制。

十进制到十六进制的转换,类似二进制。

每台计算机都有字长,表示整数和指针数据的标称大小,比如一个虚拟地址的长度,决定字长的参数最重要就是虚拟地址空间的最大大小,即存储器容量。

寻址和字节顺序

大端和小端的问题,大端就是高字节在低位,方便阅读(数据的排列和内存地址排列都是从小到大,所以方便阅读)。小端是低字节在低位,方便CPU处理。一般来说网络字节序是大端的,计算机内部是小端的。

表示字符串

C语言中字符串被编码为一个以null(值为0)字符结尾的字符数组,每个字符由某种编码表示。比如一个字符串"12345"的字节序列为:31 32 33 34 35 00

表示代码

相同代码在不同平台,不同机器类型转换为二进制指令是不同的,因为有不同的指令和编码方式。所以在不同平台上需要编译出来不同的二进制代码。

布尔代数

这里有一个有意思的就是通过位向量来表示有限集合,比如01101001来表示集合A={0, 3, 5, 6},通过位向量对集合编码的例子有,信号处理,指定一个向量掩码,位为1表示信号i有效,否则就是屏蔽的,所以这个位向量掩码就表示有效信号的集合。

C语言中的移位运算

左移没问题,但是右移会有两种,一种是逻辑右移,逻辑右移直接在左端补0,另一种是算术右移,是往左端补k个最高有效位的值。

无符号数右移是逻辑右移,有符号数两种都有可能,一般认为是算术右移。

整数表示

无符号数的编码

通过位向量表示到整数的映射(B2U,Binary to Unsigned),最小值是[00..0],最大值是[11..1],对应整数值为0,和2^w-1

补码编码

用补码表示负数,最高位为符号位,所以公式里最高位的权为负权,位向量的函数表示(B2T,Binary to Two's-complement)就是

也就是其他位按照正权加起来之和减去最高位的2^w-1

表示范围:最小值是[10..0],也就是设置负权,但是清除其他所有位,那么最小值是-2^(w-1),最大值是[01..1],清除负权位,设置其他所有位,最大值是2^(w-1)-1(少一位表示数据)

所以补码的范围不是对称的,对应正数是没有2^(w-1)的,因为0是[00..0]来表示的,所以正数这边就会少一个。

最大的无符号数比补码最大值两倍大一,也就是UMax = 2TMax + 1,补码中-1表示为11..11

  • 反码,最高位的权是-(2^(w-1) - 1)
  • 原码,最高位是符号位,(-1)^(x[w-1])

有符号数和无符号数之间的转换

根据上面补码和无符号数编码的定义,可以得到:

最后可以得到

因为x[w-1]决定了x是否为负(最高位),所以

从这里看到将补码映射到无符号数的规则:非负数保持不变,负数转成大的正数(负数加上2^w

反过来可以得到无符号数u和对应的有符号数U2T之间的关系:

推导过程和之前一样,只不过减法的减数被减数调个个,最后得到U2T的结果,鉴于无符号数的最高位为1的时候,无符号数是>=2^(w-1),最高位为0,无符号数<2^(w-1),所以得到上面的式子

可以看到对于小的数,无符号到有符号的转换将保留数字原值。大的数会被转换为一个负值。对于0<=x<2^(w-1)范围的值,两者转换保持不变,而对于之外的数值,需要加上或者减去2^w。对于最小的负数:

最小的负数会映射到一个刚好在补码正数范围之外的无符号数

扩展一个数字的位表示

分为两种:

  • 零扩展:将一个无符号数转换成一个更大的数据类型,只需要在开头加0就行
  • 符号扩展:将一个补码数字转换位一个更大的数据类型,规则是在表示中添加最高有效位的值的副本

整数运算

无符号加法

对于两个整数x,y,满足0<=x, y<=2^w-1,那么它们的和,就是0<=x+y<=2^(w+1)-2,所以需要w+1位来表示,超过了其位数范围,所以无符号加法等价于计算和模上2^w,即可以简单的丢弃x+y的w+1位表示的最高位。即:

补码加法

这一节看上去让人生畏啊,不过详细看一遍也挺简单的。

给定范围在-2^(w-1) <= x, y <= 2^(w-1)-1之内的整数值x和y,和的范围在-2^w <= x+y <= 2^w-2之间,所以需要w+1位,就会有溢出的可能,然后将数截断到w位。

因为大多数计算机使用同样的机器指令来执行无符号或者有符号的加法,所以可以表示为下面:

下面分成了四种情况讨论,并且让z=x+y, z'=z mod 2^w, z''=U2T(z')

  • -2^w <= z < -2^(w-1) 注意这里z=x+y所以范围扩大了,所以z'=z+2^w,那么0<= z' < 2^(w-1),根据无符号转补码公式,可以得到z''=z',所以可知z''=x+y+2^w,这种情况就是负溢出

  • -2^(w-1) <= z < 0 同样,z'=z+2^w,所以2^(w-1) <= z' < 2^w,根据无符号转补码,z''=z'-2^w,所以z''=x+y

  • 0 <= z < 2^w, 这时候z'=z,所以0<=z'<2^(w-1),所以z''=z'=z,所以z''=x+y

  • 2^(w-1) <= z < 2^w,所以z'=z,所以z''=z'-2^w,所以z''=x+y-2^w,这种情况是正溢出

总结一下就是下面的式子

也就是如果两个负数相加得到了正数,就是发生了负溢出。两个正数相加得到了负数,就发生了正溢出。

补码的非

-2^(w-1) <= x < 2^(w-1)都有其加法逆元,对于x!=-2^(w-1),加法逆元就是-x,而对于x=-2^(w-1)没有对应的值,因为2^(w-1)不能表示为w位的数。所以声明这个特殊的值本身就是其加法逆元,因为-2^(w-1)+-2^(w-1)=-2^w,而这种情况正好是负溢出,所以-2^w+2^w=0,因此补码的非运算如下:

无符号乘法

数的范围为0<=x, y <= 2^w-1,乘法结果最大可能需要2w位来表示,但是C语言中无符号乘法定义为产生w位的值,所以需要最后结果上模2^w,即:

补码乘法

对于无符号和补码乘法来说,乘法运算的位级表示都是一样的,所以机器可以使用一种乘法指令来进行有符号和无符号整数的乘法。下面是证明的过程:

乘以常数

整数乘法指令比较慢,所以编译器考虑使用移位和加法组合代替乘以常数因子的乘法。

对于乘以2^k的情况,也就相当于左移k位,即使溢出,通过移位得到的结果都是一样的。另外可以通过移位和加法减法来消除整数乘以常数的情况。比如x*14可以替换为(x<<3)+(x<<2)+(x<<1),因为x*14=x*(2^3)+x*(2^2)+x*(2^1)

除以2的幂

整数除法更慢,所以除以2的幂也可以用移位运算来进行,无符号和补码数分别使用逻辑右移和算术右移。

整数除法总是舍入到0,比如3.14->3, -3.14->-4,无符号数可以用右移进行运算证明如下:

对于补码的负数情况,如果需要舍入,移位会导致向下舍入,而不是向0舍入,表达式-7/2应该是-3,而不是-4

下面是补码的证明过程,和上面类似,所以最后结果是会向下舍入。

为了得到负数情况下向上舍入,需要在移位之前偏置,偏置原理是:

对于C语言就是:(x<0 ? (x + (1<<k) - 1) : x) >> k

浮点数

二进制小数

定点小数法 0.0011 -> 2^-3 + 2^-4 -> 3/16

IEEE 浮点表示

通过给定x和y的值,来表示形如x * 2^y的数,IEEE浮点标准用V = (-1)^s * M * 2^E来表示一个数

  • s:符号,决定为整数还是负数,1位直接编码
  • M:尾数,二进制小数,范围是1~2-e,n位
  • E:阶码,可能是负数,k位

单精度中符号位1位,阶码8位,尾数23位,双精度中符号位1位,阶码11位,尾数52位

根据exp阶码的值,被编码的值可以分为三种情况:

  • 规格化的值

阶码不全为0,也不全为1,阶码字段被解释位以偏置形式表示的有符号整数,E=e-Bias,e是无符号数,而Bias位2^(k-1)-1,通过这样产生指数的取值范围,单精度就是1-(2^(8-1)-1)=-126~254-(2^(8-1)-1)=127,即-126~127

尾数字段里,0<=f<1,尾数定义为1+f,这种方式就是隐含的以1开头的表示,因为第一位总是等于1,因此就不需要显式表示它

  • 非规格化的值

当阶码全0的时候,就是非规格化形式,阶码值是E=1-Bias,尾数值是M=f,非规格化数第一个提供了表示数值0的方法,第二个是表示非常接近于0.0的数,提供了一种属性,逐渐溢出,可能的数值分布均匀的接近于0.0

设定阶码值为1-Bias可以补偿非规格化数的尾数没有隐含的开头的1

  • 特殊值

阶码全为1的时候出现,当尾数全为0,表示无穷,通过符号位确定是正无穷还是负无穷。当尾数非0的时候,值为NaN。

下面是个实际的例子

舍入

IEEE浮点格式定义了四种不同的舍入方式(对于两个可能值的中间),默认方式是找到最接近的匹配,即向偶数舍入,其他三种可用于计算上界和下界

将数字向上或者向下舍入,使得结果的最低有效数字是偶数。十进制中中间位置是5,而二进制不同,只有在xx.yy100这样的二进制位模式的数才有效,最右边的y是要舍入的位置,比如10.10100,向下舍入到10.10,小数部分是5/8->1/25/81/26/8(11000)的中间值


点赞走一波😏


评论

提交评论