《深入理解计算机系统》读书笔记 第二章 信息的表示和处理。

2 信息的表示和处理

2.1 信息存储

  • 字节(byte):最小的可寻址的内存单位。

2.1.1 十六进制表示法

  • 二进制、十进制、十六进制间的相互转化。

2.1.2 字数据大小

  • 每台计算机都有一个 字长(word size),指明指针数据的标称大小(nominal size)。
  • 虚拟地址是以这样的一个字来编码的,所有字长决定了虚拟地址空间的最大大小(0 ~ 2^w-1)。
  • 32位字长:4GB。
  • 64位字长:16EB。
  • 32位程序和64位程序的区别在于如何编译的,大多数64位机器也可运行32位机器编译的程序(向后兼容)。
1
2
$ gcc -m32 prog.c
$ gcc -m64 prog.c
  • C语言中:
    • 即使是64位系统编译,int通常也只有4字节。
    • C语言中,long在32位程序中为4字节,在64位程序中为8字节。
    • ISO C99 引入了确定大小的数据类型:int32_tint64_t
    • 除非有unsigned,类型默认是有符号的,char是个例外,C标准不保证这一点。

2.1.3 寻址和字节顺序

1
2
3
4
5
int a = 0x01234567;

// 0x100 0x101 0x102 0x103
//大端法 ... 01 23 45 67 ...
//小端法 ... 67 45 23 01 ...
  • 字节顺序很重要的场合:

    • 网络应用程序的代码编写必须遵守已建立的关于字节顺序的规则。
    • 阅读表示整数数据的字节序列时。如反汇编器(disassembler)生成的代码。
    • 当编写规避正常的类型系统的程序时。如强制类型转换(cast)或使用联合(union)。
  • 值相等的整数和浮点数在字节模式上截然不同,不过一般能够通过移位相匹配。

2.1.4 表示字符串

  • 0结尾的字符数组。
  • 使用ASCII码作字符码将在任何系统上得到相同的结果,与字节顺序和字大小规则无关。

2.1.5 表示代码

  • 二进制代码很少能在不同机器和操作系统组合之间移植。

2.1.6 布尔代数简介

  • ~
  • &
  • |
  • ^

2.1.7 C语言中的位级运算

  • ~
  • &
  • |
  • ^

2.1.8 C语言中的逻辑运算

  • &&
  • ||
  • !

2.1.9 C语言中的移位运算

  • 左移:丢弃最高的k位,在右端补k个0。
  • 逻辑右移:在左端补k个0。
  • 算术右移:在左端补k个最高有效位的值。

  • C语言标准并未明确定义有符号数使用哪种右移,但几乎所有的编译器/机器都使用算术右移。

  • 如果移动k位,k超过了该数据类型的长度(w位),在许多机器上,将只考虑移位log(2)w位。
  • 加减运算符优先级比移位运算符高。

2.2 整数表示

2.2.1 整型数据类型

  • 典型的C语言有符号整数的正负值范围是不对称的,负数多1个。
  • C语言标准定义的有符号整数类型必须能够表示的最小范围的正负值范围是对称的,除了*32_t*64_t这种。

2.2.2 无符号数的编码

  • 用函数B2U-w表示。
  • 无符号编码的唯一性:该函数是个双射。

2.2.3 补码编码(Two’s complement)

  • 用函数B2T-w表示。
  • 补码编码的唯一性:该函数是个双射。

有符号数的其他表示方法:

  • 反码(Ones’ Complement)
  • 原码(Sign-Magnitude)

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

  • 用函数T2U-wU2T-w表示。
  • 对大多数C语言实现,处理同样字长的有符号数和无符号数之间相互转换的一般规则是:数值可能改变,但位模式不变。
  • 表现在最终数值上:
    • 有符号转无符号:正数不变,负数加2^w
    • 无符号转有符号:范围内不变,范围外减2^w

2.2.5 C语言中的有符号数与无符号数

  • 无符号数添加后缀u
  • 显式类型转换。
  • 隐式类型转换。
  • 格式化输出。
  • 运算数的转换:有符号和无符号运算,将转为无符号并假设二者都是非负的。
  • C语言中INT_MIN往往定义成-INT_MAX-1

2.2.6 扩展一个数字的位表示

  • 无符号数的零扩展:添加0。
  • 补码数的符号扩展:添加最高有效位的值。
  • 如果即需要扩展有需要改变符号,C语言标准要求:先改变大小,再完成符号转换。

2.2.7 截断数值

  • 截断无符号数:丢弃高位。新值为x mod 2^k
  • 截断补码数值:丢弃高位,重新解释符号位。新值为U2T-k(x mod 2^k)

2.2.8 关于有符号数与无符号数的建议

  • 可以要求绝不使用无符号数。
  • 如果仅仅想把数字作为位的集合,无符号数是非常有用的。

