数据的表示与运算

原码、反码、补码

深入理解计算机系统

无符号数

对向量$\vec{x}=\{x_{w},x_{w-1},...,x_{1}\}$:

$$B2U_w(\vec{x})=\sum\limits_{i=1}^{w}x_i2^{i-1}$$

• 值的范围: 最小值$\vec{x}=[0,0,...,0]$，其整数值为$U_{Min}=0$; 最大值$\vec{x}=[1,1,...,1]$，其整数值为$U_{Max}=\sum\limits_{i=1}^{w}=2^{w}-1$.

补码

对向量$\vec{x}=\{x_{w},x_{w-1},...,x_{1}\}$:

$$B2T_w(\vec{x})=-x_{w}2^{w-1}+\sum\limits_{i=1}^{w-1}x_i2^{i-1}$$

• 值的范围: 最小值$\vec{x}=[1,0,...,0]$，其整数值为$T_{Min}=-2^{w-1}$; 最大值$\vec{x}=[0,1,...,1]$，其整数值为$T_{Max}=\sum\limits_{i=1}^{w-1}=2^{w-1}-1$.
• $|T_{Min}|=|T_{Max}|+1$.

王道原码

王道这里的定义，等式右侧为无符号整数对应的编码，将其硬解为对应编码，即可得到等式左侧数值。(感觉非常奇怪不如csapp好理解)

纯小数 原码定义

• 纯小数原码

表示范围: $-1+2^{-n}{\leq}x{\leq}1-2^{-n}$

