使用与门、或门、非门实现加法器和减法器

wanger 2023-03-24 收录于计算机基础

笔者的程序员生涯开始于一本书：《编码：隐匿在计算机软硬件背后的语言》；

依旧清晰记得大二暑假那年读完这本书后激动的心情和颤抖的手；在随后的大学生涯中，笔者开始接触编程，旁听计算机系同学的课，系统地自学 Java，最终在大四的时候顺利找到一份编程实习工作，踏上了程序员这条路。

如今温故知新，笔者准备用这篇文章，结合代码，引用书中从零实现一个加法器和减法器的例子，带领大家领略计算机的魅力以及这本书的精彩。

本文的目标是从电路开始讲起，基于电路知识实现每个编程语言中都存在的 与 &&、或 ||、非！ 这三个逻辑门，再基于这三个逻辑门来实现一个二进制加法器和减法器；

本文会用 JavaScript 来模拟从逻辑门到加法器和减法器的过程，让我们现在开始吧！

前置知识

电路知识

手电筒

手电筒大家都用过，上面的电路也非常简单，当导线连接在一起时，灯泡会亮；导线断开时，灯泡会熄灭；

电流 & 电池

上面的灯泡会什么会亮？那是因为导线连接在一起时，会产生电流，电流经过灯泡时遇到电阻就会发光；

形象一点解释：可以把电流理解为管道里的水，把电池理解为抽水机，把灯泡理解为水力风车；

地线

地球本身就是个大导体。

拿水流举例，地就表示大海；接地表示抽水机可以从大海里抽无穷的水，也可以排无穷的水。

表示符号

手电筒电路图简化

电磁感应

当直流电通过导体时会产生磁场，而通过作成螺线管的导体时则会产生类似棒状磁铁的磁场。

继电器

继电器用到了电磁感应原理；观察下图，当螺线管的导体通电后，会产生磁场，然后会吸引上方的开关向下，连通上方导线使小灯泡发光。

逻辑门知识

有了上面的电路知识，现在可以基于电路做作出各种逻辑门

与门

只有当两个继电器都被触发的时候灯泡才会亮。这样两个继电器的串联被称为一个与门

简化符号如下：

与门的输入与输出之间的关系同样可用下表来描述:

用 JS 可以表示如下：

1
2
3


const AND = (a, b) => {
  return a && b;
};

或门

两个继电器任意一个被触发的时候灯泡就会亮。这样两个继电器的并联被称为一个或门

简化符号如下：

或门的输入与输出之间的关系同样可用下表来描述:

用 JS 可以表示如下：

1
2
3


const OR = (a, b) => {
  return a || b;
};

非门

非门又称反向器；输入端有电流时，输出端没电流；输入端没电流时，输出端有电流；

简化符号如下：

用 JS 可以表示如下：

1
2
3


const NO = (a) => {
  return !a;
};

与非门

与非门的输出和与门相反，可以用与门和非门串联得到；

简化符号如下：

与非门的输入与输出之间的关系同样可用下表来描述:

用 JS 可以表示如下：

1
2
3


const NAND = (a, b) => {
  return NO(AND(a, b));
};

或非门

或非门的输出和或门相反，可以用或门和非门串联得到；

简化符号如下：

或非门的输入与输出之间的关系同样可用下表来描述:

用 JS 可以表示如下：

1
2
3


const NOR = (a, b) => {
  return NO(OR(a, b));
};

异或门

我们还需要一个很重要的门 —— 异或门

异或门可以通过之前已经实现的其他门来组装实现，电路图如下：

电路输出结果如下：

可以发现当输入 A 和输入 B 中有且只有一个有电流进入时，才会有电流输出；

异或门的简化符号如下：

异或门的输入与输出之间的关系同样可用下表来描述：

用 JS 可以表示如下：

1
2
3


const XOR = (a, b) => {
  return AND(OR(a, b), NAND(a, b));
};

经过努力，我们已经基于电路实现了与门、或门、非门，并基于这三个基础门进一步得到了 或非门、与非门、异或门，非常棒，接下来我们会基于这些逻辑门实现加法。

实现加法器

加法是算术运算中最基本的运算，因此如果想搭建一台计算机，那么首先要造出可以计算两个数和的工具。如果深入计算机底层，你会发现，加法计算是计算机要做的唯一工作。如果我们可以造出加法器，同样地，就可以利用加法来实现减法、乘法和除法。

我们要实现的，就是类似于下方的加法器控制面板：

半加器

首先要实现一个半加器，半加器的目标是实现两个一位二进制之间的相加。

电路图如下：

可以简化如下：

用 JS 可以表示如下：

1
2
3


