《计组》第二章-数据的表示和运算

《计组》第二章-数据的表示和运算重点知识总结，包括数制与编码、运算方法和运算电路、浮点数的表示与运算三部分。

数据的表示和运算

• （1） 数制与编码
  • 进位计数制及其相互转换
    • 二进制(binary)→八进制(octonary)、十六进制(hexadecimal)
      • 
      • 以小数点为界，将二进制数分为3位（八进制）或4位（十六进制）一组，转化为对应的八进制（十六进制）数
    • 任意进制→十进制(decimalism)
      • 将任意进制数的各位数码与其权值相乘，相加即得对应的十进制数
        • 
    • 十进制→任意进制
      • 基数乘除法
        • 整数
          • 除基取余法：除基取余，最先取得的余数为数的最低位，最后取得的余数为最高位，商为0时结束
            • 
        • 小数
          • PS：在计算机中，小数和整数不一样，整数可以连续表示，但小数是离散的；所以并不是每个十进制小数都可以准确地用二进制表示。例如0.3，无论经过多少次乘二取整转换都无法得到精确的结果。但任意一个二进制小数都可以用十进制小数表示
          • 乘积取整法：乘积取整，最先取得的整数为数的最高位，最后取得的整数为数的最低位，乘积为1.0时结束
            • 
  • BCD码*
    • 定义：二进制编码的十进制数，通常采用4位二进制数来表示一位十进制数中的0~9这10个数码。这种编码方法使二进制数和十进制数之间的转换得以快速进行。但4位二进制数可以组合出16种代码，因此必有6种状态为冗余状态。
    • 分类
      • 8421码
        • 有权码，权值从高到低依次为8、4、2、1
        • 运算规则
          • 若两个8421码相加之和小于等于(1001)，即9，则不需要修正；若相加之和大于等于(1010)即10，则要加6修正（从1010 到1111这6个为无效码，当运算结果落于这个区间时，需要将运算结果加上6)，并向高位进位。
            • 
      • 余3码
        • 无权码，在8421码的基础上加（0011）形成，因此每个数都多余3
        • 例如：8→1011；9→1100
      • 2421码
        • 有权码，权值从高到低依次为2、4、2、1
        • 大于等于5的4位二进制数中最高位为1；小于5的最高位为0
  • 机器数
    • 定义
      • 机器数：二进制编码表示的数据
      • 真值：机器数对应的实际数据
    • 分类
      • 无符数（正整数）
        • 编码的全部二进制位均为数值位而没有符号位
        • 在字长相同的情况下，表示的最大数更大，一般在不出现负值运算的场合下使用，例如地址运算和表示指针
        • 字长为n位的无符号数的表示范围是0~(2^n-1)，例如机器字长16位，无符号数的表示范围为0~65535
      • 带符号数
        • 编码表示法
          • 原码、补码、反码和移码这4种编码表示的总结如下: ①原码、补码、反码的符号位相同，正数的机器码相同。 ②原码、反码的表示在数轴上对称，二者都存在+0和-0两个零。 ③补码、移码的表示在数轴上不对称，零的表示唯一，它们比原码、反码多表示一个数。 ④整数的补码、移码的符号位相反，数值位相同。 ⑤负数的反码、补码末位相差1。 ⑥原码很容易判断大小。而负数的反码、补码很难直接判断大小，可采用如下规则快速判断：对于负数，数值部分越大，绝对值越小，真值越大(更靠近0)。
          • 原码
            • 用机器数的最高位表示数的符号，其余各位表示真值的绝对值
            • 纯小数
              • 典例
            • 纯整数
              • • 真值零的原码表示有正零和负零两种形式，即[+0]=00000,[-0]=10000
              • 典例
            • 表示范围：字长为n+1，
            • 优点：与真值的对应关系和转换简单直观，便于实现乘除运算
            • 缺点：0的表示不唯一，加减运算较复杂
              • 原码加减运算规则比较复杂，对于两个不同符号数的加法（或同符号数的减法)，先要比较两个数的绝对值大小，然后用绝对值大的数减去绝对值小的数，最后还要给结果选择合适的符号。而补码表示法中的加减运算则统一采用加法操作实现。
          • 补码
            • 基于模的概念
            • 纯小数
              • 典例
            • 纯整数
              • • 零的补码表示唯一
            • 表示范围：字长为n+1，
            • 正数补码与原码相同；对于负数，符号位取1，其余各位取反，末位加1
            • 优点
              • ①与原码和反码相比，0的补码表示唯一
              • ②与原码和移码相比，补码加减运算规则比较简单，且符号位可以和数值位一起参加运算
              • ③与原码和反码相比，补码比原码和反码多表示一个最小负数。
              • 计算机中的带符号整数都用补码表示，故n位带符号整数的表示范是-2^(n-1)~2^(n-1)-1。
          • 变形补码（模4补码）
            • 双符号位的补码小数，符号位00表示正，11表示负，用在完成算术运算的ALU部件中
            • 变形补码用于检测加减运算中的溢出问题
              • 01表示正溢出
              • 10表示负溢出
            • 变形补码在存储时只需存储一位符号位（因为两个符号位正常情况下相等），但送入ALU运算时需送入两位符号位
          • 反码
            • 正数反码同原码
            • 负数反码等于真值“各位取反”，符号位取1，即补码表示的末尾减1
            • 缺点：0的表示不唯一，表示范围比补码少一个最小负数；运算较复杂，使用较少
          • 移码
            • 只能表示整数，常用来表示浮点数的阶码
            • 定义
              • 在真值X上加上一个常数（偏置值，通常为2^n）
            • 特点
              • 1||| 移码中零的表示唯一，[+0]=2"+0=[-0] =2"-0= 100...0 (n个“0”)
              • 2||| 一个真值的移码和补码仅差一个符号位，[x]补的符号位取反即得[x]移 (“1” 表示正，“0”表示负，这与其他机器数的符号位取值正好相反)，反之亦然
              • 3||| 移码全0时，对应真值的最小值-2"；移码全1时，对应真值的最大值2"-1
              • 4||| 移码保持了数据原有的大小顺序，移码大真值就大，移码小真值就小
        • 数的定点表示和浮点表示
          • 定点数的编码表示
            • 计算机中常用的数据表示格式有两种，一是定点格式，二是浮点格式。所谓定点数和浮点数，是指在计算机中一个数的小数点的位置是固定的还是浮动的：如果一个数中小数点的位置是固定的，则为定点数；如果一个数中小数点的位置是浮动的，则为浮点数。一般来说，定点格式可表示的数值的范围有限，但要求的处理硬件比较简单。而浮点格式可表示的数值的范围很大，但要求的处理硬件比较复杂。 在现代计算机中，通常用定点补码整数表示整数，用定点原码小数表示浮点数的尾数部分，用移码表示浮点数的阶码部分
            • 机器数的定点表示
              • 定点小数
                • 定点小数是纯小数，约定小数点位置在符号位之后、有效数值部分最高位之前。若数据X的形式为X=x0x1x2...xn(其中x0为符号位，x1~xn是数值的有效部分，也称尾数，x1为最高有效位)，则在计算机中的表示形式如图2.1所示。
              • 定点整数
                • 定点整数是纯整数，约定小数点位置在有效数值部分最低位之后。若数据X的形式为X=x0x1...xn（其中x0为符号位，x1~xn是尾数，xn为最低有效位)，则在计算机中的表示形式如图2.2所示。
          • 浮点数的编码表示（见下方）
