运算电路

包含数字电路的一部分内容，为部分其他内容的基础，了解即可，一般不会直接考察。

加法运算电路

半加器

最基本的加法单元是 半加器（Half Adder）。它有两个输入，一个是加数，一个是被加数，并有两个输出，一个是和，一个是进位。

A
B
Sum = A'B + AB'
Carry = AB
A
B
S
C
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
Truth Table
Half Adder

如上图所示，通过对两个输入（A 和 B）进行异或（XOR）计算，可以得到和（S）。 通过对两个输入进行与（AND）操作，可以得到进位（C，即 Carry）。

半加器的主要限制是它只能对两个位进行加法，并且不能处理来自低位的进位输入。

全加器

全加器（Full Adder）是半加器的扩展，它加上了前一位的进位（Cin）作为第三个输入，并有两个输出，一个是和（S），一个是进位（C）。

A
B
A ⊕ B
A
B
C
0
0
0
0
0
1
0
1
0
0
1
1
Sum
Carry
0
0
1
0
1
0
0
1
Inputs
Outputs
1
0
0
1
0
1
1
1
0
1
1
1
1
0
0
1
0
1
1
1
A.B
Cin
Sum = Cin ⊕ (A ⊕ B)
Cin . (A ⊕ B)
Cout = A.B + Cin . (A ⊕ B)

半加器用于处理两个位的简单加法，而全加器则可以处理包括进位在内的三位加法，是构建复杂加法电路的基础。

加法器

为了进行多位数的加法，全加器可以串联起来形成一个 加法器，以处理多个位的二进制数加法。在这种安排中，每个全加器的进位输出连接到下一个全加器的进位输入。这样，一个 n 位的加法器可以通过串联 n 个全加器来实现。

FA
FA
FA
A0
B0
A1
B1
An-1
Bn-1
Cin
C1
C2
Cn-1
Cout
F0
F1
Fn-1

上述加法器既可以处理无符号加法（unisnged），也可以处理有符号加法（int），因为二进制加法与数据类型无关，从加法器来说，只是对 0 和 1 进行操作，数据类型是对于二进制的解释方式。

一般而言，对于有符号加法，加法器还需要考虑标志位，所以加法器也被扩展为如下结构：

FA
FA
FA
A0
B0
A1
B1
An-1
Bn-1
Cin
C1
C2
Cn-1
(CF) Cout
F0
F1
(SF) Fn-1
OF
ZF

值得一提的是带符号加法器电路是如何输出各个 标志位 的，简单而言，每个标志位都可以通过加法器电路中的位信息组合得到。

  • ZF（zero flag）：当 A+B 的结果中的每一位都为 0 时，ZF 为 1，所以 $ZF = !(F_0 F_1 \cdots F_{n-1})$。
  • SF（signed flag）：A+B 的结果的正负取决于输出结果的最高位，所以 $SF = F_{n-1}$。
  • CF（carry flag）：进位即最高位，$CF = C_{out}$
  • OF（overflow flag）：$OF = C_{n-1} \oplus C_{out}$，
    • 如果 $C_{n-1}$ 和 $C_{out}$ 不同，则表示符号位的变化导致溢出，即：
      • 一个正数加上另一个正数，结果是负数。
      • 一个负数加上另一个负数，结果是正数。
    • 如果 Cin 和 Cout 相同，则没有溢出发生。

减法运算电路

计算机中没有专门的减法电路，因为补码的减法可以被转换为加法操作：

$$[A - B]_{补} = A_补 + (-B)_补$$

以下电路可以实现操作数 A 和操作数 B 的加减法。

A
B
B
ZF
OF
SF
CF
F
Cout
Cin
Sub
n
n
n
n
n
MUX
加法器
0
1

如果是计算 A+B 的话，将 Sub 设置为 0，直接对 A 和 B 进行加法计算。

