加法器

如何用门电路实现一位加法

举个例子，比如我们来计算如下二进制：
示意图
比如我们来进行这两个二进制的加法，通过竖式我们会发现

  • 我们每一位的加法其实都是加上上一位的进位$C_{i－1}$，$A_i$，$B_i$。
  • 而我们产生的结果就是这一位的和$S_i$和下一位的进位$C_i$
    我们将1bit的加法器的逻辑写出来后，就如图所示。
    示意图
    同样的我们可以把它的电路图给画出来：
    示意图
    如果我们将其封装一下，就是我们的一位全加器：
    示意图

n位bit全加器

我们只需要将n个1位加法器串联起来就可以得到一个n位全加器。
示意图

不足之处

进位信息是串行产生的，计算速度取决于进位产生和传递的速度。位数越多，运算速度越慢。

  • 电信号达到稳态需要一定时间，因此进位产生速度会有延迟。
  • 串行进位又称为行波进位，就像水波一样往下传递，每一级进位直接依赖于前一级的进位，即进位信号是逐级形成的。
    由于两个输入端允许并行输入 n bit，因此这种加法器属于：并行加法器

    由于进位信息是串行产生的，因此从“进位方式”看，这种加法器属于：串行进位加法器

    综上，很多教材把这种加法器称为 ”串行进位的并行加法器“
  • “并行” 指的是：每一位的 $A_i$、$B_i$ 同时输入，有 n 个全加器在同时工作。
  • “串行” 指的是：进位信号必须一位一位依次传递，这是速度慢的根源。

带标识位的加法器

我们在运用加法器进行运算的时候，通常要考虑溢出、为0、结果正负，所以我们这里有一些标识符可以使用：

  • OF(Overflow Flag)溢出标志：用于判断带符号数加减运算是否溢出。OF＝1溢出；OF=0未溢出
  • SF(Sign Flag)符号标志：用于判断带符号数加减运算结果的正负性。SF＝1结果为负；SF=0结果为正
  • ZF(Zero Flag)零标志：用于判断加减运算结果是否为0。ZF=1表示结果为0；ZF=0表示结果不为零
  • CF(Carry Flag)进位/借位标志：用于判断无符号数加减运算是否溢出。CF=1溢出；CF=0未溢出

算术逻辑单元(ALU)

算术逻辑单元（ALU）的作用

示意图

  • 运算器负责对数据进行处理，如：加减乘除等。
  • ALU是一种组合逻辑电路，实现了加/减/乘/除/与/或/非等功能。因此ALU是运算器的核心。
  • 由于加减乘除等运算都要基于“加法”来实现，因此加法器是ALU的核心。
  • ALU是运算器的核心

ALU的功能

  • 算术运算：加减乘除等
  • 逻辑运算：与或非、异或、移位等
  • 其他：求补码（计算B的补码）、直送（不进行计算直接通过，但是还是有控制信号）等
    示意图
    当我们要进行加法等其他方法时，控制器会传输一个指令信号为m来ALU中。

    考试重点：
  • 如果ALU支持k种功能，则控制信号位数$m>=[log_2k]$=

ALU的实现原理（简单了解即可）

示意图
这张图里的核心逻辑就是：

  • 所有功能电路（加法、乘法、与运算、移位等）都会同时对输入 A、B 进行运算，各自产生结果。
  • 多路选择器（MUX）会根据 m 位控制信号，从这些结果里选出一个，作为最终输出 F。

看懂ALU图示

示意图

  • 如果ALU支持k种功能，则控制信号位数$m>=[log_2k]$=
  • ALU的运算数、运算结果位数与计算机的机器字长相同
  • ZF/OF/SF/CF标志位用于表示本次运算结果的特征
  • 这些标志信息通常会被送入PSW程序状态字寄存器
  • 有的计算机系统把PSW寄存器称为“标志寄存器FR (Flag Register)
  • Cin是进位输入信号、Cout是进位输出信号

定点数的移位运算

十进制的移位运算

其实就是科学计数法，如图：
示意图
移位运算：通过改变各个数码位和小数点的相对位置，从而改变各数码位的位权应用：可以通过移位运算快速实现特殊数值的乘法、除法。

逻辑移位（常用于处理无符号整数）

逻辑左移：高位移出丢弃，低位补零

给大家展示一下左移奥，献丑了：
示意图
逻辑左移一位：
示意图
逻辑左移两位：
示意图
逻辑左移三位：
示意图
逻辑左移四位：
示意图我们可以看出，对于无符号整数，每逻辑左移一位，则相当于乘2。若逻辑左移丢弃的位=1，则发生溢出（超出 n bit 无符号整数的表示范围）

