计算机组成原理-数据的表示和计算

¶简介

计算机组成原理系列其一，主要是针对中国大陆考研所要求的内容对计算机组成原理的知识体系进行总结和梳理，本篇内容主要包含以下几点：

数制的表示
计算机的内部编码
定点数和浮点数
C语言中的数据表示
数据的计算

¶大纲

重点内容会使用黑色加粗表示

数据的表示和计算
- 前置知识
  - 数值转换
  - 计算机运算速度
  - CPU执行时间
- 数制
  - 进位计数法
    - r位进位计数法
    - 不同进制数相互转换方法
  - 定点数的表示
    - 真值和机器数
    - 机器数的定点表示
    - 原码、补码、反码、移码
    - 定点数的移位
      - 算术位移
      - 逻辑位移
      - 循环位移
    - 定点数的加减法
    - 溢出的判别方法
- 浮点数
  - 一般浮点数的表示
  - IEEE 754标准
- C语言中的数据类型及强制类型转换
  - 整数类型的转换
  - 包含浮点数的转换
  - 数据的存储和排列
    - 大端法
    - 小端法
- 拓展
  - 乘2取整法

¶前情提要

数值转换
- 计算机进行数据处理时，一次存取、加工和传送的数据长度称为字，对于不同的品牌CPU 1Word(一个字)通常由一个或多个（一般是字节的整数位）字节构成
- 在描述存储容量和文件大小时，K、M、G、T常用2次幂表示
  - 1Byte = 8bit
  - 1KB = $ 2^{10} $ B = $ 8\times2^{10} $ bit
  - 1MB = $ 2^{20} $ B = $ 8\times2^{20} $ bit
  - 1GB = $ 2^{30} $ B = $ 8\times2^{30} $ bit
  - 1TB = $ 2^{40} $ B = $ 8\times2^{40} $ bit
- 在描述速率、频率时，K、M、G、T常用10次幂表示
  - 1K = $ 10 ^{3} $
  - 1M = $ 10 ^{6} $
  - 1G = $ 10 ^{9} $
  - 1T = $ 10 ^{12} $
  - 1P = $ 10 ^{15} $
常见秒单位：

值	符号	名称	值	符号	名称
分数			倍数
10⁻¹ s	ds	分秒	10¹ s	das	十秒
10⁻² s	cs	厘秒	10² s	hs	百秒
10⁻³ s	ms	毫秒	10³ s	ks	千秒
10⁻⁶ s	µs	微秒	10⁶ s	Ms	兆秒
10⁻⁹ s	ns	纳秒	10⁹ s	Gs	吉秒
常用单位以粗体表示

¶计算机的性能指标

¶几种字长区别

参见计算机组成原理 - 指令系统

¶数据通路带宽

数据通路带宽是指数据总线一次所能并行传送信息的位数。这里所指的数据通路宽度是指外部数据总线的宽度，它与CPU内部的数据总线宽度（内部寄存器的大小）可能不同

CPU内部的数据通路
 外部数据总线带宽

¶运算速度

计算机运算速度
1. CPU时钟周期。通常为主频的倒数，是CPU中最小的时间单位，执行指令的每个动作至少需要1个时钟周期
2. 主频（CPU时钟频率）。机器内部的主时钟的频率，是衡量机器速度的重要参数，以Hz为单位。
3. CPI（Cycle Per Instruction），执行一条指令所需的时钟周期数。（不同指令的时钟周期数可能不同，CPI通常是一个平均值）
CPU执行时间，指运行一个程序所花费的时间
CPU执行时间 = $ \frac {CPU时钟周期}{主频} $ = $\frac {(指令条数\times CPI)}{主频}$
MIPS（Million Instruction Per Second），每秒执行多少百万条指令
MIPS = $ \frac {指令条数}{执行时间 \times 10^{6}} $ = $\frac {主频}{CPI \times 10^{6}}$

¶数制

¶进制计数法