2.3 整数运算

2.3.1 无符号加法

  • x+y若溢出,最终结果相当于x+y-2^w
  • 判断x+y是否溢出的方法是与xy进行比较。
  • 无符号数取反,-x,最终结果相当于2^w-x。(0除外,依然是0)。

2.3.2 补码加法

  • x+y若溢出,最终结果相当于x+y-2^w(正溢出)或x+y+2^w(负溢出)。
  • 当且仅当x>0, y>0, s<=0时,发生了正溢出。
  • 当且仅当x<0, y<0, s>=0时,发生了负溢出。

2.3.3 补码的非

  • -TMin-w还是TMin-W。其他数正常。
  • 补码非得位级计算方式一:-x -> ~x+1
  • 补码非得位级计算方式二:找到最右边的1,将它左边的所有位取反。

2.3.4 无符号乘法

  • x*y若溢出,最终结果相当于x*y mod 2^w

2.3.5 补码乘法

  • x*y若溢出,最终结果相当于U2T-w(x*y mod 2^w)
  • 无符号和补码乘法的位级等价性:同样的位向量,无论是做无符号乘法还是补码乘法,最终结果的位向量都是一样的。

2.3.6 乘以整数

  • 乘以2的幂:左移。(无论是无符号还是补码,无论是否溢出)
  • C语言编译器会试图用移位和加法替代乘法,如x*14 = (x<<3) + (x<<2) + (x<<1);,因为14 = 2^3 + 2^2 + 2^1,或者x*14 = (x<<4) - (x<<1),因为14 = 2^4 - 2^1

2.3.7 除以2的幂

  • 整数的除法的结果总是向0舍入,即会向下舍入一个正值,或者向上舍入一个负值。
  • 无符号:逻辑移位即可,即x / 2^k = x >> k,结果是向下舍入的。
  • 补码:如果仅仅算术移位,对负数来说结果依然是向下舍入的。因此需要做点偏移:x / 2^k = (x+(1<<k)-1) >> k

2.3.8 关于整数运算的最后思考

  • 计算机的整数运算实际上是一种模运算形式。
  • 结果运算可能溢出。
  • 补码提供了一种既能表示整数又能表示负数的灵活方法。
  • 某些规定和数据类型让程序产生意想不到的行为。

2.4 浮点数

  • IEEE浮点标准。

2.4.1 二进制小数

  • 我们不能准确地表示一个二进制小数,只能近似地表示。
  • 小数点左边位的权是2的正幂,右边是2的负幂。
  • 1-ε表示能表示的距离1最近且小于1的浮点数。

