《计组》数据的表示和运算

数制

• 字节是最基本的信息单位【B】
• 位是最小的信息单位【bit】
• 1字节（B） = 8位（bit）
  • 二进制编码好处
    • 二进制运算规则简单
    • 制造两个稳态的物理器间较容易
    • 便于使用逻辑门电路实现算术运算
• 进位计数制
  • 十进制【Decimal system】【D】
  • 二进制【Binary】【B】
    • 如101.11 = 5.75
  • 八进制【Octal number system】【O】
    • 把二进制的三位一组就是八进制
  • 十六进制【Hexadecimal】【H】
    • 把二进制的四位一组就是十六进制
    • 范围：0~9 + ABCDEF
• 数制的相互转换
  • 二进制$\rightarrow$八进制或十六进制
    • 
  • 任意进制$\rightarrow$十进制
    • 
  • 十进制$\rightarrow$任意进制
    • 

无符号数

• 寄存器的位数决定了无符号数的表示范围，如8位寄存器，无符号数表示范围为0-255
• 用无符号数表示主存地址
• 8位无符号数的范围：0~255
• 16位无符号数的范围：0~65535

有符号数

真值和机器数

• 真值：+5
• 机器数：01【0表示正，1表示负】

原码，补码，反码

• 正负数都使用原码表示，则出现以下情况
  • 1的原码0000 0001，-1的原码1000 0001，则 1 + (-1) = 0000 0001 + 1000 0001 = 1000 0010,结果非0
  • 因而原码可以表示正数，但不能表示负数
• 为了表示负数，引入补码【二进制的补数】
  • 补码重要法则：(二进制的值取反 + 1) + （原本的值） = 0
  • 【获取 -1 的补码过程】 原码 1000 001 $\underrightarrow{取反得到反码（符号位不动）}$ 1111 1110 $\underrightarrow{加1得到补码}$
  • 【获取补码表示的值】补码1111 1111 $\underrightarrow{求解补码的补码}$原码 1000 0001（对应二进制-1）
• 无符号数和有符号数表示的范围【补码表示范围】
  • 8位补码表示的整数范围是-128~127
  • short和unsigned short都是2字节（16位）的变量
  • 有符号数
    • short表示范围：-32768~32767（$-2^{n-1}~2^{n-1}-1$）
    • 负数比正数多一的原因
      • 最高位为0的正数，有0~32767共32768个【包括0】
      • 最高位为1的负数，有-1~32768个【不包括0】
  • 无符号数
    • unsigned shorty表示范围：0~65535（$2^{16} - 1 = 65535$）
• 补码优点
  • 0的补码表示唯一，都是0000 0000
  • 补码运算规则简单，且符号位可以和数值为一起参加运算
  • 补码比原码和反码多表示一个最小负数（-128）

BCD码

• 【8421码】有权码
  • 四位数权值分别为8,4,2,1
  • 2个8421码加的结果大于9（1001），则需要修正，结果加一个6（0110）
  • 如8$\rightarrow$1000，9$\rightarrow$1100
• 【余3码】无权码
  • 在8421基础上加3（0011）
  • 如8$\rightarrow$1011,9$\rightarrow$1100
• 【2421码】有权码
  • 四位数权值分别为2,4,2,1
  • 大于等于5的4位二进制中最高位为1，小于5的最高位为0
  • 如5$\rightarrow$1011而不是0101

移码

• 移码常用来表示浮点数的阶码，只能表示整数
• 整数的补码和移码符号位相反，数值位相同
• $[a]_移 = 2^n + x(2^n > a \leq -2^n,机器字长为 n+1 )$
• 如$x_1 = + 10101$,字长为8位，$[x_1]_移 = 2^7 + 10101 = 10010101$
• 如$x_2 = -10101,$字长为8位，$[x_2]_移 = 2^7 + (-10101) = 01101011$

码之间的转换

原码$\rightarrow$反码$\rightarrow$补码

