2.1 信息存储 2016 年 3 月 3 日 9:32 1. 把位组合在一起, 再加上某种解释, 即给不同的可能位模式赋予含义, 我们就能够表示任何有限集合的元素 2. 无符号编码基于传统的二进制表示法, 表示大于或者等于零的数字 ; 补码编码是表示有符号整数的最常见的方式, 有符号整数就是可以

Size: px

Start display at page:

Download "2.1 信息存储 2016 年 3 月 3 日 9:32 1. 把位组合在一起, 再加上某种解释, 即给不同的可能位模式赋予含义, 我们就能够表示任何有限集合的元素 2. 无符号编码基于传统的二进制表示法, 表示大于或者等于零的数字 ; 补码编码是表示有符号整数的最常见的方式, 有符号整数就是可以"

谓墩高
7 years ago
Views:

1 2 信息的表示和处理 2016 年 3 月 3 日 8:29 现代计算机存储和处理的信息以二值信号表示相比其他进制, 二值信号能够很容易的被表示存储和传输对二值信号进行存储和执行计算的电子电路非常简单和可靠给不同的可能位模式赋予含义 ( 解释 ), 就能够表示任何有限集合的元素无符号 (unsigned) 编码表示 0 和正整数 ; 补码 (two's-complement) 编码表示有符号整数 ; 浮点数 (floating-point) 编码表示实数的科学计数法的以二为基数的版本 ; 计算机用这些不同的表示方式实现算术运算 C 标准演化 1. 贝尔实验室 C 2. ANSI C 3. ISO C89( 也称 ISO C90, 与 ANSI C 基本一致 ) 4. ISO C99 5. GNU 99( 结合 C99 及其他一些特性, 尚未完成 ) 计算机的表示法使用有限数量的位对一个数字编码, 如果在此基础上进行的运算不能封闭的话, 某些运算可能会溢出 (overflow) 整数运算和浮点数运算会有不同的数学属性是因为它们处理数字表示有限性的方式不同 : 整数表示虽然只能编码一个相对较小的数值范围, 但这种数值是精确的 ; 浮点数表示虽然可以编码一个较大的数值范围, 但这种表示只是近似的, 并且由于舍入的策略, 会导致更多非直观的数学属性大量计算机的安全漏洞都是由于计算机算术运算的微妙细节引发的分区深入理解计算机系统笔记的第 1 页

2 2.1 信息存储 2016 年 3 月 3 日 9:32 1. 把位组合在一起, 再加上某种解释, 即给不同的可能位模式赋予含义, 我们就能够表示任何有限集合的元素 2. 无符号编码基于传统的二进制表示法, 表示大于或者等于零的数字 ; 补码编码是表示有符号整数的最常见的方式, 有符号整数就是可以为正或负的数字 ; 浮点数编码是表示实数的科学计数法的以二为基数的版本 3. 计算机的表示法是用有限数量的位来对一个数字编码, 当结果太大以致不能表示时, 某些运算就会溢出 4. 浮点运算又完全不同的数学属性, 由于表示的精度有限, 浮点运算是不可结合的整数运算和浮点运算有着不同的数学属性是因为它们处理数字表示的有限性的方式不同整数的表示虽然只能编码一个相对较小的数值范围, 但这种表示是精确的 ; 而浮点数虽然可以编码一个较大的数值范围, 但是这种表示只是近似的 5. 大多数计算机使用 8 位的块 ( 即字节 ), 作为最小的可寻址的存储器单位, 而不是在存储器中访问单独的位机器级程序将存储器视为一个非常大的字节数组, 成为虚拟存储器存储器的每个字节都由唯一的数字标识, 这个数字称为它的地址, 所有可能地址的集合成为虚拟地址空间, 虚拟地址空间只是一个展现给机器级程序的概念性映像, 实际的实现是将 RAM 磁盘存储器特殊硬件和操作系统软件结合起来, 为程序提供一个看上去统一的字节数组 6. 尽管 C 编译器维护着类型信息, 但它实际生成机器级程序并不包含关于数据类型的信息, 每个程序对象可以简单地视为一个字节块, 那么程序本身就是一个字节序列 7. 每台计算机都有一个字长, 指明整数和指针数据的标称大小, 决定了虚拟地址空间的最大大小对于一个字长为 w 位的计算机, 虚拟地址的范围为 0~2 1, 程序最多可以访问 2 个字节 8. 可移植性的一个方面就是使程序对不同的数据类型的确切大小不敏感 9. C 语言标准对不同数据类型的数字范围设置了下界, 但却没有上界 10. 对于跨越多字节的程序对象, 我们必须建立两个规则 : 这个对象的地址是什么, 在存储器中怎么排列这些字节, 在几乎所有机器上, 多字节程序对象都被存储为连续的字节序列, 程序对象的地址为所使用字节中最小的地址 11. 小端法 : 最低有效字节在前面 ; 大端法 : 最高有效字节在前面 ; 使用 ASCII 码作为字符码的任何系统上都将得到相同的结果, 与字节顺序和字大小规则无关, 文本数据比二进制数据具有更强的平台独立性 12. 不同的机器类型使用不同的且不兼容的指令和编码方式, 即使处理器完全一样, 但是运行不同的操作系统, 也会有不同的编码规则, 因此二进制代码是不兼容的 13. 计算机系统的一个基本概念就是从机器的角度来看, 程序仅仅只是字节序列 14. 位向量就是有固定长度 w, 由 0 和 1 组成的串位向量的运算可以定义成参数的每个对应元素之间的运算 15. 逻辑右移在左端补 k 个 0, 算数右移是在左端补 k 个最高有效位的值 C 语言标准并没有明确定义应该使用哪种类型的右移, 但几乎所有的编译器 / 机器组合都对有符号数据使用算术右移 16. 在许多机器上, 当移动一个 w 位的值时, 移位指令只考虑位移量的低 log 位, 因此实际上位移量就是通过计算 k mod w 得到的不过这种行为对于 C 程序来说是没有保证的, 所以移位数量应该保持小于字长程序对象 : 即程序数据指令和控制信息分区深入理解计算机系统笔记的第 2 页

3 2.2 整数表示 2016 年 10 月 13 日 19:34 1. 无符号数的表示 : = = 2,B2 :{0,1} {0,.,2 1}; 2. 补码的表示 : = - - +, 为 [,,, ], 将字的最高有效位解释为负权 ;, 为位的位向量 [,,, ]; 位的位向量 TMa = 2 = 2 1, = 2,B2 :{0,1} { 2,.,2 1}; TMi = T a + 1, 由于 0 是非负数, 造成 TMin 没有与之对应的整数 ; UMa = 2TMa + 1; 强制类型转换的结果保持位值不变, 只是改变了解释这些位的方式无符号表示中的 UMa 有着和补码表示的 -1 相同的位模式 = +, 由此推出补码数转换为无符号数的关系式 : (T2 ( ))= ( ) = +,T2 = ( ) = x + 2, < 0, 0 7. 无符号数转换为补码数的关系式 : ( 2 ( ))= ( )= +, 2 = ( ) =, < 2-2, 2 - 当执行一个运算时, 如果它的一个运算数是有符号的而另一个是无符号的, 那么 C 语言隐式地将有符号参数强制类型转换为无符号数, 并假设这两个数都是非负的将一个无符号数转换为一个更大的数据类型, 我们只需要简单地在表示的开头添加 0( 零扩展 ); 将一个补码数字转换为一个更大的数据类型, 我们需要在表示中添加最高有效位的值的副本 ( 组合权重, 符号扩展 ) 从一个数据大小到另一个数据大小的转换, 以及无符号和有符号数字之间的转换的相对顺序能够影响一个程序的行为我们要先改变大小 ( 即先截断或扩展 ), 之后再完成有符号到无符号的转换将一个位的数 = [,,,0] 截断为一个位数字时, 我们会丢弃高 w-k 位, 得到一个向量 = [,,,0] 截断一个数字可能会改变它的值溢出的一种形式对于一个无符号数 x, 截断它到 k 位的结果就相当于计算 x mod 2 补码数的截断 : 2 ([,,, ]) = 2 2 ([,,,0]) 2 分区深入理解计算机系统笔记的第 3 页

4 2.3 整数的运算 2016 年 10 月 13 日 20: 想要完整地表示算术运算的结果, 我们不能对字长做任何限制无符号运算可以被视为一种模运算形式无符号加法等价于计算和模上 2 当 x + y > 2 1 时, 其和将溢出 x +, x + < 2 x + = + 2, 2 + < 2, x = 0 = 2, > 0 一个算术运算溢出, 是指完整的整数结果不能放到数据类型的字长限制中去当执行 C 程序时, 不会将溢出作为错误而发信号模数加法形成阿贝尔群, 它是可交换的和可结合的大多数计算机使用同样的机器指令来执行无符号或有符号加法 x + = 2 2 ( )+ 2 ( ) = 2 (( + ) 2 ) x + = = + 2, 2 + 正溢出 x +, 2 + < 2 正常 x + y + 2, + < 2 负溢出 2, = 2, > 2 C 语言中的乘法被定义为产生 w 位的值 x = (x * ) mo 2 x = 2 (x * ) mo 2 ) 我们认为对于无符号和补码乘法来说, 乘法运算的位级表示都是一样的, 这表明机器可以用一种乘法指令来进行有符号和无符号运算证明如下 : 设 x = 2 ( ), = 2 ( ) 是这些位模式表示的补码值, 而 x = 2 ( ), = 2 ( ) 是这些位模式表示的无符号值, 则 (x * ) mo 2 = [( + 2 ) ( + 2 )]mo 2 = [ + ( + ) ]mo 2 = ( )mo 2 因此, 我们看到 * 和 x * 的低 w 位是相同的 w 位数字上的无符号运算和补码运算是同构的,+ 和 + 在位级上有相同的结果整数乘法指令一般需要 10 个或更多时钟周期, 而加法减法位级运算和移位只需要 1 个时钟周期, 因此, 编译器会试着使用移位和加法运算的组合来代替乘以常数因子的乘法 2 ([,,,,0,..,0]) = 2 = 2 2 = 2 x2 2 = x 2, 因此, 对于无符号变量 x,c 表达式 x 等价于 x pwr2k, 这里 pwr2k 等于 2 特别地, 我们可以通过 1U k 来计算 pwr2k 考虑一组从位位置 n 到位位置 m 的连续的 1(n ), 我们可以考虑用下面两种不同形式中的一种运算来计算 12. 这些乘积的影响 : 形式 A:(x n)+ (x n 1)+ + (x m) 形式 B:(x n + 1) (x m) 整数除法需要 30 个或者更多时钟周期除以 2 的冥也可以用移位运算来实现, 无符号数和补码分别使用逻辑右移和算术左移来达到目的整数除法总是舍入到零 a. 证明逻辑左移和除以 2 的幂之间的关系, 设 x 为位模式 [,,, ] 表示的无符号整数,k 的取值分区深入理解计算机系统笔记的第 4 页

