计算机组成原理: 算术运算

Posted on Edited on In , Word count in article: 4k Reading time ≈ 15 mins.

计算机的算术运算

数据的表示与存储

计算机码

  • 真值：符合人类习惯的十进制数字；机器数：数字化后的以机器码存储的数字；常用$8421\ \rm BCD$有权码
  • 其它编码：
    • 余三码：在8421基础上，添加011的偏置量，是无权码
    • 2421：权值不同的有权码
    • ASCII：编码英文字符
  • IEEE标准规定计算机内的有符号定点数都以补码形式存储，且使用$8421\ \rm BCD$码

定点数表示

  • 仅有符号定点数有原、反、补码的定义

  • 有符号定点数视最高位为符号位，假设 − 2n ≤ x < 2n(n ≥ 0，即只表示纯整数或纯小数)：

    • 正数的原码、反码、补码相同：

    • 原码：由符号位和尾数组成，对人来说是最直观的机器数

      • 不需要记住原码的计算公式，只需记住原码无法表示最小值 − 2n(0有两个原码)
      • 数值部分位数恰好为n

    • 反码：对原码的尾数按位取反后的码值(仍无法表示最小值)

    • 补码的定义：

      • 计算公式(负数)：[x]补 = 2n + 1 + x，当要通过补码计算原值时，n恰为数值部分位数

      • 简单理解：可看作相同位数无符号定点数中最高位的权值改为 − 2n，使相同位数无符号定点数表示范围0 ≤ x < 2n + 1中 ≥ 2n的部分能一一映射到负数集合里(最高位权值由2n变为 − 2n，即这部分定点数均减去2n + 1来对应负数)

        不难理解为何正数的补码为其本身，实际上真正的计算公式中加上2n + 1后需要模2n + 1，这个公式是正负数补码通用的，化简模运算后得到正负数补码不同的计算方式

        由于一个数加一个负数x等价于加其补码后模2n + 1，故设计运算时只需自然舍去最高位进位即可统一加减法

        • 证明：A + x = (A+2n + 1+x) mod  2n + 1 = (A+[x]补)取n + 1位

      • 当补码符号位为1，数值部分全为0时，达到能表示的最小值 − 2n，此时原码不存在

    • 补码的快捷计算(原码存在时)：反码加1，最高位自然舍去

  • 移码：定义为在补码的基础上，符号位翻转一次；其意义为偏移了2n，使比较正负数补码的大小时符合直观判断；可在浮点数中判机器零

浮点数表示

  • 可将任意分子为纯整数、分母为2的次幂的有理数$\begin{align}\frac{x}{2^y}\end{align}$表示小数为2−y × (x)2；称 − y为阶码(含阶符)、纯整数x为尾数(含数符)，就是一般的浮点数表示形式
  • 规格化： 使整数x变为纯小数，且使其大于2−k(按2k规格化)，尾数左移阶码减一，反之加一
  • 机器零：当阶码小于等于其能表示的最小值、或尾数为零时，将该数当作零(而实际不是)

浮点数IEEE标准

  • IEEE浮点数：阶码、尾数均为补码，数符在最前，阶码添加偏移量，规格化使尾数为1 ∼ 2间的小数且整数部分省略(隐藏位)，如下：

    数符  阶码(含阶符)  尾数(省略最高位的1)

  • 有如下类型及其对应位数，其中临时实数不使用隐藏位：

    $\begin{matrix}&数符&阶码&尾数&总位数&阶码偏移量\\短实数&1&8&23&32&\rm 7FH\\长实数&1&11&52&64&\rm 3FFH\\临时实数&1&15&64&80&\rm 3FFFH\end{matrix}$