• 正数
  • 原码（便于人类理解）$\underleftrightarrow{不变}$反码（中间量）$\underleftrightarrow{不变}$补码（更便于计算机运算）
    • 例：a = +19,$[a]_原 = 0001 0011 \rightarrow [a]_反 = 0001 0011 [a]_补 = 0001 0011$
• 负数
  • 原码$\underleftrightarrow{符号位不变，数值位取反}$反码$\underleftrightarrow{末位+1}$补码
  • 例：a = -19,$[a]_原 = 1001 0011 [a]_反 = 1110 1100 [a]_补 = 1110 1101$

原码$\rightarrow$补码

• 获取-1的补码过程
  • 原码1000001$\underrightarrow{取反得到反码（符号位不动）}1111 1110 \underrightarrow{加1得到补码}$ 1111 1111
• 获取补码表示的值
  • 补码1111 1111 $\underrightarrow{求解补码的补数}$原码1000 0001（对应二进制-1）
• 正数
  • 原码$\underleftrightarrow{不变}$补码
    • a = +19 $[a]_原 = 0001 0011 [a]_补 = 00010011$
• 负数
  • • 原码$\underleftrightarrow{从右往左找到第一个1，这个1左边的所有数值位按位取反}$补码
    • a = -19 $[a]_原 = 10010011 [a]_补 = 11101101$

常考数值的原码、反码、补码

基本运算部件

• 逻辑运算基本知识
  • 逻辑非NOT：
  • 逻辑与AND：，全为1时值才为1
  • 逻辑或OR：有一个为1，值就为1
  • 逻辑异或XOR：两个值相同就为1
  • 逻辑运算的对象不是数值，因此不会出现进位的情况
  • 算术逻辑单元ALU的核心部件是加法器

一位全加器【FA】

• 基本概念
  • FA是最基本的加法单元
  • input：加数$A_i$加数$B_i$低位传来的进位$C_{i-1}$
  • output：本位和$S_i$向高位的进位$C_i$
  • 和表达式 = $A_i\bigoplus B_i \bigoplus C_i$
  • 进位表达式$C_i = A_iB_i + (A_i \bigoplus B_i) C_{i-1}$
• 结构图
  • 

串行进位加法器

• 基本概念
  • 串行进位加法器：把n个FA相连得到的n位加法器
  • 每级进位直接依赖于前一级的进位，进位信号逐级形成
  • 最长运算时间由进位信号的传递时间决定
• 

并行进位加法器

• 基本概念
  • 进位信号$G_i = A_iB_i$,进位信号传递信号$p_i = A_i \bigoplus B_i$
  • 进位表达式$C_i = G_i + P_iC_{i-1}$
  • $C_i$仅与$A_i$,$B_i$和最低进位$C_0$有关，相互的进位没有依赖关系
  • CLA（超前进位部件）是实现上述表达式的文件
  • 这种进位方式快速，与位数无关，当位数多时采用全先行进位是不现实的
  • 采用并行进位的目标是：提高加法器运算速度
  • 通常采用两级或多级先行进位加法器
• 结构图
  • 

带标志加法器

• 基本概念
  • 不仅能计算和/差，还能生成相应的标志信息
  • 为了加快加法运算的速度，实际电路一定使用多级先行进位的方式
  • OF：溢出标志
  • SF：符号标志
  • ZF：零标志，当F=0时，ZF=1
  • CF：进位/借位标志，$C_{in} = 0$时，$CF = C_{out};C_{in} = 1$时，$CF = C_{out}$取反
  • A - B < 0 时，CF = 1;溢出时 OF = 1
• 结构图
  • 

算术逻辑单元ALU

• 基本概念
  • ALU的核心是带标志加法器
  • ALU是功能强大的组合逻辑电路，能进行算术运算，逻辑运算，移位操作
  • ALUop是操作控制端，决定ALU所执行的处理操作
  • ALUop的位数决定了操作的种类，位数为3时，有$2^3$ = 8 种操作
  • 在ALUop的控制下，由一个多路选择器MUX选择输出某种操作结果
  • MUX是多路选择开关，它从多个输入信号中选择一个送到输出端
• 结构图
  • 

