CSAPP《深入理解计算机系统》深读笔记3——第二章-信息的表示和处理(下)
CSAPP《深入理解计算机系统》深读笔记3——第二章-信息的表示和处理(下)
你好我是拉依达,这是我秋招结束后更新的第一个系列。我将争取完成“ 年轻人,你渴望力量吗?”的全套深度笔记。
今天开始进行第一本CSAPP:深入理解计算机系统。
整数运算
无符号加法
字数膨胀: 两个非负整数x和y,满足0≤x,y<2w。每个数都能表示为w位无符号数字。然而,如果计算它们的和,我们就有一个可能的范围0≤x+y≤2w+1-2。表示这个和可能需要w+1位。发生“字长膨胀”,意味着,要想完整地表示算术运算的结果,我们不能对字长做任何限制。但是内存字数有限制。
让我们为参数x和y定义运算十,其中0≤x,y<2w,该操作是把整数和x+y截断为w位得到的结果,再把这个结果看做是一个无符号数。这可以被视为一种形式的模运算,对x十y的位级表示,简单丢弃任何权重大于2w-1的位就可以计算出和模2w。
比如,考虑一个4位数字表示,x=9和y=12的位表示分别为[1001]和[1100]。它们的和是21,5位的表示为[10101]。但是如果丢弃最高位,我们就得到[0101],也就是说,十进制值的5。这就和值21 mod 16=5一致。
展示了字长w=4的无符号加法函数的坐标图。这个和是按模24=16计算的。
- 当x+y<16时,没有溢出,并且x+y就是x+y。这对应于图中标记为“正常”的斜面。
- 当x+y≥16时,加法溢出,结果相当于从和中减去16。这对应于图中标记为“溢出”的斜面。
补码加法,我们必须确定当结果太大(为正)或者太小(为负)时,应该做些什么。给定在范围-2w-1≤x,y≤2w-1之内的整数值x和y,它们的和就在范围-2w≤x+y≤2w-2之内,要想准确表示,可能需要w+1位。就像以前一样,我们通过将表示截断到w位,来避免数据大小的不断扩张。
阐述了字长w=4的补码加法。运算数的范围为-8~7之间。
- 当x+y<-8时,补码加法就会负溢出,导致和增加了16。
- 当-8≤x+y<8时,加法就产生x+y。
- 当x十y≥8,加法就会正溢出,使得和减少了16。
这三种情况中的每一种都形成了图中的一个斜面。
补码非的计算,对每一位求反,再对结果加1。
### 无符号乘法范围在0≤x,y≤2w-1内的整数x和y可以被表示为w位的无符号数,但是它们的乘积x·y的取值范围为0到(2w-1)2=22w-2w+1+1之间。这可能需要2w位来表示。
C语言中的无符号乘法被定义为产生w位的值,就是2w位的整数乘积的低w位表示的值。我们将这个值表示为x以y。
将一个无符号数截断为w位等价于计算该值模2:
补码乘法
范围在-2w-1≤x,y≤2w-1-1内的整数x和y可以被表示为w位的补码数字,但是它们的乘积的取值范围为-2w-1 · (2w-1-1) 到-2w-1 · -2w-1之间。要想用补码来表示这个乘积,可能需要2w位。
C语言中的有符号乘法是通过将2位的乘积截断为v位来实现的。我们将这个数值表示为x * y。将一个补码数截断为w位相当于先计算该值模2w,再把无符号数转换为补码,得到:
补码乘法示意
乘以常数
大多数机器上,乘数乘法指令相当慢,而其他整数运算只需要1个时钟周期。
因此,编译器使用重要优化,使用移位和加法的组合代替乘以常数的的乘法。
假设一个程序包含表达式x14。利用14=23+22+21,编译器会将乘法重写为 (x<<3)+(x<<2)+(x<<1),将一个乘法替换为三个移位和两个加法。无论ⅹ是无符号的还是补码,甚至当乘法会导致溢出时,两个计算都会得到一样的结果。(根据整数运算的属性可以证明这一点。)
更好的是,编译器还可以利用属性14=24-21,将乘法重写为(x<<4)-(x<<1),这时只需要两个移位和一个减法。
除以2的幂
在大多数机器上,整数除法要比整数乘法更慢——需要30个或者更多的时钟周期。
除以2的幂也可以用右移实现。无符号和补码数分别使用逻辑移位和算术移位来达到目的。[[CSAPP/第二章-信息的表示和处理#C语言位移运算]]
- 除以2的幂的无符号除法: 移位总是舍入到零的结果,这一点与整数除法的规则一样。
- 除以2的幂的补码除法,向下舍入: 与逻辑右移是一样的。因此,对于非负数来说,算术右移k位与除以2是一样的。作为一个负数的例子,对于不需要舍入的情况(k=1),结果是x/2。但是当需要进行舍人时,移位导致结果向下舍入。
- 除以2的幂的补码除法,向上舍入: 在执行算术右移之前加上一个适当的偏置量是如何导致结果正确舍入的。对于需要舍入的情况,加上偏量导致较高的位加1,所以结果会向零舍入。
浮点数
浮点表示对形如V=x×2y的有理数进行编码。它对执行涉及非常大的数字( |V|>>0 )、非常接近于0 ( |V|<<1 )的数字,以及更普遍地作为实数运算的近似值的计算,是很有用的。
二进制小数
如bn bm-1 … b1 b0 . b-1 b-2 … b-n-1 b -n 的表示法,其中每个二进制数字,或者称为位,b1的取值范围是0和1,符号 ‘.’ 现在变为了二进制的点,点左边的位的权是2的正幂,点右边的位的权是2的负幂。
![[image/Pasted image 20231228132530.png|425]]
假定我们仅考虑有限长度的编码,小数的二进制表示法只能表示那些能够被写成x×2y的数。其他的值只能够被近似地表示。
例如,数字 1/5 可以用十进制小数0.20精确表示。不过,我们并不能把它准确地表示为一个二进制小数,我们只能近似地表示它,增加二进制表示的长度可以提高表示的精度:
IEEE浮点表示
电气和电子工程师协会(IEEE)推出的 IEEE754 标准。
IEEE标准从逻辑上用三元组{S,E,M}表示一个数N,如下图所示:
N的实际值n由下列式子表示:
- n,s,e,m分别为N,S,E,M对应的实际数值,而N,S,E,M仅仅是一串二进制位。
- S(sign)表示N的符号位。对应值s满足:n>0时,s=0; n<0时,s=1。
- E(exponent)表示N的指数位,位于S和M之间的若干位。对应值e值也可正可负。
- M(mantissa)表示N的尾数位,恰好,它位于N末尾。M也叫有效数字位(sinificand)、系数位(coefficient), 甚至被称作“小数”。
IEEE标准754规定了三种浮点数格式:单精度、双精度、扩展精度。前两者正好对应C语言里头的float、double。
- 单精度:N共32位,其中S占1位,E占8位,M占23位。
- 双精度:N共64位,其中S占1位,E占11位,M占52位。
M虽然是23位或者52位,但它们只是表示小数点之后的二进制位数,也就是说,假定 M为“010110011…”, 在二进制数值上其实是“.010110011…”。而事实上,标准规定小数点左边还有一个隐含位,这个隐含位绝大多数情况下是1。
计算 e,m:
- 规格化:当E的不全为0,也不全为1时,N为规格化形式。
此时e被解释为表示偏置(biased)形式的整数,单精度bias为127,双精度为1023,e值计算公式如下图所示:
标准规定此时小数点左侧的隐含位为1,那么m=|1.M|。
如M=“101”则|1.M|=|1.101|=1.625,即 m=1.625。
- ** 非规格化:当E的全部为0时,N为非规格化形式 **
此时e,m的计算都非常简单,此时小数点左侧的隐含位为0。
-
有了非规格化形式,我们就可以表示0了。把符号位S值1,其余所有位均置0后,我们得到了 -0.0; 同理,把所有位均置0,则得到 +0.0。
-
非规格化数还有其他用途,比如表示非常接近0的小数,而且这些小数均匀地接近0,称为“逐渐下溢(gradually underflow)”属性。
- ** 特殊数值: 当E的全为1时为特殊数值 **
- 若M的二进制位全为0,则n表示无穷大,若S为1则为负无穷大,若S为0则为正无穷大;
- 若M的二进制位不全为0时,表示NaN (Not a Number),表示这不是一个合法实数或无穷,或者该数未经初始化。
IEEE 浮点数例子:
我们假定N是一个8位浮点数,其中,S占1位,E占4位,M占3位。bias为7
舍入
因为表示方法限制了浮点数的范围和精度,所以浮点运算只能近似地表示实数运算。
IEEE规定了4种舍入方案: 向偶数舍入(向最接近的值舍入,默认方式)、向零舍入、向上舍入、向下舍入。
- 当舍入方式发生分歧时,优先采用向偶数舍入。
无论是10进制数,还是二进制数,只有在数值为中间值时,才会发生纠纷。
例如:
- 1.235,向上是 1.24;向下/向零 1.23。误差相同都是0.005。这时我们优先采用向偶数舍入,即1.24。
- 1.245,向上是 1.25;向下/向零 1.24。误差相同都是0.005。这时我们优先采用向偶数舍入,即1.24。
- 而1.234999,我们保留两位小数时,就没有必要纠结。向上/向偶 1.24 误差为0.0050001;向下/向零 1.23 误差为0.0049999.向下的误差最小,所以系统会采用1.23。
- 在比如 1.2350001,舍入到1.24的误差值要小于舍入到1.23的误差值,没必要纠结。
- 其余方式,向最近的值舍入。
为什么要在纠结的时候采用向偶数舍入?
采用向上舍入一组数值,会在计算这些值得平均数中引入统计偏差。
我们采用这些方式舍入得到的一组数的平均值将比这些数本身的平均值略高一些。相反,采用向下舍入一组数值,得到的平均值会比本身的平均值略低一些。
向偶数舍入在大多数现实情况中避免了这种统计偏差。因为在50%的时间内,他将向上舍入;在50%时间内,他将向下舍入。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!