5 13. b. 范围为 0 k < w 设 x' 为 w-k 位的位表示 [,,, ] 的无符号数, 而 x'' 为 k 位表示 [,,, ] 的无符号数, 我们有 x = /2, 推导如下 : x = 2, = 2, = 2, 因此 x = 2 x + x' 可以观察到 0 x < 2 1, 因此 0 x < 2, 这意味着 /2 = 0, 因此 /2 = x + /2 = + /2 = 对于非负数来说, 算术右移 k 位与除以 2 是一样的负数算术右移 k 位在需要舍入时, 移位导致结果向下舍入, 而不是像规则需要那样向零舍入, 也就是说整数除法应该将负的结果向上舍入, 因此, 当有舍入发生时, 将一个负数右移 k 位不等价于把它除以 2 我们通过在移位之前偏置这个值来修正这种不适合的舍入, 其利用的属性是 : 对于整数 x 和任意 y > 0 的 y, 有 / = ( + 1)/ 因此, 对于 x<0, 如果在右移之前现将 x 加上 2 1, 那么我们就会得到正确的舍入结果了 ( <?( + ( ) ): ) 计算机执行的整数运算实际上是一种模运算形式分区深入理解计算机系统笔记的第 5 页

6 2.4 浮点数 2016 年 10 月 21 日 11: 理解浮点数的第一步是考虑含有小数值的二机制数字十进制表示法 :d = 10 二进制表示法 :b = 2 二进制小数点左移一位相当于此数字除以 2, 右移移位相当于此数字乘以 2 考虑有限长度的编码, 小数的十进制表示法不能准确表示像和这样的数, 小数的二进制表示法只能表示那些能够被写成 x 2 的数 IEEE 浮点表示 : = ( ) 1) 符号 (sign):s 决定这个数是负数 (s=1) 还是正数 (s=0), 对于数值 0 的符号位解释作为特殊情况处理 2) 尾数 (significaned):m 是一个二进制小数, 它的范围是 1~2-ε, 或是 0~1-ε 3) 阶码 (exponent):e 的作用是对浮点数加权, 这个权重是 2 的 E 次幂 ( 可能是负数 ) 5. 根据阶码的值, 被编码的值分为三种不同的情况 1) 规格化的值 : 阶码的位模式不全为 0 也不全为 1 阶码在此情况下被解释为以偏置形式表示的有符号整数,E=e-Bias, 其中 e 是无符号数, 其位表示为 -, 而 Bias 是一个等于 2-1( 为 127,doubl 为 2047) 的偏置值其产生的指数范围, 对于单精度是 -126~+127, 双精度则为 -1022~+1023 尾数定义为隐含的以 1 开头的表示,M=1+f 既然我们总是能够调整阶码 E, 使尾数 M 在范围 1 M < 2 中 ( 假设没有溢出 ), 那么隐含的以 1 开头的表示是一种轻松获得一个额外精度位的技巧, 由于第一位总是等于 1, 那么我们就不需要显式的表示它 2) 非规格化的值 : 阶码的位模式全为 0 阶码值是 E=1-Bias, 尾数的值是 M=f, 不包含隐含的开头的 1 非规格化数有两个用途 : i. 提供一种表示数值 0 的方法 : 当符号位为 1, 其他位为 0 时, 表示 -0.0; 当符号位为 0, 其他位为 1 时, 表示 +0.0 分区深入理解计算机系统笔记的第 6 页

