《深入了解计算机系统》

目录

[toc]

信息的表示和处理

三种重要的数字表示

• 无符号（unsigned）编码
• 补码（two's-complement）编码
• 浮点数（floating-point）编码

信息存储

字节为最小的可寻址内存单位

十六进制表示法

• 分段法——2^n进制互相转化
• 1248法——2-10进制互相转化
• 连除法——任意进制互相转换

字数据大小

每台计算机都有一个字长（word size），指明指针数据的标称大小（nominal size）

现在的计算机已大量从32位字长机器到64位字长机器迁移

32位和64位机器上，C语言的类型声明字节数不同：（注意short [int]，long [int]简写）

有符号类型	无符号类型	32位字节数	64位字节数
[signed] char	unsigned char	1	1
short	unsigned short	2	2
int	unsigned	4	4
long	unsigned long	4	8
int32_t	uint32_t	4	4
int64_t	unint64_t	8	8
char *		4	8
float		4	4
double		8	8

寻址和字节顺序（大端法和小端法）

（笔记者：这里我一开始没做笔记，草草略过。后来重新复习C/C++时才意识到该章的重要性，才补的笔记）

内存中如何排列字节

• 小端法：最低有效字节（类比十进制高位）在最前面
• 大端法：最高有效字节（类比十进制高位）在最前面

举例：存储0x1234567

地址	0x100	0x101	0x102	0x103
大端法	01	23	45	67
小端法	67	45	23	01

各类机器上所使用的方案

机器	值	类型	字节（16进制）	采用方法
Linux 32（IA32） Windows（IA32） Sun Linux 64（x86-64）	12345 12345 12345 12345	int int int int	39 30 00 00 39 30 00 00 00 00 30 39 39 30 00 00	小端法 小端法 大端法 小端法

优缺

• 大端小端没有谁优谁劣，各自优势便是对方劣势：
• 小端模式 ：强制转换数据不需要调整字节内容，1、2、4字节的存储方式一样
• 大端模式 ：符号位的判定固定为第一个字节，容易判断正负

表示字符串

C语言字符串被编码为一个以null字符结尾的字符数组，每个字符由某个标准编码来表示。

表示代码

代码在不同的机器（Linux32、Windows、Sun、Linux64）上编译时，生成字节表示的机器代码都不同

因此二进制代码是不兼容的。二进制代码很少能在不同机器和操作系统组合之间移植。

布尔代数简介

C语言的位级运算

支持按位布尔运算

一个常见用法为进行掩码运算

• 与&
• 或|
• 非~
• 异或^

C语言的逻辑运算

短路性质

• 与&&
• 或||
• 非!

C语言的移位运算

• 左移x<<k，空缺补0

• 右移x>>k

  • 逻辑右移空缺补0

  • 算术右移空缺补4个最高有效位的值（其右移的的二进制位的本质是原码的补码，算术右移便于处理以补码形式存储的有符号数）

  • 一般而言对有符号数使用算术右移，对无符号数使用逻辑右移

    与C相比，Java则明确规定了x>>k为算术右移，x>>>k为逻辑右移

整数表示

整数数据与算术操作术语。下标w表示数据表示中的位数

【必看】

重要！必看！这书坑爹......

这本书的翻译和国内教程《大学计算机基础（第三版）》的术语名词有些区别，该章节中也没有介绍原码和补码

位存储与二进制

这里的U和T都是数（10进制和2进制都是数，只是表示形式区别）

因为有时位并不表示2进制，为方便计算以及将“数”和“位存储”区分开来，该数凡是以数形式的（U、T）都会写成10进制）

函数类型

• 对于有符号数：

  • 这里的“二进制B”相当于国内的“补码”

    **（而非原码，是存储的原始二进制）**应该是是原码吧

  • "补码T"相当于国内的“以补码方式解读的10进制整数”

    （而非原码）

  • B2T的正确翻译：用补码存储的解读方式把二进制原码转化成10进制整数

• 对于无符号数：同理

操作类型

• 因为没有介绍原码和补码，这里通用没有讲减法。其实减法相当于：加((unsigned)补码的非)