校验码

  • 奇偶校验码：给有效信息额外添加1位校验码，使整体1的个数为奇数(奇校验)或偶数(偶校验)
    • 求偶校验位值的过程就是让所有有效信息位进行异或
    • 偶校验信息的过程就是让整条信息的各位异或，此时正确信息中各位的异或结果为0
    • 检错能力为1位，没有纠错能力
  • 海明校验码：检错能力为2位，纠错能力为1位
    • 使用多个校验位，并采用偶校验，每个校验位被分配到不同组，分组进行偶校验，按顺序排列为整数k，则$\begin{cases}k=0&无错\\k\ne0&出错,且该值指明了出错的位置序号\end{cases}$
    • 各校验位的位置为Pi = 2i − 1处，信息位Di按顺序排放在其余位置，位置序号为p
    • 分组：将所有p用二进制数表示，则校验位Pi将和所有第i位为1的p所指向的信息位分为一组，例如P1将和p = 3(011)、5(101)、7(111)⋯上的信息位分为一组
    • 检错：再添加一位全校验位，对整体进行偶校验，可判断1位错或2位错：$全校验位=\begin{cases}\times&其它校验位全为0时,无错\\1&1位出错\\0&2位出错\end{cases}$
    • 纠错：若2位出错，需重传；若1位出错，则对第k位取反即可

定点数运算

移位

最快的运算

  • 针对无符号定点数，采用逻辑移位，即在缺失位处补0，所有位均参与移位

  • 针对有符号补码，采用算术移位：符号位不参与移位，在缺失位处补原符号位

  • 乘以2n幂：C++编译器将采用左移运算符而不是乘号

  • 除以2n幂：C++编译器将采用右移运算符而不是除号

    • 对无符号整数，均直接逻辑右移，结果均为向下舍入(即向更小的数字舍入)

      • 向下舍入原因：二进制串的最低位会被覆盖，右移时最低位的产生的正小数部分丢失

    • 对有符号负数，需要进行偏置：

      • 向下舍入的特性会导致负数舍入后离0更远，而我们希望除法后的舍入应该离0更近，例如 − 3/2 =  − 1而不是 − 2，这种舍入是不合适的

      • 最简单的想法是先转化为正数，再右移，再转化为负数：⌈x/2k⌉ =  − ((−x)>>k)

      • 通过偏置进行向上舍入是最常用的办法，即在右移之前加上偏置量(1<<k) − 1

        偏置量证明：假设需要右移k位，那么容易得到$\begin{cases}前k位为0,&不需要舍入\\前k位大于0,&需要舍入\end{cases}$

        若增加该偏置量，在不需要舍入的情况下，不改变结果

        在需要舍入的情况下，添加后将进位，使结果加1，即⌈x/2k⌉ = ⌊x/2k⌋ + 1

    • 由于向下舍入是更简单的方式，一些语言不采用向零舍入

按位运算和逻辑运算及加减法

按位与运算可用于截取前k位二进制串

加减法稍慢，减法需要先将后者的补码算术取反

  • 采用高速并行加法器，也称超前进位加法器(CLA)：

    • 回顾一位加法器的最少逻辑门实现：$\begin{matrix}{\rm S_i}=A\oplus B\oplus C_{i-1}\\{\rm C_i}=(A\oplus B)C_{i-1}+AB\end{matrix}$，即最低位的进位有5T的时延

    • 串行加法器：由于来自低位的进位参与高位进位的计算时不用通过异或门，故每个高位进位又有2T的时延，综合下来一个串行加法器的时延与位数n线性正相关

    • CLA的思路就是，首先一次性、同时计算出各位的进位，由于${\rm C_i}=AB+(A+B)C_{i-1}$，将Ci − 1展开即可得到$\begin{cases}G_i=A_iB_i\\P_i=A_i+B_i\\\rm {C_i}=G_i+P_iG_{i-1}+P_iP_{i-1}G_{i-1}+\cdots+(P_iP_{i-1}···P_1G_0)+(P_iP_{i-1}···P_0C_0)\end{cases}$

      所有进位的时延都为$3T$

    • CLA的问题在于，位数越高所需逻辑电路越复杂，因此通常采用8位CLA串行连接产生非完全超前进位的更高位加法器

  • 有符号整数的算术取反(取相反数)为整体按位取反后末位加1：

    • $\begin{align}&设有n+1位以补码存储的二进制有符号正数\\&证明正\rightarrow负:最高位表示0,其余位最多表示2^n-1,当前数值为A\\&整体取反后,最高位表示-2^n,其余位变为2^n-1-A,加一后等于2^{n-1}-A\\&易得0+A=-(-2^n+2^n-A)\\&反之同理\end{align}$

  • 加减法溢出位判断：当且仅当两操作数符号相同时可能溢出

    • 一位判断：结果符号位和原符号位不同时溢出

    • 二位判断：结果的两个符号位不同时溢出

    • 证明两个负数补码的数值部分相加后，若不溢出，最高位一定有进位：

      $\begin{align}&证:设两负数原值为x、y,[x]_{补}=1,X、[y]_{补}=1,Y;其中X、Y都为n位\\&由[x]_{补}=x+2^{n+1}、[y]_{补}=y+2^{n+1}\\&若x+y不溢出,即x+y\ge-2^n\\&\Rightarrow[x]_{补}+[y]_{补}-2^{n+2}\ge-2^n\\&\Rightarrow[x]_{补}+[y]_{补}=X+Y+2^{n+1}\ge3·2^n\\&\Rightarrow X+Y\ge2^n\Rightarrow X+Y最高位一定有进位\end{align}$