C语言中的整数类型与类型转换

• 有符号数和无符号数的转换
  • 定义
    • 强制类型转换的结果保持位置不变，仅改变了解释这些位的方式
  • 实例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int main(){
    //例子1
    //x的补码为 1110 1111 0001 1111
    short x = -4321;
    //无符号位y的二进制为 1110 1111 0001 1111 对应真值为61215
    unsigned short y = (unsigned short ) x;
    //输出结果 x = -4312 y = 61215
    printf("x = %d,y = %u\n",x,y);

    //例子2
    //无符号位x2的二进制表示为 1111 1111 1111 1111
    unsigned short x2 = 65535;
    //有符号位y2的二进制表示为 1111 1111 1111 1111

    short y2 = (short)x2;
    //输出结果 x2 = 65535， y2 = -1
    printf("x2 = %u, y2 = %d\n",x2,y2);
    return 0;
}

不同字长整数之间的转换

• 当大字长变量向小字长变量强制类型转换时
  • 系统把多余的高位部分直接截断，低位直接赋值
• 短字长整数到长字长整数的转换时
  • 要是响应的位值相等，也要对高位部分进行填充
  • 原数位无符号整数，填充0
  • 原数位为有符号整数，进行符号填充
• 例：char为8位无符号整数，转换为int时高位补0即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int main(){
    int x = 165537,u = -34991;//int 4B = 32位
    //x，y，u，x十六进制表示为 0x000286a1 0x86a1 0xffff7751 0x7751
    short y = (short)x,v = (short)u;
    //输出 x = 165537,y = -31071
    printf("x =%d,y=%d\n",x,y);
    //输出 u = -34991, v = 30545
    printf("u=%d,v=%d\n",u,v);

    //例子2
    short x1 = -4321;
    int y1 = x1;
    unsigned short u1 = (unsigned short)x1;
    unsigned int v1 = u1;
    //x1,y1,u1,v1十六进制表示为 0xef1f 0xffffef1f 0xef1f 0x0000ef1f
    //输出x1 = -4321，y1 = -4321
    printf("x1 = %d,y1 = %d\n",x1,y1);
    //输出 u1=61215,v1=61215
    printf("u1 = %u,v1 = %u \n",u1,v1);
    return 0;
}

数据的存储和排列

数据的大端方式和小端方式存储

• 用最低有效字节LSB和最高有效字节MSB分别表示数的低位和高位
• short 占2字节 = 16位
• int，float 占4字节 = 32位
• double 占8字节 = 64位
• 大端方式：按MSB到LSB的顺序存储数据
• 小端方式：按LSB到MSB的顺序存储数据
• 
  • 如小端方式中，按字节编制
  • 设int变量i的地址为0800H，i的机器数为01234567H，则地址0800H表示的内容为67H

数据按边界方式对齐方式存储

• 边界对齐相对于边界不对齐，是一种空间换时间的思想
• 存储字长为32位时，半字是2的整数倍，字地址是4的整数倍，字节大小为8位
• 边界对齐虽然浪费了一些存储空间，但是可以提高取指令和取数的速度
• 边界不对齐可以充分利用存储空间，但是效率低
• 
• 例题
  • 

定点数

• 边界不发生移动的数
• 运算过程中可以不考虑定点数是小数还是整数

定点数的运算

• 补码的加减法运算
  • 定义和相关概念
    • 按二进制运算规则计算
    • 符号位和数值位一起参与运算
    • 运算结果的高位被丢弃
  • 实例
    • 
  • 运算电路信号解释

    • 记忆方法	解释	是否有意义
      Zero零	ZF=1表示结果F为0	对无符号和有符号数都有意义
      Overflow溢出	OF=1表示带符号整数运算发生溢出	对无符号数没有意义
      Signal信号	SF表示结果的符号	对无符号数没有意义
      Carry进位	CF表示无符号整数运算时的进位，判断是否发生溢出	对于带符号数运算无意义

