计算机的算术运算

数据的表示与存储

计算机码

• 真值：符合人类习惯的十进制数字；机器数：数字化后的以机器码存储的数字；常用$8421\ \rm BCD$有权码

• 其它编码：

  • 余三码：在$8421$基础上，添加$011$的偏置量，是无权码
  • $2421$：权值不同的有权码
  • ASCII：编码英文字符

• IEEE标准规定计算机内的有符号定点数都以补码形式存储，且使用$8421\ \rm BCD$码

定点数表示

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

• 有符号定点数视最高位为符号位，假设$-2^n\le x\lt 2^n$($n\ge 0$，即只表示纯整数或纯小数)：

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

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

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

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

  • 补码的定义：

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

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

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

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

      • 证明：$A+x=(A+2^{n+1}+x)\mod 2^{n+1}=(A+[x]_{补})_{取n+1位}$

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

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

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

浮点数表示

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

浮点数IEEE标准

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

  $数符\ \ 阶码(含阶符)\ \ 尾数(省略最高位的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}$
  • 各校验位的位置为$P_i=2^{i-1}$处，信息位$D_i$按顺序排放在其余位置，位置序号为$p$
  • 分组：将所有$p$用二进制数表示，则校验位$P_i$将和所有第$i$位为$1$的$p$所指向的信息位分为一组，例如$P_1$将和$p=3(011)、5(101)、7(111)\cdots$上的信息位分为一组
  • 检错：再添加一位全校验位，对整体进行偶校验，可判断$1$位错或$2$位错：$全校验位=\begin{cases}\times&其它校验位全为0时,无错\\1&1位出错\\0&2位出错\end{cases}$
  • 纠错：若$2$位出错，需重传；若$1$位出错，则对第$k$位取反即可

定点数运算

移位

最快的运算

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

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

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

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

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

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

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

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

    • 最简单的想法是先转化为正数，再右移，再转化为负数：$\lceil x/2^k\rceil=-((-x)>>k)$

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

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

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

      在需要舍入的情况下，添加后将进位，使结果加$1$，即$\lceil x/2^k\rceil=\lfloor x/2^k\rfloor+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}$，将$C_{i-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=(a_n,a_{n-1},\cdots,a_0)_2$，计算$b^{a_n2^n}·...·b^{a_0·1}$即可

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

    c++

    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$化为二进制$(a_n,a_{n-1},\cdots,a_0)_2$，按权值展开后，$b^N=b^{a_n2^n+\cdots+a_0·1}=b^{a_n2^n}·...·b^{a_0·1}$

  • $b^{2^n}$虽然比$b^N$小，但还是较大，因此要证明每次迭代时，取模不影响结果，递归套用推论易证：$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;
    }

• 模数为$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设计