一个r进制数($ K_n K_{n-1} K_{n-2} …… K_{0} K_{-1} …… K_{-m} $)可以表示为：
$ K_n r^n + K_{n-1}r^{n-1} + …… K_{0}r^{0} $ $+ K_{-1}r^{-1} + …… K_{-m}r^{-m} = \sum_{i=n}^{-m} K_ir^i $ 其中r是基数，$r^i$ 是第i位的位权（整数位最低位规定为第0位），$K_i$的取值可以是0，1，…… r-1共r个数码中的任意一个
不同进制数之间的互相转换
1. 二进制与八进制和十六进制可以很方便的互相转换
2. 任意进制转换为十进制数:将任意进制数的各位数码与他们的权值相乘，再将乘积相加即可
  例如：$ (11011.1)_2 = 1\times 2^4 + 1\times 2^3 + 0\times 2^2 + 1\times 2^1 + 1\times 2^0 + 1\times 2^{-1} = 27.5 $
3. 十进制转换为任意进制数:

¶定点数的编码表示

¶真值和机器数

真值：日常生活中使用正负号表示的数字，例如：-19、20。真值是计算器所代表的实际值
机器数：计算机中通常把数的符号和数值部分一起编码，通常用“0”表示正、“1”表负。这种把符号和数值一起编码的数称为机器数。常用的有原码、补码、反码、移码。例如：0,101（这里的“,”仅区分符号位和数值位）表示+5

¶机器数的定点表示

计算机组成原理-数据的表示和计算_2

¶原码、补码、反码、移码

对于这几种码的相互转换、适用范围、原码和补码的表示范围、补码原码的加减运算等要重点关注

用机器数的最高位表示符号位(单符号位)，其余各位表示数的绝对值
例如：$ x_1 = +0.1101， x_2 = -0.1101 $，字长为8位，其原码表示为$ [x_1]_原$ = 0，1101000 ， $ [x_2]_原$ = 1，1101000，其中最高位为符号位
原码中的真值零有正零和负零两种形式，$ [+0]_原$ = 0，0000和 $ [-0]_原$ = 1，0000，而补码的零是唯一的
双符号位表示: 00表示正，11表示负，其中第一位数字表示真正的符号，第二位数字可以用于溢出判断，即01、10表示发生溢出需要进行右移保持符号位不变
四种码的相互转换

¶定点数的移位

定点数的移位主要包括：算数移位、逻辑移位、循环移位

算术移位：算术移位的操作对象是有符号数，其在移位过程中的符号位要保持不变(只移动数值位，其右添补0或1看符号位，左移添补0或1)，左移一位相当于乘以2;右移一位相当于除以2
- 对于正数由于$ [ x]_原 $ = $ [ x]_补 $ = $ [ x]_反 $ = 真值，因此对于移位(左移和右移)后的空位均添0补充
- 对于负数：
  - 原码表示：左移和右移均添0补充
  - 补码表示：左移添0补充，右移添1补充（对于补码来说，其由低向高位找到的第一个“1”，在此“1”的左边各位均与对应的反码相同，在此“1”右边(包括此“1”)均与对应的原码相同）
  - 反码表示：左移和右移均添1补充
  - 误差分析：
    - 对于正数、负数原码，左移时高位丢1，结果出错；右移时低位丢1，影响精度
    - 对于负数补码，左移时高位丢0，结果出错；右移时，地位丢1，影响精度
    - 负数反码，左移时高位丢0，结果出错；右移时低位丢0，影响精度
逻辑移位：逻辑移位将操作数视作无符号数，其左移或右移时均添0补充
循环移位：将移出的数位又移入数据中，循环移位适合将数据的低字节数据和高字节数据互换

¶定点数的加减法，乘除（此处不做重点说明）

补码的加减运算规则：
- 按二进制运算规则运算
- 若做加法，直接两数补码相加；若做减法，则先将减数转化为对于的负数再与被减数相加
- 符号位与数值位一起运算，加、减结果的符号位也在运算中直接得出
- 最终的运算结果的高位丢弃，保持位数不变，运算结果也为补码
例子：

¶溢出的判别方法

计组-数据的表示和计算_10

¶浮点数

对于浮点数的学习可以类比十进制的科学计数法来比较学习

¶一般浮点数的表示