const HalfAdder = (a, b) => {
  return [XOR(a, b), AND(a, b)];
};

但是半加器也只能做 1 位二进制之间的加法，功能有限，要实现目标中的加法器，还需要基于半加器实现全加器。

全加器

全加器相对于半加器多了一个进位输入，这为全加器的串联从而实现多位加二进制加法提供了可能。

电路图如下：

以下表格总结了全加法器所有可能的输入组合以及对应的输出结果：

全加器可以简化如下：

用 JS 可以表示如下：

1
2
3
4
5


const FullAdder = (ci, a, b) => {
  const [s1, co1] = HalfAdder(a, b);
  const [s2, co2] = HalfAdder(s1, ci);
  return [s2, OR(co1, co2)];
};

最终实现

有了全加器，我们就可以很方便的实现多位加二进制加法了。

要注意，当把两个二进制数相加时，第 1 列的处理方式与其他列有所不同。因为后面的几列可能包括来自前面加法的进位，而第 1 列不会，所以全加器的进位输入端是接地的，这表示第 1 列的进位输入是一个 0。

对于中间的二进制位和灯泡，可以按如下办法来连接全加器：

最终，第 8 个灯泡和最后一对开关将以如下方式连接到全加法器上：

还可以用另一种方式来看这 8 个全加器的连接，每个全加器的进位输出都作为下一个全加器的进位输入：

加器器可以简化如下：

继续简化：

基于 8 位加法器，可以通过串联轻松实现 16 位加法器。

代码实现加法器

有了上面铺垫，可以很轻松地用代码模拟八位加法器：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


const EightBitAdder = (arr1, arr2) => {
  const [a7, a6, a5, a4, a3, a2, a1, a0] = arr1;
  const [b7, b6, b5, b4, b3, b2, b1, b0] = arr2;
  const [s0, co0] = FullAdder(false, a0, b0);
  const [s1, co1] = FullAdder(co0, a1, b1);
  const [s2, co2] = FullAdder(co1, a2, b2);
  const [s3, co3] = FullAdder(co2, a3, b3);
  const [s4, co4] = FullAdder(co3, a4, b4);
  const [s5, co5] = FullAdder(co4, a5, b5);
  const [s6, co6] = FullAdder(co5, a6, b6);
  const [s7, co7] = FullAdder(co6, a7, b7);
  return [+co7, +s7, +s6, +s5, +s4, +s3, +s2, +s1, +s0];
};

测试一下效果：

1
2
3


console.log(EightBitAdder([0, 1, 1, 0, 0, 1, 0, 1], [1, 0, 1, 1, 0, 1, 1, 0]));

// [1, 0, 0, 0, 1, 1, 0, 1, 1]

最终的加法器的完整代码如下，可以看到代码中只用了逻辑门，没有用一个数学运算符，便实现了加法运算：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


// 与门
const AND = (a, b) => {
  return a && b;
};

// 或门
const OR = (a, b) => {
  return a || b;
};

// 非门
const NO = (a) => {
  return !a;
};

// 或非门
const NOR = (a, b) => {
  return NO(OR(a, b));
};

// 与非门
const NAND = (a, b) => {
  return NO(AND(a, b));
};

// 异或门
const XOR = (a, b) => {
  return AND(OR(a, b), NAND(a, b));
};

/**
 * 半加器
 *
 * @returns [加加输出, 进位输出]
 */
const HalfAdder = (a, b) => {
  return [XOR(a, b), AND(a, b)];
};

/**
 * 全加器
 *
 * @param {*} ci 进位输入
 * @param {*} a 输入
 * @param {*} b 输入
 * @returns [加加输出, 进位输出]
 */
const FullAdder = (ci, a, b) => {
  const [s1, co1] = HalfAdder(a, b);
  const [s2, co2] = HalfAdder(s1, ci);
  return [s2, OR(co1, co2)];
};

// 八位加法器
const EightBitAdder = (arr1, arr2) => {
  const [a7, a6, a5, a4, a3, a2, a1, a0] = arr1;
  const [b7, b6, b5, b4, b3, b2, b1, b0] = arr2;
  const [s0, co0] = FullAdder(false, a0, b0);
  const [s1, co1] = FullAdder(co0, a1, b1);
  const [s2, co2] = FullAdder(co1, a2, b2);
  const [s3, co3] = FullAdder(co2, a3, b3);
  const [s4, co4] = FullAdder(co3, a4, b4);
  const [s5, co5] = FullAdder(co4, a5, b5);
  const [s6, co6] = FullAdder(co5, a6, b6);
  const [s7, co7] = FullAdder(co6, a7, b7);
  return [+co7, +s7, +s6, +s5, +s4, +s3, +s2, +s1, +s0];
};