• 溢出判别方式
  • 一般用异或门来实现溢出判断电路
  • 仅当两个符号相同的数相加或两个符号相异的数相减时才可能产生溢出
  • 计算时，左边出现溢出，将溢出位丢弃
  • 判断溢出的三个方式
    • 一位符号法
      • 参与操作的两个数符号相同，结果又与原操作数符号不同，则溢出
    • 采用一位符号法根据数据位的进位判断情况判断情况
      • 若符号位的进位和最高数位的进位相同，则没有溢出
    • 采用双符号法/模4补码
      • 模4补码有模2补码的所有优点，且更容易检查溢出问题
      • 模4补码存储时只需要一个符号位
      • 模4补码计算时（在ALU）需要两个符号位
      • 最高位代表真正的符号，低位符号参与移位操作
      • 00表示正数，无溢出
      • 01表示正溢出
      • 10表示负溢出
      • 11表示负数，无溢出

补码乘法运算

• 乘法运算由累加和右移操作实现
  • 原码一位乘法
    • 定义和概念
      • 符号位和数值位时分开求的
      • 符号位不参与运算，同号为正，异号为负
      • 累积符号 = 两个数的符号位的异或
      • 乘积数值 = 两个数的绝对值相乘的结果
      • 积和被乘数采用双符号位
      • 最多进行n次加法运算，n次移位
    • 计算过程
      • 
    • 电路图
      • 
  • 补码一位乘法
    • 定义和概念
      • 一种有符号数的乘法
      • 对多进行n次移位，n+1次加法运算
      • booth算法的移位规则

        • 高位	低位	操作
          0	0	部分积右移一位
          0	1	部分积加$[a]_补$，右移一位
          1	0	部分积加$[-a]_补$，右移一位
          1	1	部分积右移一位

      • 计算过程
        • 
      • 电路图
        • 

除法

• 除法运算由累加和左移（逻辑左移）实现
• 原码除法运算（不恢复余数法）
  • 符号扩展
    • 正数符号位不变，扩展位填充0
    • 负数原码表示和正数表示相同，符号位为1
    • 负数补码符号位不变，附加位用1（对于整数）或0（对于小数）进行填充
    • 如16位补码Ox8FA0扩展位32位为OxFFFF 8FA0
    • 如-64位的补码是1100 0000，则其十六进制为OxFFFF FFC0
  • 该方法商符和商值分开进行
  • 商符由两个操作数的符号位异或形成
  • 计算过程
    • 
  • 电路图
    • 
• 补码除法运算（加减交替法）
  • 该方法符号位和数值位一起参与运算，商符自然形成
  • 根据被除数和除数的符号决定加法还是减法
  • 上商的原则根据余数和除数的符号位共同决定
    • 同号上商1
    • 异号上商0
  • 最后一步商置1
  • 计算过程
    • 
  • 电路图
    • 

移位运算

算术移位

• 算术移位的对象是有符号数，移位过程中符号位保持不变
• 算术左移情况下，补码左移的前提条件是其原最高有效位于原符号位相同【如符号位1，最高有效位1，此时数据不丢失】
• 算术左移实现乘法功能，算术右移实现除法功能
• 例子
  • 十进制-4$[1111 1100]{补}$ 右移两位 $\rightarrow$ 高位填充符号位$\rightarrow [1111 1111]{补}$,即十进制-1，是-4的$\frac{1}{4}$
• 码制及其添补规则
  • 正数+
    • 原，反，补$\rightarrow$0
  • 负数-
    • 原码$\rightarrow$ 0
    • 补码左移$\rightarrow$0
    • 补码右移$\rightarrow$1
    • 反码$\rightarrow$1

逻辑移位

• 逻辑移位视数为无符号数
• 左移，低位补0
• 右移，高位补0
• 例
  • 十进制-4$[1111 1100]{补}$ 右移两位 $\rightarrow$ 高位补0$\rightarrow [0011 1111]{补}$,即十进制63，不是-4的$\frac{1}{4}$

循环移位

• 分类
  • 带进位标志CF的循环移位（大循环）
  • 不带进位标志位CF的循环移位（小循环）