逻辑右移：低位移出丢弃，高位补0

接下来给大家看看右移这么个事儿奥！

右移一位：
示意图
右移两位：
示意图
右移三位：
示意图
我们可以看出，对于无符号整数，每逻辑右移一位，相当于÷2。若逻辑右移丢弃的位=1，则会丢失精度。(小数失去)

算数位移（常用于处理带符号整数）

在计算机内部，带符号整数都是由补码表示的。

算术左移：高位移除丢弃，低位补零
示意图
我们现在来进行下算数左移一位：
示意图
左移两位：
示意图
左移三位：
示意图
对于带符号整数，每算数左移一位，则相当于乘2。若算数左移前后的符号为不同，则发生溢出（超出 n bit 带符号整数的表示范围）

xdm到算术右移了，这个就有点神奇了，简直就是马猴🦄⭐。具体原理我现在也想不通，凑合着看看吧。
负数👇
示意图
正数👇
示意图

补充

逻辑位移常用于处理无符号整数，算术位移常用于处理带符号整数，是”常用于“而不是”只能用于“。对于计算机硬件来讲，只要给出二进制串，无论是什么数值类型，都可以通过指令进行逻辑移位、算数移位。

定点数的加减运算

原码的加减运算

原码的加法运算：

  • 正+正：绝对值做加法，结果为正
  • 负+负：绝对值做加法，结果为负
  • 正+负：绝对值大的减绝对值小的，符号同绝对值大的数
  • 负+正：绝对值大的减绝对值小的，符号同绝对值大的数
    加法器直接怼原码进行加法操作，可能会出错

补码的加减运算

示意图
负数的补码转原码：

  • 数值位取反+1
  • 负数补码中，最右边的1及其右边同原码。最右边的1的左边同反码
    对于补码来说，无论加法还是减法，最后都会转变成加法，由加法器实现运算，符号位也参与运算。

溢出判断

如图所示，我们这俩个式子是会溢出的。
示意图
我们可以这样来看补码，就是把补码给重排列成我们熟悉的数值排布方式：
示意图

  • 只有”正数＋正数“才会上溢———正+正＝负
  • 只有”负数＋负数“才会下溢———负＋负＝正
    方法一：采用一位符号位，设A的符号为$A_S$，B的符号为$B_S$，运算结果的符号为$S_S$，则溢出逻辑表达式为：

    $$V = A_SB_S\overline{S_S}+\overline{A_S}\overline{B_S}S_S $$

  • 若V=0，表示无溢出
  • 若V=1，表示有溢出
    方法二：采用一位符号位，根据数据位进位情况判断溢出
    示意图
    示意图
    方法三：采用双符号位
    示意图
    正数符号为00，负数符号位11

    $$[A+C]_补=00,0001111+00,1111100=01,0001011{}{}上溢 $$

    $$[B-C]_补=11,1101000+11,0000100=10,1101100下溢 $$

    记两个符号位为$S_{S1}S_{S2}$，则$V=S_{S1}\oplus S_{S2}$。若V=0，表示无溢出；若V=1，表示有溢出。

无符号数的加减运算

无符号数的加减法其实和补码差不多，唯一需要知道的就是要明白 二进制溢出本质上是一个周期。

无符号数加法/减法的溢出判断

  • 手算判断溢出的方法：n bit 无符号整数表示范围$0到2^n-1$，超出此范围溢出。
  • 计算机判断溢出的方法：
    • 无符号数加法的溢出判断：最高位产生的进位=1时，发生溢出，否则未溢出
    • 无符号数减法的一处判断：减法变加法，最高位产生的进位=0时，发生溢出，否则未溢出。

补码加减运算电路

示意图
如果是减法，那么Sub将会变为1。此时多路选择器将会把加数整体取反，并且控制Cin位1。开局也就变成了Y+0 000 0001，也就是变相末位加1了。无符号这个也适用。

无符号整数的乘法运算原理

十进制的手算

示意图

二进制的手算

示意图
通过上下这样，我们可以得出一个结论：无符号整数的手算方法与十进制类似（逐位相乘，错位相加）。但是我们如何用计算机来实现呢？我们人类计算可以直接把一整行进行相加，但是计算器的加法器只能一次加两个数。

无符号整数乘法