• （2） 运算方法和运算电路
  • 基本运算部件
    • 运算器由算术逻辑单元（ALU，核心是加法器）、移动器、状态寄存器和通用寄存器等组成
    • 一位全加器
      • 最基本的加法单元
        • 输入
          • 加数Ai
          • 加数Bi
          • 低位传来的进位Ci-1
        • 输出
          • 本位和Si
          • 向高位的进位Ci
      • 和表达式：Si=Ai⊕Bi⊕Ci-1
        • ⊕为异或运算 Ai、Bi、Ci中有奇数个1时，Si取1
      • 进位表达式：Ci=AiBi+(Ai⊕Bi)Ci-1
    • 串行进位加法器（行波进位）
      • 把n个全加器相连得到n位加法器，每级进位直接依赖于前一级的进位
      • 串行进位加法器的运算时间主要由进位信号的传递时间决定，位数越多时间越长；全加器本身的求和延迟只是次要因素
    • 并行进位加法器
      • • 当Ai与Bi都为1时，Ci=1， 即有进位信号产生，所以称AiBi; 为进位产生函数(本地进位)，用Gi表示。
        • Ai⊕Bi=1且Ci-1=1时，Ci=1。可视为Ai⊕Bi=1, 第i-1位的进位信号Ci-1可以通过本位向高位传送。因此称Ai⊕Bi为进位传递函数(进位传递条件)，用Pi表示。
      • • Ci仅与Ai、Bi及最低进位C0有关，相互间的进位没有依赖关系，可并行运算
        • 实现该逻辑表达式的电路称为先行进位（CLA）部件；通过这种进位方式实现的加法器称为全先行进位加法器，是一种并行加法器
        • 加法器位数的增加会使得电路结构变得很复杂，因此，可以将16位加法器分为4组，组内组外都并行运算
    • 带标志加法器
      • 电路
      • 标识符
        • 零标志ZF
          • 零标志是根据每一位加法器的计算结果Fi相或得到的，所以只有在结果的每一位都为0的时候所有位相或才能得到0的输出，但是或门上有取反符号，所以在ZF标志的输出为1时代表结果全零，反之不全为0.
        • 溢出标志OF
          • 判断带符号数是否溢出，OF = Cn⊕Cn-1
        • 符号标志SF
          • 表示带符号整数加减运算结果的符号位，因此直接取结果的最高位作为SF，即SF =Fn-1
        • 进/借位标志CF
          • 判断无符号数的溢出，CF=Cout⊕Cin，即当Cin =0时，CF 为进位Cout，当Cin=1 时，CF为进位Cout 取反
    • 算术逻辑单元ALU
      • • ALUop是操作控制端，其位数决定了操作的种类（当位数为3时，ALU最多只有8种操作）
        • MUX是多路选择开关（多路选择器），从多个输入信号中选择一个送到输出端
  • 定点数的移位运算
    • 算数移位
      • PS：不论是正数还是负数，移位后其符号位均不变，且移位后都相当于对真值补0
      • • 负数的反码各位除符号位外与负数的原码正好相反，因此移位后所添的代码应与原码相反，即全部添1
        • 分析由原码得到补码的过程发现，当对其由低位向高位找到第一个“1”时，在此“1”左边的各位均与对应的反码相同，而在此“1”右边的各位(包括此“1”在内)均与对应的原码相同。因此负数的补码左移时，因空位出现在低位，则添补的代码与原码相同，即添0；右移时因空位出现在高位，则添补的代码应与反码相同，即添1.
      • 算数移位的对象是有符号数，移位过程中符号位保持不变
    • 逻辑移位
      • 被移位的数字是逻辑数，既无符号，也没有数值大小
        • 逻辑左移
          • 高位移丢，低位添0
        • 逻辑右移
          • 低位移丢，高位添0
      • 逻辑移位常用于对数据字的装配、拆卸中
    • 循环移位
      • 带进位标志位CF的循环移位（大循环）
      • 不带进位标志位的循环移位（小循环）
  • 定点数的加减运算
    • 补码的加减法运算
      • 
      • 公式
      • 特点
        • 符号位与数值位一起参与运算
        • 运算结果的高位丢弃，保留n+1位，结果仍为补码
      • 补码加减运算电路
        • • 已知一个数的补码表示为Y, 则这个数的负数的补码为-Y+1，因此，只要在原加法器的Y输入端加n个反向器以实现各位取反的功能，然后加一个2选1多路选择器，用一个控制端Sub来控制，以选择是将原码Y输入加法器还是将-Y输入加法器，并将控制端Sub同时作为低位进位送到加法器，如图2.10所示。该电路可实现补码加减运算。当控制端Sub为1时，做减法，实现X+（-Y）+1=[x]补+[-y]补；当控制端Sub为0时，做加法，实现X+ Y= [x]补+ [y]补
      • 溢出判别方法
        • 一位符号位法
          • • V=0表示无溢出
            • V=1表示有溢出
          • 若参加操作的两个数符号相同，结果又与原操作数符号不同，则表示结果溢出
        • 双符号位法（模4补码）
          • 运算结果的两个符号位相同，表示未溢出；不同表示溢出，此时最高位符号代表真正的符号
        • 采用一位符号位根据数据位的进位情况判断溢出
    • 原码加减法运算
      • 加法规则：先判符号位，若相同，则绝对值相加，结果符号位不变;若不同，则做减法，绝对值大的数减去绝对值小的数，结果符号位与绝对值大的数相同。
      • 减法规则：两个原码表示的数相减，首先将减数符号取反，然后将被减数与符号取反后的减数按原码加法进行运算。
  • 定点数的乘除运算
    • 乘法（累加-右移）
      • 原码一位乘法
        • 符号位
          • 两数符号位异或：
        • 数值位：绝对值相乘
          • 
        • 无符号数乘法运算电路
          • 
      • 补码一位乘法（Booth算法）
        • 
        • 补码乘法运算电路
          • 
    • 除法（累加-左移）
      • 原码除法运算（不恢复余数法/原码加减交替除法）
        • 符号位
          • 两束符号位异或
        • 数值位
          • 累加-左移
            • 
      • 补码除法运算（加减交替法）
        • 符号位与数值位一起参加运算，商符自然形成
          • 
        • 除法运算电路
          • 
  • C语言中的整数类型及类型转换
    • 
    • 自动类型转换
      • 转换按数据长度增加的方向进行，以保证数值不失真，或者精度不降低。例如，int 和 long 参与运算时，先把 int 类型的数据转成 long 类型后再进行运算。
      • 所有的浮点运算都是以双精度进行的，即使运算中只有 float 类型，也要先转换为 double 类型，才能进行运算。
      • char 和 short 参与运算时，必须先转换成 int 类型。
    • 强制类型转换
      • 有符号数和无符号数转换
        • 强制类型转换的结果保持位值不变，仅改变了解释这些位的方式
        • 例：unsigned short x =65535 → short y = -1
      • 不同字长整数之间的转换
        • 小字长变量→大字长变量
          • 原数字是无符号整数
            • 零填充
          • 原数字是有符号整数
            • 符号位填充
        • 大字长变量→小字长变量
          • 多余的高位部分截断，低位直接赋值
          • 例如：int x = 65536 → short y =0
  • 数据的存储和排列
    • 大小端存储
      • 
      • 大端方式：从最高有效字节到最低有效字节的顺序存储数据
      • 小端方式：从最低有效字节到最高有效字节的顺序存储数据
    • 边界对齐
      • 通过存储空间换取取指令和取数速度，例如精简指令系统计算机RISC