• 这章的截断和加法乘法非等运算，并无涉及到机器层次做法

  补码和无符号数的加法和乘法这里反而着重讲如何用10进制计算来获得机器计算的结果

  仅供使用的计算方法和机器不同，但这里只是强调什么运算、什么结果，而不强调计算过程

其他理解

下面的符号不应该指的是一个过程，虽然类型是一个函数但不是一个操作？？？

符号	类型	含义（翻译不太对啊）
B2Tw	函数	二进制（目标数）转补码（国内教程经典理解：补码转原码）
B2Uw	函数	二进制（目标数）转无符号数
U2Tw	函数	无符号数转补码
U2Bw	函数	无符号数转二进制
T2Bw	函数	补码（计算机存储形式）转二进制数
T2Uw	函数	补码（计算机存储形式）转无符号数
TMinw	常数	最小补码值
TMaxw	常数	最大补码值
UMaxw	常数	最大无符号数
$+^t_w$	操作	补码加法
$+^u_w$	操作	无符号数加法
$*^t_w$	操作	补码乘法
$*^u_w$	操作	无符号数乘法
$-^t_w$	操作	补码取反
$-^u_w$	操作	无符号数取反

英文

• 无符号数（Unsigned）
• 补码（Two's-complement）
• 二进制（Binary）

该书符号举例

• 无符号数编码
  • $B2U_4([0001])=1=[0001]$
  • $B2U_4([1111])=15$
• 有符号数编码
  • $B2T_4([0001])=1$
  • $B2T_4([1111])=-1$
• 有符号转无符号
  • $T2U_{16}(-12345)=53191$

国内符号举例

• $[+13]_原=00001101$、$[+13]_反=00001101$、$[+13]_补=00001101$
• $[-13]_原=10001101$、$[-13]_反=11110001$、$[-13]_补=11110010$

整数数据类型

C语言整型数据类型的典型取值范围：（long和char *在32、64位程序上字节数不同）（注意short [int]，long [int]简写）

C数据类型	32位 - 最小值	32位 - 最大值	64位 - 最小值	64位 -最大值
[signed] char	-128	127	-128	127
unsigned char	0	255	0	255
short	-32768	32768	-32768	32768
unsigned short	0	65535	0	65535
int	-2147483648	2147483647	-2147483648	2147483647
unsigned	0	4294967295	0	4294967295
long	-2147483648	2147483647	-9223372036854775808 = 9e+18 = 9艾	9223372036854775807 = 9e+18 = 9艾
unsigned long	0	4294967295	0	18446744073709551615 =18e+18 =18艾
int32_t	-2147483648	2147483647	-2147483648	2147483647
uint32_t	0	4294967295	0	4294967295
int64_t	-9223372036854775808	9223372036854775807	-9223372036854775808	9223372036854775807
uint64_t	0	18446744073709551615	0	18446744073709551615

2字节的int

上表没有标明：有些机器int可以用2字节来实现，范围同short类型

也可以无歧义声明：int16_t / uint16_t

最值记法

有符号数|最小值|>|最大值|

记法：需要补码（负数）和不需要补码（非负数）的数对半开

圆一圈256。0不需要补码（非负数）。即unsigned 128对应的位置需要补码，为负数

C和Java

C和C++都支持有符号（默认）和无符号数。Java只支持有符号数。

无符号数的编码

还是1248法好用

$$B2U_w(\vec{x})=\sum^{w-1}_{i=0}x_i2^i \\ 唯一性、双射$$

补码编码

这里的B实质上是补码而非原码

$$B2T_w(\vec{x})=-x_{w-1}2^{w-1}+\sum^{w-2}_{i=0}x_i2^i \\ 唯一性、双射$$

B2T是经典的补码转原码问题，公式法如上，但一般多按位来计算较为直观和快捷

按位计算最直观，但要分正数和负数情况，正数不变，当为负数时：

• 两端1不变，中间取反（该方法最快，还要记一下TMin_w的情况）
• 原码 = 反码（全部取反） + 1 法（该方法最好理解，为模算法的原理）