表示格式：$ N=(-1)^S \times M \times R^E $
- S取值为0或1，用来决定浮点数的符号
- M是一个二进制定点小数，称为尾数，一般使用定点原码小数表示，尾数的位数反映了浮点数的精度
- E是一个二进制定点整数，称为阶码，常用移码表示。阶码的值反映了浮点数小数点的实际位置，阶码的位数反映了浮点数的表示范围
- R是基数，一般是隐含的，可以取值为2、4、8等
浮点数的规格化
浮点数的尾数位数决定了浮点数的有效位数，有效位越多，数据的精度越高，浮点数的规格化就是为了使得尾数保留更多的有效位数。规格化的操作是通过调整一个非规格化的浮点数的尾数和阶码的大小，使得非零的浮点数在尾数的最高数位上保证是一个有效值（即值为1）
1. 规格化操作
  - 左规：当运算结果的尾数最高数位不是有效位时，即$ \pm0.0……01XXX $的形式时需要进行左规，左规时，尾数每左移一位、阶码减1(以基数为2，下同)。左规可能需要多次
  - 右规：当运算结果的尾数的有效位进位到小数点前时，需要右规。尾数右移一位、阶码加1。右规需要进行一次
  - 为何只需要进行一次？当浮点数运算的结果使尾数溢出（即使用双符号位表示时为01或10）时，Example：
    
    $ a = +2^2 \times 00.1100 $
    $ b = +2^2 \times 00.1000 $
    $ a+b = 2^2 \times(00.1100+00.1000) = 2^2 \times 01.0100$
    $ \mathtt{=>^{右规} 2^3 \times 00.1010} $
2. 用原码表示的规格化尾数（基数为2）的形式如下：
  1. 正数为0.1xx……xx的形式，最大值表示为0.11……1，最小值为0.100……0
  2. 负数为1.1xx……xx的形式，最大值表示为1.10……0，最小值表示为1.11……1
浮点数的加减运算
浮点数的运算特点是阶码运算和尾数运算分开进行，加减运算分为以下几步
1. 对阶
  对阶的目的是使两个操作数的小数点位置对⻬，即使得两个数的阶码相等。为此，先求阶差，然后以小阶向大阶看⻬的原则，将阶码小的尾数右移一位(基数为2)，阶加1，直到两个数的阶码相等为止。尾数右移时，舍弃掉有效位会产生误差，影响精度
  （类比科学计数法将$ 98.11 \times 10^2 + 8.11 \times 10^3 $转变为$ 9.811 \times 10^3 + 8.11 \times 10^3$）
2. 尾数求和
  将对阶后的尾数按定点数加(减)运算规则运算。运算后的尾数不一定是规格化的，因此，浮点数的加减运算需要进一步进行规格化处理。
3. 规格化
  参照上方规格化规则，对于IEEE 754规格化的尾数形式为$ \pm 1.xxxx $，因为IEEE 754尾数的最高位默认隐含为1所以规格化时的主要区别就是要将有效位移到小数点左边一位（即小数点左边只能为1）
4. 舍入
  在对阶和尾数右规时，可能会对尾数进行右移，为保证运算精度，一般将低位移出的两位保留下来，参加中间过程的运算，最后将运算结果进行舍入，还原表示成IEEE 754格式。
  常见的舍入方法有:
- 舍1入法:类似于十进制的“四舍五入”法。运算结果保留位的最高数位为0，则舍去;最高数位为1，则在尾数的末位加1。这样可能会使尾数溢出，此时需再做一次右规。
- 恒置1法:不论丢掉的最高数位是0还是1，都把右移后的尾数末位恒置1
- 截断法:直接截取所需位数，丢弃后面的所有位，这种舍入处理最简单
1. 溢出判断
  在尾数规格化和尾数舍入时，可能会对阶码执行加/减运算。因此，必须考虑指数溢出的问题。
  若一个正指数超过了最大允许值(127或1023)，则发生指数上滥，产生异常
  若一个负指数超过了最小允许值(-126或-1022)，则发生指数下溢，通常把结果按机器零处理。
  - 右规和尾数舍入。数值很大的尾数舍入时，可能因为末位加1而发生尾数溢出，此时需要通过右规来调整尾数和阶。右规时阶加1，导致阶增大，因此需要判断是否发生了指数上溢。当调整前的阶码为11111110时，加1后，会变成11111111而发生指数上滥。
  - 左规。左规时阶减1，导致阶减小，因此需要判断是否发生了指数下溢。其判断规则与指数上溢类似，左规一次，阶码减1，然后判断阶码是否为全0来确定是否指数下滥。
  - 由此可见，浮点数的溢出并不是以尾数溢出来判断的，尾数溢出可以通过右规操作得到纠正。运算结果是否溢出主要看结果的指数是否发生了上溢，因此是由指数上滥来判断的。