• （3） 浮点数的表示与运算
  • 浮点数的表示
    • 浮点数的表示格式
      • 浮点数表示法：以适当的形式将比例因子表示在数据中，让小数点的位置根据需要而浮动
      • • 
        • S：数符，0正1负，用来决定浮点数的符号
        • M：尾数，二进制定点小数，一般用定点原码小数表示
          • 尾数的位数反映浮点数的精度
        • E：阶码/指数，二进制定点整数，用移码表示
          • 阶码的值反映浮点数的小数点的实际位置
          • 阶码的位数反映浮点数的表示范围
        • R：基数，一般约定为2、4、16等
    • 浮点数的表示范围
      • 上溢（中断运算，进行溢出处理）
        • 正上溢
        • 负上溢
      • 下溢（当作机器零处理）
        • 正下溢
        • 负下溢
    • 浮点数的规格化
      • 
      • 定义：通过调整一个非规格化浮点数的尾数和阶码的大小，使非零的浮点数在尾数的最高数位上保证是一个有效值
      • 左规
        • 当运算结果的尾数的最高数位不是有效位时，进行左移
        • 每左移一位，阶码减1（假定基数为2）
      • 右规
        • 当运算结果的尾数的有效位进到小数点前面时，进行右移
        • 每右移一位，阶码加1（假定基数为2）
    • IEEE 754标准
      • 浮点数格式
        • • 对于规格化的二进制浮点数，数值的最高位总是“1”,为了能使尾数多表示一位有效位，将这个“1”隐藏，称为隐藏位，因此23位尾数实际上表示了24位有效数字。 PS：短浮点数与长浮点数都采用隐藏尾数最高数位的方法，因此可多表示一位尾数. 对于短浮点数，偏置值为127; 对于长浮点数，偏置值为1023。 存储浮点数阶码之前，偏置值要先加到阶码真值上。例如，阶码值为3，因此在短浮点数中，移码表示的阶码为127 + 3 =130 (82H)；在长浮点数中，阶码为1023+ 3=1026 (402H)。
      • 浮点数范围
      • 全0/1阶码
        • • 全0阶码全0尾数
            • +0/-0。零的符号取决于数符S
          • 全1阶码全0尾数：
            • +∞/-∞
    • 定点、浮点表示的区别
      • （1） 数值的表示范围
        • 若定点数和浮点数的字长相同，则浮点表示法所能表示的数值范围远大于定点表示法
      • （2） 精度
        • 对于字长相同的定点数和浮点数来说，浮点数虽然扩大了数的表示范围，但精度降低了
      • （3） 数的运算
        • 浮点数包括阶码和尾数两部分，运算时不仅要做尾数的运算,还要做阶码的运算，而且运算结果要求规格化，所以浮点运算比定点运算复杂
      • （4） 溢出问题
        • 在定点运算中，当运算结果超出数的表示范围时，发生溢出；浮点运算中，运算结果超出尾数表示范围不一定溢出，只有规格化后阶码超出范围，才发生溢出
  • 浮点数的加减运算
    • 
    • 阶码运算和尾数运算分开进行
    • 过程
      • 对阶
        • 使两个数的阶码相等（小数点对齐）
        • 遵循小阶向大阶看齐的原则，将阶码小的尾数右移至阶码相等为止
      • 尾数求和
      • 规格化
      • 舍入
        • 在对阶和尾数右规时，可能会对尾数进行右移，为保证运算精度，一般将低位移出的两位保留下来，参加中间过程的运算，最后将运算结果进行舍入，还原表示成IEEE 754格式。
        • 舍入方法
          • 0舍1入法
            • 运算结果保留位的最高数位为0，则舍去；否则在尾数的末位加1
          • 恒置1法
            • 只要因移位而丢失的位中有1，就把尾数末位置1
          • 截断法
        • 若因尾数舍入而发生了指数溢出，需对尾数再做右规处理
      • 溢出判断
        • 注意:某些题目可能会指定尾数或阶码采用补码表示。通常采用双符号位，当尾数求和结果溢出(如尾数为10.x...x或 01.x...x) 时，需右规一次；当结果出现00.0xx...x或11.1x...x时，需要左规，直到尾数变为00.1..x或11.0x...x.
        • 在尾数规格化和舍入时，可能会对阶码执行加/减运算，进而导致指数溢出的问题
        • 若正值数超过了最大允许值，则发生指数上溢，产生异常
        • 若负值数超过了最小允许值，则发生指数下溢，将结果按机器零处理