第二章：信息的表示与处理

哈工大854 深入理解计算机系统 CSAPP 第二章：信息的表示与处理       无符号（unsigned）编码基于传统的二进制表示法，表示大于或者等于零的数字；补码（two’s-complement）编码是表示有符号整数的最常见的方式，有符号整数就是可以为正或者负的数字；浮点数（floating-point）编码是表示实数的科学记数法的以二为基数的版本。

信息的表示与处理

• 2.0 概述
  • 现代计算机存储和处理的信息以二值信号表示
  • 二值信号能够很容易地被表示，存储和传输
  • 无符号编码 补码编码 浮点数编码（运算不可结合） 溢出
  • 整数的表示只能编码一个相对较小的数值范围，但精确 浮点数可以编码一个较大的数值范围，但只是近似
• 2.1 信息存储
  • 2.1.1 十六进制表示法
    • 虚拟内存：机器级程序将内存视为一个非常大的字节数组
    • 虚拟内存地址：内存中每个字节都由一个唯一的数字来标识（地址），所有可能地址的集合
    • 引入：二进制表示法太冗长，十进制表示法与位模式的相互转换麻烦
    • 表示：0x
    • 二进制与十六进制的转换
    • 十进制与十六进制的转换
  • 2.1.2 字数据大小
    • 字长（word size）：指明指针数据的标称大小（nominal size）
    • 32位—4字节—4GB 64位—8字节—16EB
    • 向后兼容：64位机器可以运行32位机器编译的程序
    • 32位程序—64位程序，区别在于程序是如何编译的（使用的编译器类型），而不是机器类型
    • int32_t和int_64t数据大小固定，不随编译器和机器设置而变化
    • 大部分数据类型默认为有符号数值，除非声明unsigned
    • 编程时，应注意程序的可移植性（保证程序对不同的数据类型的确切大小不敏感）
  • 2.1.3 寻址和字节顺序
    • 寻址前提
      • 对象的地址是多少
      • 内存中如何排列这些字节
    • 连续的字节序列
      • 小端法：最低有效字节在最前面
      • 大端法：最高有效字节在最前面
      • 双端法：一旦确定了操作系统，字节顺序也就固定下来了
    • 字节顺序的影响
      • 不同类型的机器之间通过网络传输二进制数据
      • 检查机器级程序，阅读表示整数的字节序列时
      • 编写规避正常的类型系统的程序时（系统级编程）
        • 强制类型转换并不会改变真实的指针，只是告诉编译器以新的数据类型来看待被指向的数据
  • 2.1.4 字符串表示
    • 在使用ASCLL码作为字符码的任何系统上都将得到相同的结果，与字节顺序和字大小规则无关
    • 文本数据比二进制数据具有更强的平台独立性
    • 拓展
      • Unicode：字符集（为每一个字符分配一个唯一的ID/码位/码点/code point）
      • UTF-8：编码规则（将码位转换为字节序列的规则）
      • ASCLL字符集适合于英语文档
  • 2.1.5 表示代码
    • 不同的机器类型使用不同的且不兼容的指令和编码方式
    • 二进制代码很少能在不同机器和OS组合之间移植
  • 2.1.6 布尔代数
  • 2.1.7 C语言中的位级运算
    • OR 或 |
    • AND 与 &
    • NOT 非 ～
    • EXCLUSIVE-OR 异或 ^（同0异1） （a^b）^a = b
  • 2.1.8 C语言中的逻辑运算
    • ||
    • &&
    • ！
    • 非0的参数表示TRUE 参数0表示FALSE 返回0/1，分别表示TRUE/FALSE
  • 2.1.9 C语言中的移位运算
    • 左移（＜＜），补0，
    • 右移（＞＞，C）
      • 逻辑右移：补0（无符号数）
      • 算术右移：补最高有效位的值（有符号数）
      • JAVA中规定＞＞为算术右移＞＞＞为逻辑右移
    • 拓展
      • 移动位数＞数据类型位数，取模（JAVA中，C不保证）
      • 移位运算最好加括号
• 2.2 整数表示
  • 2.2.0 概述
    • 无符号数: 只能表示非负数
    • 有符号数（一般指补码）: 可表示负数，零和正数
    • 相关函数说明
  • 2.2.1 整型数据类型
    • 32/64位程序上C语言整型数据类型的典型取值范围
    • C语言标准：定义了每种数据类型必须能够表示的最小的取值范围
    • C/C++ 都支持有符号（默认）和无符号数。JAVA只支持有符号数。
  • 2.2.2 无符号数（Unsigned）
    • 无符号数编码
    • 无符号数编码具有唯一性
  • 2.2.3 补码（Two＇s complement）
    • 补码编码
    • 补码编码的唯一性
    • 说明
      • 补码的取值范围是不对称的：|TMin| =|TMax|+1
      • 最大的无符号数值刚好比补码的最大值的两倍大一点 UMax=2TMax+1
      • C语言标准并未给出要求用补码的形式来表示有符号整数，但几乎所有的机器都是这么做的
      • 使用补码的程序便于移植
    • 拓展
      • 反码：One＇s Complement
      • 原码：Sign-Magnitude
      • 比较：对于数字0都有两种不同的编码方式
        • 反码：+0=[00...0] 或 -0=[11...1]
        • 原码：+0=[00...0] 或 -0=[10...0]
      • 起源
        • 补码：对于非负数x，我们用（2^w - x）来表示计算-x的w位表示
        • 反码：用（[111...1]-x）来表示-x
  • 2.2.4 有符号数与无符号数之间转换
    • C语言允许在各种不同的数字数据类型之间做强制类型转换
    • 保持位模式不变（底层的表示保持不变），只是改变了解释这些位的方式
    • 补码——＞无符号数
    • 无符号数——＞补码
  • 2.2.5 C语言中的有符号数和无符号数
    • 转换场景
      • 显式的强制类型转换
      • 隐式的类型转换（一种类型表达式被赋值给另一种类型的变量时）
      • printf指定输出数值类型时
    • 转换规则
      • 隐式的将有符号参数强制转换为无符号数
  • 2.2.6 扩展一个数字的位表示
    • 扩展场景
      • 较小的数据类型转换到较大的类型
    • 扩展方式
      • 零扩展（zero extension）：开头添0
      • 符号扩展（sign extension）：开头添最高有效位的值
  • 2.2.7 截断数字
    • 截断场景
      • 较大的数据类型转换到一个较小的数据类型（可能会导致溢出）
    • 截断方式
      • 截断无符号数值
      • 截断补码数值
  • 2.2.8 关于有符号数与无符号数的建议
    • 强制类型转换常常在不知不觉中导致程序错误，特别是有符号数到无符号数的隐式转换
    • 因此，除了C语言的大多数语言都很少支持无符号数
    • 无符号数用途：地址表示...