2.4.2 IEEE浮点表示

  • V = (-1)^s * M * 2^E

    • 符号s(sign)。
    • 尾数M(significand),一个二进制小数,范围在1~2-ε0~1-ε
    • 阶码E(exponent)。
  • 浮点数的位表示分成三段:

    • 1位符号位。
    • k位阶码。
      • float:8,范围:-126 ~ +127。
      • double:11,范围:-1022 ~ +1023。
    • n位尾数。
      • float:23
      • dobule:52
  • 根据阶码的值,可以分为三种情况:

    1. 规格化的(E != 0 && E != 255
      • 阶码部分表示成无符号数得到的值e并不是阶码,E = e - Bias,其中偏置码Bias = 2^(k-1) - 1
      • 尾数部分表示成浮点数得到的值f(0.xxxx)并不是尾数,为了获得额外一个精度,M = f + 1。即隐含的以1开头(implied leading 1)的表示。
    2. 非规格化的(E == 0
      • E = 1 - Bias
      • M = f
    3. 无穷大(E == 0x1111..1111 && M == 0)、NaN(E == 0x1111..1111 && M != 0

2.4.3 数值示例

  • 比较浮点值的大小可以转化成比较无符号整型的大小。(负数时需要一些技巧,见练习2.84)

  • 一般属性:

    • 值+0.0总有一个全为0的位表示。
    • 最小的正非规格化值的位表示:0 000..000 000..001。其中,M = f = 2^(-n)E = -2^(k-1) + 2
    • 最大的非规格化值的位表示:0 000..000 111..111。其中,M = f = 1 - 2^(-n)E = -2^(k-1) + 2。(仅仅比最小正规格化值小一点)
    • 最小的正规格化值的位表示:0 000..001 000..000。其中,M = 1+f = 1E = -2^(k-1) + 2
    • 值1.0的位表示:0 100..000 000..000。其中,M = 1+f = 1E = 0
    • 最大的正规格化值的位表示:0 111..110 111..111。其中,M = 1+f = 2 - 2^(-n)E = 2^(k-1) - 1
  • 练习把整数值转换成浮点形式对理解浮点表示非常有用。

2.4.4 舍入(rounding)

  • 四种舍入方式:
    • 向偶数舍入。(可避免统计偏差。浮点数同样可用。二进制同样可用。)
    • 向零舍入。
    • 向下舍入。
    • 向上舍入。

2.4.5 浮点运算

  • IEEE标准定义了一些规则,如:1/-0 = 负无穷,1/+0 = 正无穷。
  • 实数的加法可能由于溢出得到无穷值,实数加法是可交换、不可结合的。
  • 大多数值在浮点加法下都有逆元,无穷和NaN是例外。
  • 浮点加法满足了单调性属性。若a>=b,对任意xx+a >= x+b。无符号或补码加法不具备这个实数(和整数)加法的属性。
  • 浮点乘法是可交换、不可结合的,在加法上也不具备分配性。
  • 对于任何a、b、c(均不为NaN),浮点乘法满足如下单调性:a>=b && c >=0 => a*c >= b*ca>=b && c<=0 => a*c <= b*c。无符号或补码的乘法没有这些单调性属性。
  • 只要a!=NaN,就有a * a >= 0。无符号或补码的乘法没有这些单调性属性。

2.4.6 C语言中的浮点数

  • 单精度和双精度使用向偶数舍入的舍入方式。
  • C语言标准不要求机器使用IEEE浮点,所以没有标准的方法来改变舍入方式或者得到无穷、NaN、-0等数值。
  • GCC字长引入#define _GNU_SOURCE 1 #include <math.h>来定义INFINITHYNAN
  • intfloatdoublie的互转:
    • intfloat:不会溢出,但可能被舍入。
    • intfloatdouble:能保留精确的数值。
    • doublefloat:可能舍入,可能溢出成无穷。
    • floatdoubleint:向零舍入,也可能溢出。C标准没对溢出做要求,Intel系微处理器指定位模式[10…00]为整数不确定值(integer indefinite),如(int)+1e10会得到-21483648

习题:

  • 2.1 二进制/十六进制转换。
  • 2.2 二进制/十进制/十六进制转换。
  • 2.3 二进制/十进制/十六进制转换。
  • 2.4 十六进制加减运算。
  • 2.5 整数的大小端存储。
  • 2.6 值相等的整数和浮点数在字节模式上的比较。
  • 2.7 字符串的字节模式。
  • 2.8 位向量的布尔运算。
  • 2.9 布尔运算与三原色。
  • 2.10 使用^实现两数交换。
  • 2.11 使用^交换同一地址的值时导致的问题。
  • 2.12 使用掩码提取或设置个别位上的状态。
  • 2.13 使用“设置位”、“清除位”操作实现“或”和“异或”运算。
  • 2.14 布尔运算和逻辑运算。
  • 2.15 只使用位级和逻辑运算实现x==y
  • 2.16 移位运算。
  • 2.17 无符号数的编码和补码编码。
  • 2.18 十六进制转补码转十进制。
  • 2.19 有符号数转无符号数。
  • 2.20 分析2.19。
  • 2.21 有符号和无符号进行运算。
  • 2.22 验证补码数的符号扩展规则。
  • 2.23 移位和符号转换的综合运用。
  • 2.24 截断数值。
  • 2.25 有符号数和无符号数混用导致的错误。
  • 2.26 有符号数和无符号数混用导致的错误。
  • 2.27 判断两个无符号数相加是否溢出。
  • 2.28 无符号数求反。
  • 2.29 可能溢出的补码加法。
  • 2.30 判断两个补码相加是否溢出。
  • 2.31 判断两个补码相加是否溢出。
  • 2.32 判断两个补码相加是否溢出。
  • 2.33 补码的非。
  • 2.34 无符号乘法和补码乘法。
  • 2.35 判断乘法是否溢出。
  • 2.36 判断乘法是否溢出。
  • 2.37 修复XDR库乘法漏洞。
  • 2.38 移位和加法替代乘法的应用。
  • 2.39 移位和加法替代乘法的应用。
  • 2.40 移位和加法替代乘法的应用。
  • 2.41 移位和加法替代乘法的应用。
  • 2.42 实现一个“除以16”的函数。
  • 2.43 乘除综合练习。
  • 2.44 整数运算综合练习。
  • 2.45 二进制小数的表示。
  • 2.46 二进制小数不精确引发的灾难性后果。
  • 2.47 填表,浮点数值范围。
  • 2.48 推导浮点的位。
  • 2.49 浮点精度。
  • 2.50 二进制浮点数舍入到偶数
  • 2.51 二进制浮点数舍入引发的灾难性后果。
  • 2.52 二进制浮点数表示与舍入综合。
  • 2.53 定义双精度无穷和0值的宏。
  • 2.54 整数和浮点混合计算题