乘法

比加法更慢

  • 原码一位乘：因计算机是定长机，因此将笔算乘法中被乘数左移转换成部分积右移，并使其高位和被乘数相加(因乘数最低位可舍去，因此同时右移即可)；假设两个数值为n位的数相乘：

    • 符号位单独处理得到，乘法过程为绝对值相乘
    • 注意使用逻辑右移，因为最高位本质上是数值位，总共需要移n位
    • 部分积寄存器n + 1位，多出的一位存假溢出

  • 原码两位乘：将两次一位乘化为一次两位乘，其有五种情况

    • 00：直接右移两位

      01：加一次被乘数后右移两位

      10：加两倍的被乘数(左移一次)后右移两位

      11：因很难计算三倍，故先减一倍被乘数后记账一次(在右移两位后高位加一倍等价于移位前加四倍)

      ​ 借位初始为0，每次都需要参与运算

      100：因有借位的参与，此时直接加四倍的被乘数(左移两次)后右移两位

    • 因涉及到减法，故需要真符号位，又被乘数最多可能左移两位，因此需要在被乘数前补三位

      并采用算术右移

    • 因涉及到借位，为防止最后借位仍为1，需在乘数前补位(偶补两位、奇补一位，由于是绝对值，补的是0，因此奇数位只需补1位而最后不会出现11 1的情况)，用于处理该借位

    • 总共需要右移$\begin{align}\left\lfloor\frac{乘数}2\right\rfloor\end{align}$次两位，若乘数位数为奇数最终需再移一位

  • 补码一位乘(校正法)：被乘数符号任意、乘数取绝对值后，进行原码一位乘的过程，最后进行校正

    • 由于是补码，采用算术右移，且部分积寄存器需补一位真符号位

    • 若乘数本身为负数，需在移位完成后减去一倍的乘数，减后不需要移位

  • 补码一位乘(比较法/Booth算法)：在对校正法公式整理后，依据最后两位(需补附加位)有四种情况(后一位减前一位有三种情况)：

    • 00/11：直接右移一位

      01：加一倍乘数后右移一位

      10：减一倍乘数后右移一位

    • 乘数寄存器需补附加位(初始为零)

    • 注意最后一次比较后不移位，总共只移n位

  • 补码两位乘：将两次Booth乘法步骤合为一次，有八种情况：

    • 000：直接算术右移两位

      001：加一倍乘数后右移两位

      010：减一倍右移再加一倍右移，整理得加一倍后右移两位

      011：加两倍后右移两位

      100：减两倍后右移两位

      101：加一倍右移再减一倍右移，整理得减一倍后右移两位

      110：减一倍后右移两位

      111：直接右移两位

    • 因此部分积需补三位、乘数需补一位附加位

    • 此外，乘数算上附加位需补成奇数位，且最后一次比较后不移位

  • 快速幂算法：

    • N = (an,an − 1,⋯,a0)2，计算ban2n · ... · ba0 · 1即可

    • 或者，当N为偶数时使其自乘，为奇数时记录多余的b，在最后相乘：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      int quick_power(int b, int N) {
          int ans = b, tmp = 1;
          while (N) {
              if (N & 1) { // 奇数时抽出一份 b, 记录在 tmp 中.
         tmp *= b;
                  --N;  // 幂数减1.
              }
              else {   // 偶数时自乘, 幂数减半.
                  ans *= ans;
                  N >>= 1;
              }
          }
          return ans * tmp;
      }