• 2.5 总结
  • 64位程序的优势是可以突破32位程序具有的4GB地址限制
  • 无符号数和补码的运算都满足整数运算的结合律，交换律，分配律 因此，编译器可以做优化
• 2.4 浮点数
  • 2.0 概述
    • IEEE浮点标准，大大提高了科学应用程序在不同机器程序上的可移植性
  • 2.4.1 二进制小数
    • 类比于10进制的科学计数法
    • 有十进制科学计数法的同样弊端—并非所有的数都能被表示，只能增加二进制表示长度提高表示精度
  • 2.4.2 IEEE浮点表示
    • 32：1+8+23 64：1+11+52
    • 规格化的值
    • 非规格化的值
    • 特殊值
      • ∞：两个非常大的数相乘，或者除以0时，表示溢出的结果
      • NaN：不是一个数，运算结果不能是实数或者无穷时
  • 2.4.3 数字示例
    • 可表示的数不是均匀的，越靠近原点处越稠密
    • 非规格化的值的分布是均匀的
    • 最大非规格化数和最小规格化数的转换是平滑的，这归功于偏置值（Bias）的设计
    • 整数值转换为浮点形式
    • 想一想：对于具有n位小数的浮点格式，不能准确描述的最小正整数的公式？
  • 2.4.4 舍入
    • 向偶数舍入（避免了统计方差），向零舍入，向下舍入，向上舍入
    • 最低有效位的值为0认为是偶数 最低有效位的值为1认为是奇数 注意：只有当是中间值时，遵循向偶数舍入
  • 2.4.5 浮点运算
    • 浮点数加法，乘法不具有结合性
    • 浮点数加法，乘法具有交换性，单调性（而整数乘法，加法不具有单调性）
  • 2.4.6 C语言中的浮点数
    • int→float，精度降低，舍入
    • int/float→double，精确数值
    • double→float，溢出∞/精度降低，舍入
    • float/double→int，溢出/向0舍入
• 2.3 整数运算
  • 2.3.1 无符号加法
    • 两个ω位的无符号数相加可能需要ω+1位来表示（字长膨胀）
    • 大多数语言支持固定精度的运算，即会对结果进行截断 （Lisp语言支持无限精度运算）
    • 无符号数加法
      • 定义
      • 推导
    • 溢出检测
      • 检测函数
    • 无符号数求反
  • 2.3.2 补码加法
    • 两个ω位的补码数相加可能需要ω+1位来表示，同样需要截断
    • 补码加法
      • 定义
      • 推导
    • 溢出检测
      • 检测函数
      • 防止溢出
  • 2.3.3 补码的非
    • 拓展：补码求非技巧
      • 求补加1
      • 自右向左，第一个非0前的高位全部取反
  • 2.3.4 无符号乘法
    • 定义
  • 2.3.5 补码乘法
    • 定义
    • 无符号和补码乘法的位级等价性（同理，加法，非）
  • 2.3.6 乘以常数
    • 乘法指令需要10个或更多个时钟周期
    • ①与2的幂相乘的无符号乘法
    • ②与2的幂相乘的补码乘法
    • ③推广到乘以任意常数
  • 2.3.7 除以2的幂
    • 整数除法要比乘法更慢——需要30个或者更多的时钟周期
    • 无符号（逻辑右移），补码（算术右移）
    • 整数除法总是舍入到0，因此，x/y向下舍入一个正值，向上舍入一个负值
    • ①除以2的幂的无符号除法（向下舍入）
    • ②除以2的幂的补码除法，向下舍入
    • ③除以2的幂的补码除法，向上舍入（➕偏量）
    • 右移的方式无法推广到除以任意常数
  • 2.3.8 关于整数运算的最后思考
    • 计算机执行“整数”运算实际上是一种模运算形式
    • 表示数字的有限字长限制了可能的值的取值范围，使得结果可能溢出
    • 无论运算数是以无符号形式还是以补码形式表示的，都有完全一样或者非常类似的位级行为。
    • 实际上，大多数计算机使用同样的机器指令来执行无符号或者有符号算法