¶IEEE 754标准

现代计算机中，一般都以IEEE 754标准存储浮点数，IEEE标准用: $V=(-1)^S \times M \times 2^E $来表示一个浮点数

¶简介

符号: S决定这个数是正数还是负数
尾数: M是一个二进制小数，采用隐藏位的原码（隐藏位是指隐藏尾数了小数点左边的1）
阶码: E是对浮点数进行加权，权重是2的E次幂，使用移码表示
- 移码 = 原码+偏移值（float型为127，double型为1023）
- 在手算阶码时可以将其视为无符号数计算，然后再减去（加上）偏移值即可得到原码（移码也即阶码），使用十进制计算再转为二进制较为方便

在IEEE 754标准中:

规格化的短浮点数的真值为：$ (-1)^S \times 1.M \times 2^{E-127} $
规格化的短浮点数的真值为：$ (-1)^S \times 1.M \times 2^{E-1023} $

计组-数据的表示和计算_12

符号位	阶码	尾数
sign	exponent	fraction

对于不同精度的浮点数，阶码与数值位分配的位数不一样，如下：

精度	数符	阶码	尾数	总位数	偏移值
短浮点数(C中的float)	1	8	23	32	$127_{(10)}$ \|\| $7F_{(16)}$
长浮点数(C中的double)	1	11	52	64	$1023_{(10)}$ \|\| $3FF_{(16)}$

对于32位的单精度浮点数，符号位分配是1位，阶码分配了8位，尾数分配了是23位（实际上是24位，隐藏了隐含小数点左边的1）。

根据这个标准，我们来尝试把一个十进制的小数转换为IEEE 754标准表示。

¶规格化的值

最普遍的情况，当exp的位模式不全为0（数值0），也不全为1（单精度255，双精度2047）
例如：178.125

先把浮点数分别把整数部分和小数部分转换成2进制
1. 整数部分用除2取余的方法，求得：10110010
2. 小数部分用乘2取整的方法，求得：001
3. 合起来即是：10110010.001
4. 转换成二进制的浮点数，即把小数点移动到整数位只有1，即为：1.0110010001 * 2^111，111是二进制，由于左移了7位，所以是111
把浮点数转换二进制后，这里基本已经可以得出对应3部分的值了
1. 数符：由于浮点数是正数，故为0.(负数为1)
2. 阶码 : 阶码的计算公式：阶数 + 偏移量，阶码是需要作移码运算，在转换出来的二进制数里，阶数是111(十进制为7)，对于单精度的浮点数，偏移值为01111111(127)[偏移量的计算是：$ 2^{(e-1)} - 1 $， e为阶码的位数，即为8，因此偏移值是127]，即：111+01111111 = 10000110
3. 尾数：小数点后面的数，即0110010001
4. 最终根据位置填到对位的位置上：

数符	阶码	尾数
0	1 0 0 0 0 1 1 0	0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

阶码与尾数之间隐含小数点

可能有个疑问：小数点前面的1去哪里了？由于尾数部分是规格化表示的，最高位总是“1”
我们将尾数定义为M=1+f，小数字段被描述为小数值f，其中0<=f<1，其二进制表示为：
IEEE浮点表示
也就是二进制小数点在最高有效位的左边。
我们也可以把M看成一个二进制表达式为下图的数字，也总能调整阶码使得尾数M的范围在1到2之间。
IEEE浮点表示_2

既然第一位总是1，那就可以直接隐藏不需要显示出来，同时也能够获得一个额外的精度位。

¶非规格化的值