7 根据 IEEE 的浮点格式, 认为值 +0.0 和 -0.0 在某些方面是不同的, 而在其他方面是相同的 ii. 表示那些非常接近于 0.0 的数 : 它提供了一种属性, 称为逐渐溢出, 其中, 可能的数值分布均匀地接近于 0.0 3) 特殊值 : 阶码的位模式全为 1 i. 当尾数全为 0 时, 表示得到的值表示无穷, 当 s 为 1 时表示 +, 当 s 为 0 时表示当两个非常大的数相乘或除以零时, 无穷能表示溢出的结果 ii. 当尾数不全为 0 时, 表示的值被称为 NaN (Not a Number) 6. 通过将非规格化的值的 E 定义为 1-Bias, 而不是 -Bias, 我们可以补偿非规格化数的尾数没有隐含的开头的 1 这一事实 7. 升序排列的浮点数的位表示视为无符号整数的话, 这些整数也是按照升序排列的,IEEE 浮点数的位表示格式使浮点数能够使用整数排序函数进行排序 8. k 位阶码和 n 位小数的浮点表示的一般属性 : 1) 2) 3) 值 +0.0 总有一个全为 0 的位表示 ; 最小的正非规格化数的位表示是由最低有效位为 1 而其他所有位为 0 构成的它具有小数值 M=f=2 和阶码值 E= 因此他的数字值为 V = 2 最大的非规格化值的位表示是由全为 0 的阶码字段和全为 1 的小数字段组成的它具有小数值 M=f=1-2 和阶码值 E= 因此他的数字值为 V = (1 2 ) 2 - ; -, 这仅比最小的规格化值小一点 ; 4) 5) 最小的正规格化值的位模式的阶码字段最低有效位为 1, 其他位全为 0 他的尾数值 M= 1, 而阶码值 E= 因此, 数值 V = 2 值 1.0 的位表示的阶码字段除了最高有效位等于 0 以外, 其他位都等于 1 他的尾数值 M= - ; 1, 而阶码值是 E=0; 6) 最大的规格化值的位表示的符号位为 0, 阶码的最低有效位除了最高有效位等于 0 以外, 其他位都等于 1 小数值 f=1-2, 尾数 M=2-2 它的阶码值 E=2-1, 得到数值 V = 9. (2 2 ) 2 = (1 2 ) 2 因为表示方法限制了浮点数的范围和精度, 浮点运算只能近似地表示实数运算 IEEE 浮点格分区深入理解计算机系统笔记的第 7 页

