深入理解计算机系统笔记（一）

数字的二进制表示

1. 整数的二进表示
   • unsigned int 编码
     • UMIN 和 UMAX，即使用 unsigned int 编码所能表示的最大范围整数，使用 w 位表示 unsigned int，最小的为全 0，最大的为全 1，那么 UMIN = 0，UMAX = 2^w -1。
   • int 编码，即有符号位的整型编码，编码的本质其实是集合间的一一对应关系，且不改变原先集合的运算性质。int 编码一般使用补码，two's complement。
     • 符号位为 0 代表正数，则最小的正数为 0001，最大的正数为 0111，从最小的 0001 一直加 1 到 0111 分别对应了 2^(w-1) -1 个正数，对于 w=4 的情况，就代表了 1 - 15 的正整数。且从二进制的比较来看，0001 是要小于 0111 的，也符合原整数集合的比较关系。
     • 对于负数来说，符号位为 1，则能代表的最大负数为 1111，最小的负数为 1000，对应了 2^(w-1) 个负数，所能代表的范围就是 -2^(w-1) ~ -1。也就是说 1111 对应 -1，1000 对应 -8。运算关系也符合，(1111)b + (1)b = 1(0000)，舍去溢出的高位，刚好等于二进制的 0。
     • 所以 TMAX = 2^(w-1) -1，TMIN = 2^(w-1)。
     • 对于补码的计算来说，对正数编码取反加 1 即可。
   • 运算
     • AND OR NOT XOR(同为 0，不同为 1)
     • 算术位移与逻辑位移
       • 算术位移继承符号位
       • 逻辑位移补 0
   • 大端编码与小端编码
     • little endian，大部分机器用的编码方式，低位存储在高字节，高位存储在低字节，与人们日常使用习惯相反。
     • big endian，与人们的日常使用习惯相同，网络传输一般使用 big endian。
   • 机器的位数代表机器的寻址范围，64 位机器只有 47 位可用于寻址。计算机的寻址是以字节为单位的。
     • 字节对齐，字节对齐的本质是提高访问效率，控制访问的起始地址是 8 字节或者 4 字节的整数倍，64 位计算机在读取的时候是一次读取 64 位也就是 8 个字节，如果存储的地址不合适，就会导致本来一个读周期就能读完的数据要两个读周期。
     • 定某个数据类型的变量存储的起始地址是编译器做的事，对于结构体内的基本数据类型，编译器都会进行对齐操作，保证访问一个成员时尽量少的读取周期。
     • 可以使用 #pragma pack(n) 指定对齐数。
     • 这里可以与 CPU 缓存的 false sharing 做下比较。
       • CPU 缓存的最小单位是 cache line。修改了 cache line 对应的内存的任一字节，都会使整个 cache line 失效，所以最好将只读数据和可变数据分开存储。
       • CPU 1 缓存了 cache line。CPU 2 修改了 cache line 对应的内存任一字节，也会失 CPU 1 的 cache line 失效，称做 false sharing。
2. 浮点数的二进制表示 floating point
   • 对于浮点数来说，是没有整数那种精确的一一对应关系的，只能是一种非精确表示。
   • 规范化表示
     • (-1)^s * M * 2^e
       • s 为符号位，取值为 1 或者 0
       • M 是一个二进制小数，取值在 [0,2) 之间
       • e 为阶码
     • 三个字段 s, exp, frac
       • s 占 1 位
       • 32 位中，exp 占 8 位，frac 占 23 位；64 位中，exp 占 11 位，frac 占 52 位
       • 与补码表示不同，同一个浮点数的正负值只有符号位不同，其它位都是一样的
     • 规范化表示
       • exp 不全为 0 也不全为 1
         • exp 全为 0 转为非规范化表示
         • exp 全为 1 且 frac 全为 0 表示无穷大
         • exp 全为 1 且 frac 不全为 0 表示 NaN
       • 阶码 e = exp - bias，其中 bias = 2^(w-1) -1
         • 这样可以省略使用多余的位来表示指数的正负
       • 1.frac 是 M 的值，其中 1 这个位是隐藏的，这样可以多出一位的精度
     • 非规范化表示
       • exp 全为 0
       • e = 1 - bias，bias = 2^(w-1) - 1
       • 非规范化表示可以表示 0.0，且分 -0.0 和 +0.0，即 exp 全为 0，frac 全为 0
       • e = 1 - bias，可以补偿规范化表示中隐藏的 1，实现非规范化表示到规范化表示的平滑过渡
       • M 的值是 frac，无隐藏的 1
     • 浮点数的运算
       • 加法不满足结合性，有可能丢失精度
       • 满足交换率和单调性 a>=b，除了 NaN 以外，a + x >= b + x。而整数不满足这个性质，由于溢出的存在，浮点运算不会溢出，因为有无穷大的定义，但会丢失精度
     • 为什么浮点数不能直接进行比较？
       • 浮点数运算的中间结果会保存到浮点数寄存器中，而浮点数寄存器是 80 位扩展精度，和内存中的值进行比较的话，由于精度不同，比较结果就不同。但当浮点数刚好可以精确表示的时候，是可以直接比较的。或者直接比较两个内存里的浮点数，也是可以直接比较的，也就是说不经过运算，但这种在实际运用中意义不大。