$$\begin{aligned} [x]_{\text{原}}= \left\{ \begin{array}{lr} x, & 1>x{\geq}0 \\ 1-x=1+|x|, & 0{\geq}x>-1 \end{array} \right. \end{aligned}$$

• 纯整数原码

表示范围: $-2^{n}+1{\leq}x{\leq}2^{n}-1$

$$\begin{aligned} [x]_{\text{原}}= \left\{ \begin{array}{lr} 0,x, & 2^n>x{\geq}0 \\ 2^n-x=2^n+|x|, & 0{\geq}x>-2^n \end{array} \right. \end{aligned}$$

王道补码

纯小数 补码定义

• 纯小数原码

表示范围: $-1{\leq}x{\leq}1-2^{-n}$(较原码多-1)

$$\begin{aligned} [x]_{\text{补}}= \left\{ \begin{array}{lr} x, & 1>x{\geq}0 \\ 2+x=2-|x|, & 0>x{\geq}-1 \end{array} \right. \end{aligned}$$

• 纯整数原码

表示范围: $-2^{n}{\leq}x{\leq}2^{n}-1$(较原码多-$2^n$)

$$\begin{aligned} [x]_{\text{补}}= \left\{ \begin{array}{lr} 0,x, & 2^n>x{\geq}0 \\ 2^{n+1}+x=2^{n+1}-|x|, & 0{\geq}x{\geq}-2^n \end{array} \right. \end{aligned}$$

原码、反码、补码、移码之间的转换

注:对于整数原码、反码、补码都相同

• 原码->反码: 负数所有数值位按位取反
• 原码->补码: 负数从右往左找第一个1，这个1左边所有的数值位按位取反
• 反码->补码: 负数末位+1
• $[x]_{\text{补}}$->$[-x]_{\text{补}}$: 从右往左找第一个1，这个1左右所有位按位取反

运算器

运算器的作用:用于实现算数运算(加减乘除)、逻辑运算(与或非)

• ACC:累加器，用于存放操作数，或运算结果
• MQ:乘商寄存器，在乘、除运算时，用于存放操作数或运算结果
• X:通用的操作数寄存器，用于存放操作数
• ALU:算数逻辑单元，通过内部复杂的电路实现算数运算、逻辑运算

		加	减	乘	除
Accumulator	ACC	被加数、和	被减数、差	乘积高位	被除数、余数
Multiple-Quotient Register	MQ			乘积、乘积低位	商
Arithmetic and Logic Unit	X	加法	减法	被乘数	除数

乘法

原码乘法

说明:

• 符号位单独处理，$x_s{\oplus}(\text{异或})y_s$
• 数值位取绝对值进行乘法计算
• 寄存器位数保持统一，都为$n+1$(小数部分为$n$，符号位为$1$位)。
• 逻辑右移，高位补0
• 先加法，再移位，重复n次，即乘数的符号位不参与运算(MQ的位数位为$n+1$，第n次加法且移位后，MQ最低位为符号位，此时执行完成)
• 运算次数: 加法$n$次，移位$n$次。

注:这里双符号位仅仅是为了与补码乘法对齐。

补码乘法

说明: 若小数的位数为n，则:

• MQ的位数为$n+2$，其中最后一位为辅助位
• 若辅助位-辅助位前一位=1时，则$(\text{ACC})+[x]_{\text{补}}$
• 若辅助位-辅助位前一位=0时，则$(\text{ACC})+0$
• 若辅助位-辅助位前一位=-1时，则$(\text{ACC})+[-x]_{\text{补}}$
• 其他位置的寄存器位数保持统一，都为$n+2$，因此在ACC和X处采用双符号位补码运算。
• 乘数MQ处采用单符号位补码。
• 运算次数: 加法$n+1$次，移位$n$次。($n$为数值为大小)

使用Booth算法求解的过程如下图所示:

原码乘法和补码乘法

• 符号位、数值位:
  原码乘法的符号位通过异或确定，数值位由被乘数和乘数的绝对值进行n轮加法、移位。
  补码乘法的符号位和数值为都是由被乘数和乘数进行n轮加法、移位，最后再多来一次加法。

• 每次做的加法:
  原码乘法每次加法可能$+0$、$+[|x|]_{\text{原}}$
  补码乘法每次加法可能$+0$、$+[x]_{\text{补}}$、$+[-x]_{\text{补}}$

• 每次的移位操作:
  原码乘法逻辑右移
  补码乘法补码的算数右移

• 符号位是否参与运算:
  原码乘法不参与运算
  补码乘法参与运算

除法

原码除法:恢复余数法

说明:

• 符号位单独处理，$x_s{\oplus}(\text{异或})y_s$
• 数值为取绝对值进行除法计算
• 寄存器位数保持统一，都为$n+1$(小数部分为$n$，符号位为$1$位)。
• 注意:进行最后一步商时，商为$n+1$位，若最后一位为$1$，且$\text{余数}<0$，则说明此时仍需恢复余数，即将商的最后一位改为$0$，并恢复余数。
• 运算次数: 商为$n+1$位时，左移$n$次，根据最后的余数是否位负判断是否需要在进行加一次的操作。

原码除法:加减交替法(不恢复余数法)

说明:

• 符号位单独处理，$x_s{\oplus}(\text{异或})y_s$
• 数值为取绝对值进行除法计算
• 寄存器位数保持统一，都为$n+1$(小数部分为$n$，符号位为$1$位)。
• 若最后一步商余数为负，也需要恢复余数并商0
• 运算次数: 商为$n+1$位时，左移$n$次，加法$n+1$或$n+2$次，根据最后的余数是否位负判断。

原码除法:恢复余数法 与 加减交替法(不恢复余数法)

• 恢复余数法: 当余数为负时，商0，并$+[\text{除数}]$，再左移。
• 加减交替发: 当余数为负时，商0，并左移，$+[\text{除数}]$，得到下一个余数。当余数为正时，商1，并左移，$-[\text{除数}]$，得到下一个余数。

补码除法:加减交替法

说明:

• 符号位参与运算
• 被除数/除数、除数采用双符号位

过程:
被除数和除数同号，则被除数减去除数，异号则被除数加上除数。
余数和除数同号，商1，余数左移一位减去除数。
余数和除数异号，商0，余数左移一位加上除数。
重复n次。

原码除法和补码除法的区别

强制类型转换

• 无符号数和有符号数不改变数据内容，改变解释方式。
• 长整数变短整数，高位截断，保留低位。
• 短整数变长整数，符号扩展。

边界对齐

假设机器字长为32位

• 半字: 16bit
• 字: 32bit
• 字节: 8bit

浮点数

• 阶码: 常用补码或者移码表示的定点整数。反应浮点数的表示范围及小数点实际位置。
• 尾数: 常用原码或者补码表示的顶点小数。其数值部分的位数n反应了浮点数的精度。

浮点数的规格化

规格化浮点数: 规定尾数的最高数值位必须是一个有效值。

左规: 当浮点数运算的结果为非规格化数时要进行规格化处理，将尾数算数左移一位，阶码$+1$。

右规: 当浮点数运算的结果尾数出现溢出(双符号位为01或10)时，将尾数算数右移一位，阶码$+1$。

IEEE754

浮点数加减运算步骤:

• 对阶
• 尾数相减
• 规格化
• 舍入
• 判溢出

位数

	char	char*	short	int	unsigned int	float	double	long	long long	unsigned long
32位机器	1	4	2	4	4	4	8	4	8	4
64位机器	1	8	2	4	4	4	8	8	8	8

参考资料

[1] 王道计算机组成原理