如果是计算 A-B 的话，将 Sub 设置为 1，会对 B 进行取反加一，得到 $-B_补 = \overline{B_补} + 1$，然后使用加法器计算 A + (-B) 即可。

乘法运算电路

二进制乘法与十进制乘法的手工计算方式类似：

       1011   (this is binary for decimal 11)
     × 1110   (this is binary for decimal 14)
     ======
       0000   (this is 1011 × 0)
      1011    (this is 1011 × 1, shifted one position to the left)
     1011     (this is 1011 × 1, shifted two positions to the left)
  + 1011      (this is 1011 × 1, shifted three positions to the left)
  =========
   10011010   (this is binary for decimal 154)

在计算机中实现乘法指令可以通过如下几种方式模拟以上过程：

软件算法

如果没有专有硬件支持，可以通过一系列加法和位移操作来实现乘法。编译器将乘法运算转换为一个循环代码段，在循环代码段中通过比较、加法和移位等指令实现乘法运算。

// 如何使用加法和位移来实现两个整数的乘法（了解即可）
unsigned int multiply(unsigned int a, unsigned int b) {
    unsigned int result = 0;  // 结果初始化为0
    while (b > 0) {           // 当第二个操作数大于0时继续循环
        if (b & 1) {          // 检查b的最低位是否为1
            result += a;      // 如果是，将a加到结果上
        }
        a <<= 1;              // 将a左移一位，相当于a乘以2
        b >>= 1;              // 将b右移一位，去掉已经处理过的最低位
    }
    return result;            // 返回计算的乘积
}

顺序乘法器

通过硬件的方式串行地模拟手工计算的方式，无符号数的乘法硬件电路如下图所示（了解即可）：

32 位 ALU
被乘数寄存器 X
乘积寄存器 P
乘积寄存器 Y
加
控制逻辑
计数器 Cn
64 位
32
32
32
32
右移
C

其思路是通过右移和加法，每次输出乘法结果中的一位，由于原理稍复杂，这里不阐述更多细节。

阵列乘法器

阵列乘法器（Array Multiplier）是一种用于执行乘法运算的硬件电路，它通过布置一系列全加器和半加器在一个二维网格或阵列中来实现，它能够并行处理多个位的乘法和累加，可以在一个或多个时钟周期内完成乘法操作。

除法运算电路

二进制除法在计算机中的实现与我们在十进制中所执行的传统除法类似。

          00111   商 = 0111 = 7
     ----------
0010 | 00001111   被除数 X = 15 = 1111 = 00001111
         0010     除数 Y = 2 = 0010
         -----
          0011
          0010
          -----
           0011
           0010
           ----
           0001   余数 = 0001 = 1

二进制除法可以被总结为如下步骤：

  1. 准备：
    • 将被除数和除数都转换为二进制形式。
    • 写下被除数和除数，类似于十进制除法的长除法形式。
  2. 除法：
    • 从被除数的最高位开始，与除数进行比较。
    • 如果被除数当前部分大于或等于除数，则商为 1，否则商为 0。
    • 如果商为 1，则将被除数当前部分减去除数，并将差写在下面。
    • 将被除数的下一位数字移下来，与差组成新的被除数部分。
    • 重复上述步骤，直到被除数的每一位都被处理完毕。
  3. 余数：
    • 最后一次减法运算得到的差即为余数。
    • 如果最后一次减法得到的差是0，则表示整除，没有余数。

简单的除法电路结构也是通过模拟以上过程实现（了解即可）：

32 位 ALU
除数寄存器 Y
余数寄存器 R
余数/商寄存器 Q
加/减
控制逻辑
计数器 Cn
64 位
32
32
32
32
左移
写使能

在除法电路中，在每次迭代中我们将当前余数左移一位，并引入被除数的下一位，然后执行余数减去除数的操作，接下来通过条件判断 检测减法结果的符号以确定商的当前位。

在每次迭代中，我们可以输出除法结果中的一位，重复直到处理完所有位后，可以得到商和余数的结果。