示意图
开始：

  1. 将被乘数、乘数分别放入寄存器X、Y
  2. 乘积寄存器P设置为0
  3. 计数器$C_n$的初始值设置为n（n为乘数的位数）
  4. 还有就是，上面是被乘数，下面是乘数∇
    特殊情况：但是在开始时，我们的计数器会先去检测有没有全零的情况。乘数和被乘数只要有一个全零，不需要进行后续的运算。

我么将重复n轮、移位运算，直到计数器$C_n =0$：

  1. 将乘数寄存器Y的最低位，送入”控制逻辑“进行判断
  3. 若Y的最低位为1，则执行加法，运算结果写回P，加法产生的进位需要保存进进位触发器C
  4. 若Y的最低位为0，则什么也不做。
  5. 将【C、P、Y】视为整体，逻辑右移一位
  6. 计数器$C_n$减一
    当然我们还是把示意图放上去过一遍。

示意图
示意图
示意图
示意图
结束：

  1. 乘法运算的结果用2n位暂存（寄存器P，寄存器Y），n位数乘n位数肯定不会大于2n位的。
  2. 在很多计算机架构中，通常仅保留低n位作为成乘积结果（因此，运算结果可能会发生溢出）
    示意图

无符号整数乘法的溢出判断、溢出处理

我们来看看两种情况，根据上面结束②：
示意图
溢出的判断：其实溢出判断比你想象的要简单，就是看更高的那n位是否为0，不为0那就是没溢出，为0就是溢出。此时可将OF标志位（溢出标志位）变为1

溢出的处理：

  1. 程序员可以选择忽略溢出，只不过会导致结果错误罢了
  2. 如果想要处理溢出这种异常，可以在乘法指令之后执行一条溢出自陷指令。该指令会检查OF标志位，若OF==1，就执行操作系统的”异常处理程序“

带符号整数（补码）的乘法运算原理

无符号整数乘法整数 VS 带符号整数乘法电路

示意图
发现区别了吗？区别其实是这样的：
示意图
我们以4bit带符号整数为例，我会将要用到的东西放在下图中：
示意图
开始：

  1. 将被乘数、乘数分别放入寄存器X、Y
  2. 乘积寄存器P变为0，”辅助位“变为0
  3. 计数器$C_n$的初始值变为n（n位乘数的位数）
    特殊情况：和无符号一样，如果乘数或者被乘数有0的话，结果直接为0。
    示意图

重复n轮 加/减法、移位运算，直到计数器$C_n=0$：

  1. 将乘法寄存器Y的最低位、辅助位，2bit送入”控制逻辑“进行判断
  2. 根据寄存器Y的最低位、辅助位，决定是$+[X]_补，-[X]_补，+0$
  3. 将【P、Y、辅助位】视为整体，算数右移一位
  4. 计数器$C_n$减一
    示意图

结束：

  1. 乘法运算的结果用2n位暂存（寄存器P，寄存器Y），n位数乘n位数肯定不会大于2n位的。
  2. 在很多计算机架构中，通常仅保留低n位作为成乘积结果（因此，运算结果可能会发生溢出）

带符号整数乘法：溢出判断、溢出处理

溢出判断：两个 n bit带符号整数相乘，运算结果用 2n bit暂存。通常仅保留低n位作为乘法运算结果。若高n+1位不完全相同，说明发生溢出，此时可将OF标志位（溢出标志位）变为1
示意图
溢出的处理：

  1. 程序员可以选择忽略溢出，只不过会导致结果错误罢了
  2. 如果想要处理溢出这种异常，可以在乘法指令之后执行一条溢出自陷指令。该指令会检查OF标志位，若OF==1，就执行操作系统的”异常处理程序“

计算器实现乘法运算的三种方法

我们上一节用到的那种方法，n位就得n时刻，真的很浪费时间。所以我们将直接来讨论其他两种方式。

阵列乘法器

特点：可以在1个时钟内完成乘法运算

注意：阵列乘法器是快速乘法器中的一种。很多“快速乘法器”都可以在1个时钟内完成乘法运算。
示意图
你看得懂吗？看不懂吧！没事我也看不懂👍，知道怎么用就行👍

用逻辑运算、加/减运算等效实现乘法

思考：在一个没有乘法运算电路的计算机中，能否用其他运算等效实现乘法？
我们来看下面这个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 用移位运算、加法运算等效实现32bit无符号数乘法 */
unsigned int multiply_unsigned(unsigned int x, unsigned int y) {
    unsigned int result = 0;
    for (int i = 0; i < 32; i++) {
        // 提取乘数 y 的最低位
        unsigned int bit = y & 1;
        // 如果当前位为 1，加上被乘数 x
        if (bit) {
            result += x;
        }
        // 被乘数 x 左移一位，乘数 y 右移一位
        x <<= 1;
        y >>= 1;
    }
    return result;
}