除法和取模

极慢，取模和除法是同时进行，同时完成的

  • 恢复余数法：因定长机，将笔算过程中除数右移改为使余数和商左移，根据余数和除数的大小来上商

    • 预处理：被除数和除数先转换成其绝对值，计算结果的符号位需单独处理
    • 若减除数后，新余数为负数，则要恢复余数，即加上除数，并在商的末位商0
    • 否则直接在商的末位商1
    • 两种情况均需使余数和商同时逻辑左移

  • 原码的加减交替法(不恢复余数法)：

    • 每次减除数后，根据余数：$\begin{cases}正数商1左移减\\负数商0左移加\end{cases}$

    • 共移n次，最后一次移位后仍需继续运算一次

  • 补码的加减交替法：

    • 取两位符号位，每次运算前比较余数和除数的符号位：$\begin{cases}同号商1减除数\\异号商0加除数\end{cases}$

    • 共移n次，最后一次移位后恒商1，因此会导致些许误差

  • 快速模幂算法：为了减小因幂运算导致的数字极大，产生额外空间、时间消耗，故通过以下定理将其变为模数相乘再取模，数字会小很多

    • 前置定理：$(a_1·a_2){\rm mod}\ n=((a_1{\rm mod}\ n)·(a_2{\rm mod}\ n)){\rm mod}\ n$

    • 推论：$a^N{\rm mod}\ n=(a{\rm\ mod}\ n)^N{\rm mod}\ n$

    • 假设计算$b^N{\rm mod}\ n$，为快速计算幂，这里复用快速幂算法，将N化为二进制(an,an − 1,⋯,a0)2，按权值展开后，bN = ban2n + ⋯ + a0 · 1 = ban2n · ... · ba0 · 1

    • b2n虽然比bN小，但还是较大，因此要证明每次迭代时，取模不影响结果，递归套用推论易证：$b^{2^n}{\rm mod}\ n=(b^{2^{n-1}}·b^{2^{n-1}}){\rm mod}\ n=(b^{2^{n-1}}{\rm mod}\ n)^2{\rm mod}\ n$

      所以计算n次幂的模时，可计算n − 1次幂的模的平方的模

    • ```c++ int quick_power_mod(int b_mod_n, int N, int n) { int ans = 1; b_mod_n %= n; // 预处理, (b^N)%n = ((b%n)^N)%n. while (N) { // 取N的二进制表示中的第一位,如果为1,则计算 (ans(b^{权值}%n)) mod n. if (N & 1) { // 为保证数字始终较小,迭代 ans 时要再mod n. ans = (ans b_mod_n) % n; } // 为保证数字始终较小,迭代 b的幂 时要再mod n, 使数字<n^2. b_mod_n = (b_mod_n * b_mod_n) % n; N >>= 1; } return ans; } 

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10

      - 模数为$2$的$n$次幂($n>1$)：直接用位运算**截取前$n-1$位**即可

        - ```c++
          int mod_2_power(int b, int n) {
              // 若n为2^k,则二进制表示为00...010...00, 唯一的1在第k+1位上.
              // 则n-1为00...01...11, 最高位的1在第k位上.
              // 故 b % n = b & (n-1);
              return b & (n - 1);
          }

定点数运算总结

浮点数运算

ALU设计