最好再转换为10进制

旁注：有符号数的其他表示方法

反码（Ones' Complement）

$$B2O_w(\vec{x})=-x_{w-1}(2^{w-1}-1)+\sum^{w-2}_{i=0}x_i2^i$$

原码（Sign-Magnitude）

$$B2S_w(\vec{x})=(-1)^{x_{w-1}}\cdot(\sum^{w-2}_{i=0}x_i2^i)$$

这两种编码都有一个奇怪的属性：对数字0有两种不同的编码方式，(+0)!=(-0)

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

$$T2U_w(x)=\left\{ \begin{aligned} &x+2^w,&x<0 \\ &x,&x\geq0 \end{aligned} \right.\\ U2T_w(u)=\left\{ \begin{aligned} &u,&u\leq TMax_w \\ &u-2^w,&u>TMax_w \end{aligned} \right.$$

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

• C语言的有符号、无符号的类型转化不改变底层的位，只改变解释方式
• 计算或比较时，有符号数自动转换为无符号数

扩展一个数字的位表示

较小的数据类型转换成较大的数据类型

• 无符号数转换：零扩展。前面补0即可

• 补码数转换：符号扩展。前面补最高有效位（前面所说的算术右移）

  原理：1001补 > 1111原(-7) > 10000111原(-7) > 11111001补

• 较小补码数转较大无符号数：先改变大小再T2U

  该优先级应注意：负数会变成一个极大而非较大的数

• 较小无符号数转较大补码数：应该也是先改变大小再U2T

  该优先级原因：绝对无损变换，先扩展补数的正数区域则可以有效避免损失

截断数字

较大的数据类型转换成较小的数据类型

• 截断无符号数：直接截断

  • 例：7[0111] > 7[111]（无损）
  • 例：15[1111] > 7[111]（有损）

• 截断补码数值：先转换为无符号数截断，再转换回补码

  原理：这个用画圆法也都不好理解，可以死记一下。理解时可以假设只截断一位：

  • 用画圆法模型来看。截断一位：中心对称。截断多位：多次中心对称并每次把圆周缩小一半
  • 当截断补码没有损失信息时：补码所转的无符号数一定被截断了！使得无符号数的位置发生对称，新的位置到达半圆的距离为补码的信息。
  • 例：

$$无符号数截断结果：\\ B2U_k([x_{k-1},x_{k-2},\cdots,x_0])=B2U_w([x_{w-1},x_{w-2},\cdots,x_0])mod2^k\\ ~\\ 补码数截断结果：\\ B2T_k([x_{k-1},x_{k-2},\cdots,x_0])=U2T_k(B2U_w([x_{w-1},x_{w-2},\cdots,x_0])mod2^k)\\ ~\\ 重要提示！\\ \begin{align} &补码截断公式中的B2U_w中的B是补码形式存储的\\ &-1[1001]在里面存储为15[1111],转换为无符号数应为15而非9\\ &即截断结果为(-1)而非(1) \end{align}$$

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

多数语言认为无符号数麻烦多，不支持无符号数

• 不适合场合（较小数字的运算就已经会出现问题了，易出bug）：

  • 会改变与其运算的有符号数的值、运算结果不能为负

    1_u - 2_t == 1_u + (16^4-2)_u == (16^4-1)_u > 0

    1_u - 2_u == unsigned(-1_t) == (16^4-1)_u > 0

    1_t - 2_t == -1_t < 0

• 适用场合：

  • 无数字意义的位的集合
  • 地址
  • 模运算、多精度运算的数学包

旁注：函数getpeername的安全漏洞

简单来说就是负数len作为memcpy参数自动转化为极大的无符号数

该函数将会复制多达2^31个字节，读到它没有授权的内核内存区以及以外的非法地址（进程的虚拟地址空间），最后导致溢出

整数运算

重要：必看上一节的章前提示

无符号加法

无符号数加法

$$x+^u_wy= \left\{ \begin{aligned} x+y,&\quad\quad x+y<2^w&正常\\ x+y-2^w,&\quad\quad 2^w\leq x+y<2^{w+1}&溢出\\ \end{aligned} \right .$$

无符号数求反

$$-^u_wx= \left\{ \begin{aligned} &x,&x=0\\ &2^w-x,&x>0\\ \end{aligned} \right .$$

溢出检测

$$当且仅当x+^u_wy<x(或者x+^u_wy<y)$$

模数加法形成的数学结构：

阿贝尔群（Abelian group），也称交换群

就是整数环上的模，任何一个循环群必定是阿贝尔群

补码加法

补码加法

$$x+^t_wy=\left\{ \begin{align} x+y-2^w,\quad\quad&2^w-1\leq x+y&&正溢出\\ x+y,\quad\quad&-2^{w-1}\leq x+y<2^{w-1}&&正常\\ x+y+2^w,\quad\quad&x+y<-2^{w-1}&&负溢出 \end{align} \right .$$

溢出检测

$$当且仅当(x>0\quad\&\&\quad y>0\quad\&\&\quad x+^t_wy\leq0)时，\quad正溢出\\ 当且仅当(x<0\quad\&\&\quad y<0\quad\&\&\quad x+^t_wy\geq0)时，\quad负溢出$$

补码的非

所有补码都有加法逆元：补码的非

$$-^t_wx=\left\{ \begin{align} &TMin_w,&x=TMin_w\\ &-x,&x>Tmin_w \end{align} \right. \\\quad\\ -x=~x+1，原理与作用：\\ 用画圆法分别画出：x、-^t_wx、-^u_wx、(unsinged)-^t_wx四条圆弧，并解析其作用，就通透多了$$

区别：补码的非（补码的加法逆元）和无符号的加法逆元相比虽然体现和公式不同，但定义相同：自身加自身的加法逆元等于0

无符号乘法

$$x*^u_wy=(x\cdot y)mod2^w \\\quad\\ 即：先乘法，再无符号截断$$

补码乘法

$$x*^t_wy=U2T_w((x\cdot y)mod2^w) \\\quad\\ 即：先乘法，再补码数截断$$

无符号和补码乘法的位级等价性（推导过程略，理解成数学的意外巧合吧）

$$T2B_w(t1*^t_wt2)=U2B_w(u1*^t_wu2)$$

TMin*-1的Bug：

$$\begin{align} 结论：~&-TMin=TMin_3\\ 计算方法1：~&-1*TMin_3=-1*100_2=100_2=TMin_3\\ 计算方法2：~&-1*TMin_3=-1*100^t_2=U2T(-1*100^u_2)=U2T(4)=-4=Tmin_3\\ 理解方法：~&TMin没有与之对应的正数，用画圆理解就是：做了个左右对称，TMin_w还是自己 \end{align}$$

旁注：XDR库中的安全漏洞

调用分配函数（如malloc）时使用了一个乘法溢出的值作为参数，最终只分配了4096个字节

而复制数据到该缓冲区时，复制数量为溢出的量，会超过malloc缓冲区的大小，最终导致溢出

乘以常数

整数乘法指令慢（旧机器10个以上时钟周期，i7为3个），而其他整数运算快（加减法、位级运算、移位只需要1个时钟周期），因此编译器使用优化

编译器优化：

用移位和加法运算的组合来代替乘以常数因子的乘法（乘法得到的溢出结果和移位得到的溢出结果也是相同的）

但大多数编译器只在需要少量移位、加法和减法就足够的时候才使用这种优化

时钟周期：

也叫振荡周期，定义为时钟频率的倒数。是计算机中最基本、最小的时间单位

一个时钟周期内，cpu仅完成一个基本动作

乘以2的幂

$$x[x_{w-1},x_{w-2},\cdots,x_0]*2^k=[x_{w-1},x_{w-2},\cdots,x_0,0,\cdots,0]=x<<k\\~\\ 应用实例：x*14=x*(2^3+2^2+2^1)=(x<<3)+(x<<2)+(x<<1)=（x<<4）-(x<<1)\\ 其应用和10进制的列式计算一致$$

除以2的幂

整数除法速度比整数乘法更慢：30或更多时钟周期（整数除法是舍入到零的）

优化：同样用移位实现-右移（无符号数使用逻辑右移、补码数使用算术右移）

整数除法定义

$$\begin{align} 向下取整定义&：\left\lfloor a\right\rfloor为向下取整，\left\lfloor a\right\rfloor\leq a<\left\lfloor a\right\rfloor+1\\ 向上取整定义&：\left\lceil a\right\rceil为向上取整，\left\lceil a\right\rceil-1<a\leq\left\lceil a\right\rceil\\ （向零取整）整数除法定义&：向零取整，舍掉小数部分，即正数结果为\left\lfloor a\right\rfloor，负数结果为\left\lceil a\right\rceil \end{align}$$

无符号除法

$$x[x_{w-1},x_{w-2},\cdots,x_0]>>k=[0,\cdots,0,x_{w-1},x_{w-2},\cdots,x_k]$$

补码除法

$$x/2^k= \left\{ \begin{align} &x>>k,&x\geq0\\ &(x+(x<<k)-1)>>k,&x<0 \end{align} \right.\\ 此处的右移为算术右移：x[x_{w-1},x_{w-2},\cdots,x_0]>>k=[x_{w-1},\cdots,x_{w-1},x_{w-1},x_{w-2},\cdots,x_k] \\~\\ 推导：这里的右移是算术右移，上面的(x<<k)-1是偏量值。\\ 负数加偏量值原因：如果直接使用算术右移：其结果是向下取整而非向零取整$$

C表达式

(x<0?x+(1<<k)-1:x)>>k

遗憾的是，这种方法不能推广到除以任意常数（乘法有乘法分配率而除法没有）

关于整数运算的最后思考

浮点数

旁注：IEEE浮点标准

IEEE（电气和电子工程师协会，Institute of Electrical and Electronic Engineers，简称读做“eye-triple-ee”，triple即三倍的意思）

二进制小数

定点表示法

• 二进制小数转十进制分数：就是分母多加一个(2^{小数位数})，同样是1248法
• 二进制小数转十进制小数：1248法的扩展：0.5、0.25、0.125、0.0625

浮点运算不精确的灾难后果（经典）

1991.02.25，海湾战争期间，美国爱国者导弹拦截飞毛腿导弹失败

原因：程序内置的时钟类似一个计数器，每0.1s加1，而这个0.1s用二进制小数值为：0.000110011[0011循环]近似表示

无限循环小数：其实1/10对2进制，就相当于1/3对10进制，或者扩展为1/n对m进制（n不是m的因数）

IEEE浮点表示

IEEE浮点标准

$$V=(-1)^s*M*2^E\\ \begin{array}{l}\\ ~~s：符号（sign）&float：1位&double：1位\\ ~E：阶码（exponrnt,exp字段）&float：8位&double：11位\\ M：尾数（significand,frac字段）&float：23位&double：52位\\ \end{array}$$

根据exp的值，被编码的值可分为三种情况（最后一种有两个变种）

情况	exp值（以float为例）	frac值	情况	解释方法
情况1	不为0或255（8个位不全为0或1）	任意	规格化的	exp被解释为以偏置形式表示的有符号整数
情况2	0 （8个位全为0）	任意	非规格化的	（+0.0!=-0.0）
情况3.a	255 （8个位全为1）	位均为0	无穷大
情况3.b	255 （8个位全为1）	位不均为0	NaN	（NaN!=NaN）

情况2、3可视作对exp的标记

至于标记时要减去全0全1而非减去TMin_w和TMax_w

• 一是因为全0全1的标记if起来更快？
• 二是为了满足升序排列（把浮点数除掉符号位看成是无符号数），正数比较起来会更快

• 情况1：规格的值

$$\begin{aligned} &\begin{aligned} E&=以偏置形式表示的有符号整数\\ &=e-Bias\\ &=(无符号数)-(2^{k-1}-1)&&=(无符号数)-(127)\\ &\subset[-2^{k-1}+1,2^{k-1}]&&\subset[-126,127]\not\subset[-128,127] \end{aligned}\\ \\ &\begin{aligned} E的处理目的：&以偏置形式表示的有符号整数：目的为在减去全0全1的情况下来仍然能表示0这个数\\ &偏置前后的取值范围变化可以用画圆法理解\\ \end{aligned}\\ \\ &\begin{aligned} M&=1+f\\ &=1.f_{n-1}f_{n-2}\cdots f_{0} \end{aligned}\\~\\ &M的处理目的：加1的目的：因为第一位总是1，隐性表示可以获得一个额外精度位\\ \\ &规格化情况：正常情况，用来表示浮点数 \end{aligned}\\$$

• 情况2：非规格的值

$$\begin{aligned} &\begin{aligned} E&=以偏置形式表示的有符号整数\\ &=1-Bias\\ &\neq e-Bias=-Bias\\ &=1-(2^{k-1}-1)=-2^{k-1}+2&&=-126 \end{aligned}\\ \\ &\begin{aligned} E的处理目的：&这里的E并无什么实际作用，主要是用来作为“非规格”的标记，影响M的处理规则\\ &这里可以用作标记的原因：规格化的Exp值使用偏置的方式表示了0，该情况下空闲出来\\ \end{aligned}\\ \\ &\begin{aligned} M&=f\\ &=0.f_{n-1}f_{n-2}\cdots f_{0} \end{aligned}\\ \\ &M的处理目的：这里不用加1，目的是使之能够表示极其小的数和0\\ \\ &\begin{aligned} 范围补充：&这里E的值为-126而非“规格化”范围的外的-127，是因为这里的M少了一个隐性精度\\ &事实两者的值域是贴着的\\ &非规格化的最大值=0.1[1循环]*2^{126}=1.0*2^{126}+1=规格化的最小值+1\\ \end{aligned}\\ &\begin{aligned}\\ 非规格情况：&通过标记识别，有两个用途：能用于表示数值0、和表示非常接近于0.0的数\\ &但第一个用途有个问题：符号位分别为0和1时，+0.0和-0.0被认为是不同的 \end{aligned} \end{aligned}$$

• 情况3：无穷大、NaN

  特殊值

  • 无穷大：表示溢出的结果

    如：大数相乘、除以零、double大数转float

  • NaN（Not a Number）：用来表示非实数或无穷的数

    如：-1的开方、无穷减去无穷

数字示例

这节是举例子

舍入

IEEE浮点格式定义了四种舍入方式，默认方法是找到最接近的匹配，其他三种可用于计算上界和下界

• 向偶数舍入（round-to-even），也称为最接近的值舍入（round-to-nearest）

  不同于整数除法的向零舍入，也不同于向上舍入和向下舍入，其为四舍五入的进化版本：四舍六入五向偶（相当于随机，可减少误差）

• 向零舍入

• 向下舍入

• 向上舍入

应用：二进制舍入：10.Y10000（正中间值：让Y变为0）

浮点运算

• 浮点运算特点

  • 额外指定了一些规则，例：

    1/-0 = -无穷，1/+0 = +无穷

• 浮点加法特点

  • 也有阿贝尔群，在浮点加法下有逆元

    （两个大数相乘或除以0会为无穷，而相加不会？）【?】

    无穷和NaN例外

  • 满足单调性**（无符号或补码的没该属性）**

    a>=b则x+a>=x+b

    （为什么？因为可以用+无穷来取缔溢出？）【?】

  • 不具有结合性，这是缺少的最重要的群属性

• 浮点乘法特点

  • 满足单调性**（无符号或补码的没该属性）**

    a>=b且c>=0则a*c>=b*c

    a>=b且c<=0则a*c<=b*c

  • 不具有结合性，例：（无符号或补码的没该问题）

    (le20*le20)*le-20 = +无穷

    le20*(le20*le-20) = le20

  • 不具有分配性，例：（无符号或补码的没该问题）

    le20*(le20-le20) = 0.0

    le20*le20-le20*le20 = NaN

  • 平方大于0，例：

    a*a>=0（a不等于NaA）

C语言中的浮点数