实现减法器

接下来来实现减法器，我们要实现的，就是类似于下的减法器控制面板：

之前的加法器可以通过进位很轻松的完成计算；

但是在减法中没有进位，而是有借位，这就很麻烦；借位是一种与加法存在本质区别的麻烦机制。

先看看十进制减法

日常生活中用减法时，怎么避免借位呢？

思考十秒…

可以采用如下方式：

253 - 176

在这个式子中加上一个数再减去这个数，结果是相同的。因此先加上 1000，再减去 1000：

253 - 176 + 1000 - 1000

这个式子与下式等价：

253 - 176 + 999 + 1 - 1000

然后用以下方式将数字重新组合：

253 + (999 - 176) + 1 - 1000

用 999 减去目标数，则达到了不用借位的目标，如图：

第一步：

第二步：

第三步：

在看看二进制减法

有了上面十进制减法的基础，现在来看看二进制减法。

第一步，用 11111111（即 255）减去减数：

这其实就是是计算机中的补码

第二步，将减数对 1 的补数与被减数相加：

第三步，将上式所得结果加 1：

第四步，减去 100000000（即 256）：

结果就等于十进制数的 77。

求补器

上面提到了补码的概念，相当于对每位取反，因此我们计算 8 位二进制数补数的时候可以简单地用 8 个反向器：

问题是，该电路只会对输入求反，而我们要的是一台既能做加法又能做减法的机器，因此就要求该电路仅当进行减法运算时才实现反转。电路可以改造为如下图所示：

简化图如下：

用 JS 可以表示如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


const Complementer = (sub, arr) => {
  const [a7, a6, a5, a4, a3, a2, a1, a0] = arr;
  return [
    XOR(sub, a7),
    XOR(sub, a6),
    XOR(sub, a5),
    XOR(sub, a4),
    XOR(sub, a3),
    XOR(sub, a2),
    XOR(sub, a1),
    XOR(sub, a0),
  ];
};

最终实现

注意，这里三个信号都标识为“SUB”，这就是加/减法转换开关。当该信号为 0 的时候，其进行的是加法运算，为 1 时进行的则是减法运算。在减法中，输入 B（第二排开关）在送入加法器之前，需先通过求补电路进行取反。此外，在做减法时，我们通过设定 CI（进位输入）为 1 来使得结果加 1。而在加法中，求补电路将不起作用，且输入 CI 为 0。

用 JS 可以表示如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


const EightBitMinus = (arr1, arr2) => {
  const [a7, a6, a5, a4, a3, a2, a1, a0] = arr1;
  const [b7, b6, b5, b4, b3, b2, b1, b0] = Complementer(true, arr2);
  const [s0, co0] = FullAdder(true, a0, b0);
  const [s1, co1] = FullAdder(co0, a1, b1);
  const [s2, co2] = FullAdder(co1, a2, b2);
  const [s3, co3] = FullAdder(co2, a3, b3);
  const [s4, co4] = FullAdder(co3, a4, b4);
  const [s5, co5] = FullAdder(co4, a5, b5);
  const [s6, co6] = FullAdder(co5, a6, b6);
  const [s7, co7] = FullAdder(co6, a7, b7);
  const co = XOR(true, co7);
  return [+co, +s7, +s6, +s5, +s4, +s3, +s2, +s1, +s0];
};

测试一下效果：

1
2
3


console.log(EightBitMinus([1, 1, 1, 0, 1, 0, 0, 0], [0, 1, 0, 1, 0, 1, 0, 1]));

// [0, 1, 0, 0, 1, 0, 0, 1, 1]

总结

本文从基础电路开始，实现了与门、或门、非门、或非门、与非门、异或门 这些基础的逻辑门，再基于这些逻辑门，实现了一个简单的加法器和减法器，并给出了相应的代码实现；整体可以看到代码中只用了逻辑门，没有用一个数学运算符，便实现了加法和减法运算。

本文只是抛砖引玉，希望能给到对计算机感兴趣的同学一点点启发。

实际上，《编码》这本书中还有其他非常精彩的部分，例如寄存器的实现，强烈建议感兴趣的同学读一读原书，点击这里可以下载。

目录

使用与门、或门、非门实现加法器和减法器

前置知识

电路知识

手电筒

电流 & 电池

地线

表示符号

手电筒电路图简化

电磁感应

继电器

逻辑门知识

与门

或门

非门

与非门

或非门

异或门

实现加法器

半加器

全加器

最终实现

代码实现加法器

实现减法器

先看看十进制减法

在看看二进制减法

求补器

最终实现

总结