CSAPP(第三版)第二章信息的表示和处理学习笔记

一.信息存储

大部分计算机使用8位的块,（或者字节）来作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称之为虚拟内存（virtual memory）。内存的每一个字节由唯一的数字来标识，称为它的地址（address），所有可能地址的集合称之为虚拟地址空间（virtual address space）。

十六进制表示法

一个字节由8位组成，用二进制表示就是 00000000₂-11111111₂ ，用十进制表示是0₁₀-256₁₀，用十六进制表示是00₁₆-FF₁₆

字数据大小

每台计算机都有一个字长（word size），指明指针数据的标称大小（nominal size）。因为虚拟地址是以这样的一个字来编码的，所以字长决定的重要的系统参数就是虚拟地址空间的最大大小。也就是说，对于一个字长为w位的机器而言，虚拟地址的范围为0~2^w-1。

程序员应该力图使他们的程序在不同的计算机和编译器上可移植，可移植的其中一个方面就是使程序对不同的数据类型的确切大小不那么敏感

寻址和字节顺序

对于跨多个字节的程序对象，我们必须建立两个规则：这个对象的地址是什么，以及在内存中如何排列这些字节。

小端法
最低有效字节在最前面的方式

大端法
最高有效字节在最前面的方式

假设变量x的类型为int，文娱地址0x100处，它的十六进制值为0x01234567。地址范围0x100~0x103的字节依赖于机器的类型：:

几种机器所使用的字节顺序会成为问题的情况：

• 在不同类型的机器之间通过网络传送二进制数据时，一个常见的问题是当小端法机器产生的数据被发送到大端法机器或者反过来时，接受程序会发现，字里的字节成了反序的。
• 当阅读表示整数数据的字节序列时字节顺序也很重要。
• 当编写规避正常的类型系统的程序时。

表示字符串

C语言中的字符串被编码为一个以null（其值为0）字符结尾的字符数组。

表示代码

不同的机器类型使用的且不兼容的指令和编码方式。即使是完全一样的进程，运行在不用的操作系统上也会有不同的编码规则，因此二进制代码是不兼容的。二进制代码很少能在不同机器和操作系统组合之间移植。

布尔代数简介

二进制值是计算机编码，存储和操作信息的核心，所以围绕数值0和1的研究已经演化除了丰富的数学知识体系，最简单的布尔代数是在二元集合{0,1}基础上的定义。

C语言中的位级运算

包括按位与、按位或、异或运算，位运算的一个常见应用就是实现掩码运算（从一个字中选出一个组位）

C语言中的逻辑运算

包括逻辑或||、逻辑与&&、逻辑非！
逻辑运算表达式中，第一个参数能够确定表达式的结果的时候，逻辑运算表达式就不会计算第二个参数的值

C语言中的移位运算

向左移位运算右端补0
向右移位运算包含两种形式：逻辑移位（左端补0）和算数移位（左端补最高有效位）

二.整数表示

下图列出了引入的数学术语，用于精确定义和描述计算机如何编码和操作的整数。

整型数据类型

无符号数的编码

假设一共有 w 位，每个介于 0 ~ 2^w -1 之间的数都有唯一一个 w 位的值编码，即这个函数映射是一个双射。
补码表示的是字的最高有效位解释为负权(negative weight)。
原理：无符号数编码的定义
对象量
\vec{x}

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

C中的有符号数和无符号数

C 语言允许无符号数和有符号数之间的转换。转换的原则是底层的位表示保持不变。

扩展一个数字的位表示

零扩展： 将一个无符号数转换为一个更大的数据类型，在开头加0
符号扩展： 将一个二进制补码转化为一个更大的数据类型，在开头加最高有效位

截断数字

截断一个数字可能会改变它的值——溢出的一种形式

有关有符号数和无符号数的建议

有符号数到无符号数的隐式强制类型转换导致了某些非直观的行为。而这些非直观的特性经常导致程序错误，并且这种包含隐式强制类型转换细微差别的错误很难被发现。因为这种强制类型转换是在代码中没有明确指示的情况下发生的，程序员经常忽视了它的影响。

避免这类错误的一种方法就是绝不使用无符号数。实际上，除了 C 以外，很少有语言支持无符号整数。

整数运算

无符号加法

每个数都能表示为 w 位无符号数字。如果计算它们的和，表示这个和可能需要 w + 1位。无符号运算可以被视为一种模运算形式。

二进制补码加法

必须确定当结果太大(为正)或者太小(为负)时，应该做些什么。

二进制补码的乘法

乘以2的幂

在大多数机器上，整数乘法指令相当慢，需要 10 个或者更多的时钟周期，然而其他整数运算(例如加法、减法、位级运算和移位)只需要 1 个时钟周期。因此，编译器使用了一项重要的优化，试着用移位和加法运算的组合来代替乘以常数因子的乘法。

除以2的幂

在大多数机器上，整数除法要比整数乘法更慢——需要 30 个或者更多的周期。除以 2 的幂也可以用移位运算右移来实现，无符号和补码数分别使用逻辑移位和算术移位来达到目的。

浮点

二进制小数

IEEE浮点表示

用 V = (-1)^s * M * 2^E 的形式来表示一个数：

• 符号(sign) s决定这个数是负数(s=1)还是正数(s=0)，对于数值 0 的符号位解释作为特殊情况处理。
• 尾数(significand) M 是一个二进制小数，它的范围是 1 ~ 2 - ε，或者是 0 ~ 1 - ε。
• 阶码(exponent) E 的作用是对浮点数加权，这个权重是 2 的 E 次幂(可能是负数)

将浮点数的位表示划分为三个字段，分别对这些值进行编码：

• 一个单独的符号位 s 直接编码符号 s。
• k 位的阶码字段 exp = e(k-1)…e(1)e(0) 编码阶码 E。
• n 位小数字段 frac = f(n-1)…f(1)f(0) 编码尾数 M，但是编码出来的值也依赖于阶码字段的值是否等于 0。

舍入

因为表示方法限制类浮点数的范围和精度，浮点运算只能近似地表示实数运算。因此，对于值 x，我们一般想用一种系统的方法，能够找到“最接近的”匹配值，这就是舍入运算的任务。

常见的舍入方式有：向偶数舍入、向零舍入、向下舍入、向上舍入

浮点运算

浮点加法不具有结合性。浮点乘法在加法上不具备分配性。对于科学计算程序员和编译器编写者来说，这是很严重的问题，即使为了在三维空间中确定两条线是否交叉而写代码这样看上去很简单的任务，也可能成为一个很大的挑战。

C语言的浮点数

float 和 double。在 int、float 和 double 格式之间进行强制类型转换时，程序改变数值和位模式的原则如下(假设 int 是 32 位的)：

• 从 int 转换成 float，不会溢出，可能被舍入。

• 从 int 或 float 转换成 double，能够保留精确的数值。

• 从 double 转换成 float，可能溢出成为正无穷或负无穷，也可能被舍入。

• 从 float 或者 double 转换成 int，值会向零舍入。例如 1.999 将被转换成 1。