8 式定义了四种不同的舍入方式 1) 2) 3) 4) 向偶数舍入 ( 默认 ) 向零舍入向上舍入向下舍入在实际中, 浮点单元的设计者使用一些聪明的小技巧来避免执行精确的计算, 因为计算只要精确到能够保证得到一个正确的舍入结果就可以了浮点加法不具有结合性编译器无法知道在效率和忠实于原始程序的确切行为之间, 使用者愿意做出什么样的选择造成编译器倾向于保守, 避免任何对功能产生影响的优化, 即使是很轻微的影响浮点加法满足单调性, 无符号和补码不具有这个属性浮点乘法可交换, 不具有可结合性, 在加法上不具有分配性, 满足以下单调性 : a b 且 c 0 a b 且 c 0 只要 a! =, 就有 0 C 语言标准不要求机器使用 IEEE 浮点, 所以没有标准的方法来改变舍入方式或者得到特殊值, 大多数系统提供 include.h 文件和读取这些特征的过程库, 但是细节因为系统不同而不同强制类型转换规则原类型转换类型结果 int float 不会溢出, 但可能被舍入 int/float double 能够保留精确的数值 double float 可能溢出为无穷, 还可能被舍入 float/double int 值会向零舍入分区深入理解计算机系统笔记的第 8 页

Introduction to Computer Systems /18-243, spring st Lecture, Jan. 12th

Introduction to Computer Systems /18-243, spring st Lecture, Jan. 12th 计算机组成原理习题课 1 授课老师 : 王浩宇 haoyuwang@bupt.edu.cn 1 练习 : 机器数的表示和相互转化练习 1: 当十六进制数 9B 和 FF 分别表示为原码补码反码移码和无符号数时, 所对应的十进制数各为多少 ( 设机器数采用一位符号位 )? 16 进制真值无符号数原码 ( 真值 ) 反码 ( 真值 ) 补码 ( 真值 ) 移码 ( 真值 ) 9BH 二进制十进制