• 主要特点
  • 移出的数位又被移入数据中，而是否带进位则要看是否将进位标志符加入循环位移
  • 循环移位适合将数据的低字节数据和高字节数据互换
• 流程
  • d中，数据位连同CF一起左移
  • 数据的最高位移入CF
  • CF则移入数据的最低位
  • 

浮点数

产生原因

• 二进制无法表示小数
• 浮点数表示法能以适当的形式将比例因子表示在数据中，让小数点位置根据需要而浮动
• 位数有限下，既扩大了数的表示范围，又保持的了数的有效精度

定义

• 浮点数是指用符号，尾数，基数和指数来表示的小数
• 浮点数有两种类型
  • 双精度浮点数double，64位
  • 单精度浮点数float，32位
• 基数
  • 二进制基数为2
  • 基数越大，表示范围越大，精度越低
• 符号
  • 指使用一个数据位来表示数值的符号，1为负，0为正
• 尾数
  • 尾数的位数反映浮点数的精度
  • 使用正则表达式，将表现形式多样的浮点数统一为一种表达式
  • 规则
    • 基数为2时，将小数点前面的值固定为1，基数为4时，尾数的最高两位不全为0
• 指数（阶码）部分
  • 阶码的位数反映浮点数的表示范围
• 

表示范围

• 【正上溢】：大于最大正数
• 【负上溢】：小于绝对值最大负数
• 【正下溢】：0到最小正数之间
• 【负下溢】：0到绝对值最小负数之间
• 通俗情况：上溢为大于最大数，下溢为小于最小数

浮点数举例

• 阶码，位数均用补码表示，求a，b的真值
  • a = 001;1.1001;
    • 001对应值为1，即阶码为1，尾数1.1001对应值$ - \frac{7}{16}, a = 2^1 \times (- \frac{7}{16}) = - \frac{7}{8}$
  • b = 001;0.01001
    • 001对应值为1，即阶码为1，尾数0.01001对应值+$\frac{9}{32},b = 2^1 \times (\frac{9}{32}) = \frac{9}{16}$

规格化浮点数

• 规格化：规定尾数的最高数位必须是一个有效值（1）
• 目的
  • 提高数据的表示精度
• 
• 左规
  • 当浮点数运算的结果为非规格化时要进行规格化处理
  • 将尾数算术左移一位，阶码减一
  • $b = 2^1 * (+0.01001) = 2^0 * (+0.10010)$
• 右规
  • 浮点数运算的结果尾数出现溢出（双符号位为01或10）
  • 尾数算术右移一位，阶码加1

浮点数加减运算过程

• 对阶
  • 目的：对齐两个操作数的小数点位置
  • 本质：把较小的阶码调整到较大的阶码
  • 阶码增大，尾数右移
  • 无阶码减小的情况
• 尾数求和
  • 对尾数进行加减法
• 规格化
  • 规格化浮点数
• 舍入
  • 浮点数概念，定点数无舍入
  • 舍入情况：对阶或右规格化
  • 舍入不一定产生误差（后几位为0时不产生误差）、
• 溢出判断
  • 双符号位为01或10时，溢出

C语言中的浮点数类型

• 以下转换范围和精度都是从小到大，转换过程无损失
  • $char \rightarrow int \rightarrow long \rightarrow double \rightarrow$
  • $float \rightarrow double$
• $int/float \rightarrow double$【能保留精确值】
• $int \rightarrow float$【不发生溢出，int值过大时可能发生舍入】
• $double \rightarrow float$【可能发生溢出和舍入】
• $float/double \rightarrow int$【可能发生溢出和舍入】

IEEE754标准浮点数范围

• IEEE754中尾数使用原码表示，阶码用移码表示
• 

浮点数与十进制间的计算

• 单精度中，最高位为符号位，接着的8位为阶码，偏置值为127，后23位为尾数值【隐藏了整数部分】
• 双精度中，最高位为符号位，接着的11位为阶码，偏置值为1023，后52位为尾数值

浮点数转十进制

十进制转浮点数

浮点数和定点数区别