当阶码全为0时，所表示的数非规格化的形式。这种情况下，阶码的值是1-Bias，尾数M=f，也就是小数字段的值，不包含隐含开头的1。
非规格化有两个用途：

一、是提供一种表示数值0的方法，因为使用规格化的数我们必须使M>=1，无法表示0。
二、是表示那些非常接近0的数。

¶定点、浮点表示的区别

在字长相同时，浮点数取字长的一部分作为阶码，所以表示的范围比定点数要大，但是由于字长固定也就意味着尾数部分的有效位数减少，精度就要比定点数有所降低

计组-数据的表示和计算_13

¶C语言中的数据类型及强制类型转换

在C语言中常会用到强制类型转换，C中对定点整数的存储是使用补码形式，常见的转换有char->int->long->double和float->double。从前到后的范围和精度都是从小到大，转换的过程中没有损失

¶整数类型的转换

无符号<---->有符号：不改变数据内容，只改变对其的解释方式
长整数 ---->短整数：高位截断，只保留低位
短整数 ---->长整数：
- 无符号数，进行高位“0”拓展
- 有符号数，高位用原符号位拓展

¶包含浮点数的转换

int转换为float时，虽然不会发生溢出，但float尾数连隐藏位共24位，当int型数的第24~31位非0时，无法精确转换成24位浮点数的尾数，需进行舍入处理，影响精度。
int或float转化为double时，因double的有效位数更多，因此能保留精确値。
double转换为float时，因float表示范围更小，因此大数转换时可能会发生滥出。此外，由于尾数有效位数变少，因此高精度数转换时会发生舍入。
float或double转换为int时，因int没有小数部分，因此数据会向0方向截断(仅保留整数部分)，发生舍入。另外，因int表示范围更小，因此大数转换时可能会溢出。

机器字长	char	short	int	long	float	double
32位机	1B	2B	4B	4B	4B	8B
64位机	1B	2B	4B	8B	4B	8B

¶数据的存储和排列

大端法和小端法
数据按照“边界对齐”的方式存储

¶典型例题

P11-22
P17-20-23
P32-28-30
P51-(33,37)-(38,44)-41

¶拓展

¶乘2取整法

考虑一个十进制小数0.123，我们可以用“乘10取整”法得到它的每一位小数：第一位小数是0.123 *10=1.23，取整数1；第二位小数：0.23 *10=2.3，取整数2

上面的方法供你直观理解，下面我们从数学的角度分析其中的原理。

现在有一个十进制小数为0.625，要把它转换为二进制小数，我们需要找到它的每一位。记这个二进制小数点后第1位是$a_1$，第二位是$a_2$，……，那么这个小数的值就是$ a_1 \ast {\frac{1}{2}}^{-1}+a_2 \ast {\frac{1}{2}}^{-2}+a_3 \ast {\frac{1}{2}}^{-3}+… $ 。现在我们的目标是根据0.625找到对应的$ a_1，a_2，a_3$ ，…使得$ 0.625=a_1 \ast {\frac{1}{2}}^{-1}+a_2 \ast {\frac{1}{2}}^{-2}+a_3 \ast {\frac{1}{2}}^{-3}+… $

在等式两边同时乘以2，得到$1.25=a_1 \ast {\frac{1}{2}}^{0}+a_2 \ast {\frac{1}{2}}^{-1}+a_3 \ast {\frac{1}{2}}^{-2}+…$

我们发现，左边的整数部分1对应右边的$a_1$，也就是二进制小数的第一位，于是$a_1=1$，对于剩下的部分：

$0.25=a_2 \ast {\frac{1}{2}}^{-1}+a_3 \ast {\frac{1}{2}}^{-2}+…$

我们再次乘以2，得到$0.5=a_2 \ast {\frac{1}{2}}^{0}+a_3 \ast {\frac{1}{2}}^{-1}+… $于是$a_2=0$

再乘以2，得到$1=a_3 \ast {\frac{1}{2}}^{0}+…$，于是$a_3=1$，到这里，所有的数都消耗完了，我们找到了0.625对应的二进制小数：0.101

参考文献：
《王道考研-计算机组成原理复习指导》
《Computer Systems A Programer’s Perspective Third Edition》