这个代码的含义是32位的x与32位的y相乘。你会发现我并没有使用到乘号，只是用到了&位运算。

  • &：可以把乘数Y的最低一个比特给它取出来
    优点：在没有乘法运算电路、不支持乘法指令的计算机中，也可以等效实现乘法效果。

    缺点：运算速度很慢（在非流水线计算机中，每条指令的执行都至少需要1个时钟）

对比和总结

实现方式 核心组成 / 实现手段 运算速度 时钟周期需求 典型特点
阵列乘法器（快速乘法器） 硬件阵列结构，并行计算 ⚡ 最快 1 个时钟周期内完成 硬件复杂度高，面积大，延迟极低，适合高性能场景
ALU + 移位器 + 寄存器 + 控制逻辑 通用运算单元 + 移位寄存器 + 时序控制 🚀 较快 多个时钟周期完成 硬件复用性好，平衡性能与面积，是主流 CPU 乘法器实现方式
移位 + 加 / 减运算等效实现 软件 / 微码层面，逐位移位累加 🐢 最慢 需多次循环（与位数相关） 无需专用乘法硬件，兼容性强，适合无乘法指令的极简架构

无符号整数的除法运算原理。

手算无符号整数除法（十进制、二进制）
示意图
这里我主要说一下什么是中间余数把，就是最左边那几位，也就是你准备在商上面写下的数字的下位。

无符号整数除法：以 4bit 无符号整数为例

示意图
开始：

  • 将数据放入寄存器中：
    • 除数放入寄存器Y
    • 被除数放入寄存器【R,Q】 并完成零扩展。图中我们用的是n除以n，所以被除数n需要零扩展前面补零
    • 计数器$C_n$ 的初始值变为n。这里的n还是初始n，并不是零扩展后的
  • 特殊情况检查：
    • 如果除数为0，发生”除数为0“异常，停止除法运算，调出操作系统的异常处理程序
    • 如果被除数<除数，则商=0，余数=被除数，除法器不必再执行
      进行1+n轮处理（计算1+n位商）：
  • 上商的规则：如果【R】-【Y】>=0，则上商1，否则上商0
  • 第一轮特殊处理（商溢出规则）：
    • 直接上商，若第一位商=1，发生”商溢出“异常，停止除法运算
    • 直接上商，若第一位商=0，说明不会发生”商溢出“，不必保存这位商，也不让$C_n--$，除法运算继续。
  • 其余n轮处理：
    • 先左移，空出的位用上商
    • 上商，背后的过程可能会进行加法/减法
    • 计数器$C_n--$。当计数器$C_n=0$时，除法运算结束
      这里要注意的是，我们上商的时候其实R里面直接变成R-Y了，只不过又因为控制逻辑计数器恢复了。

关于”商溢出“的进一步讨论

示意图
其实单从这张图也能看出来，单精度真的不可能溢出。因为商最高是n位，但是双精度就不一定了。

带符号整数（补码）的除法运算原理

示意图
开始：

  • 被除数：n bit被除数，需符号扩展为 2n bit，放入寄存器【R,Q】，最后一位符号是什么扩什么。
  • 除数：n bit除数，放入寄存器【Y】
  • 计数器$C_n$：初始值为n，表示剩余n轮处理。
    n轮处理：
  • 先左移，空出的位用于上商
  • 上商：
    • 由控制逻辑根据中间余数与除数的符号组合 来决定本轮做减法还是加法(同号减，异号加)
    • 再根据ALU运算结果（新余数）的符号位来决定上商为1还是0
    • 新余数与老余数相比，符号不变->上商1；符号变->上商0
  • 计数器$C_n--$：当为0时，停止
    结束：
  • 当计数器等于0时，除法运算结束。n bit寄存器【R】保存余数、n bit寄存器【Q】保存商
  • 如果原被除数和除数异号，商Q需要取补码，取反加一。

特殊情况的判断

  • 可直接得到除法运算结果：如果|被除数|<|除数|，则商=0，余数=被除数，除法器不必再进行。
  • 除数是否为0：如果除数为0，发生”除数为0“异常，停止除法运算，调出操作系统的异常处理程序
  • 是否可能发生溢出：考试要点：对于补码的单精度除法(即nbit÷nbit，得到nbit商、nbit余数），仅“绝对值最大的负数÷-1“，才有可能发生“商溢出”异常
    示意图
    4bit的范围是-8 到 7，也就是说这样会溢出。

说些什么吧！

twikoo