在之前的 CMOS 二极管 文章中，我描述了 CMOS 晶体管的原理的制作工艺相关的一些内容，同时还说明了常用的数字电路门（与门、非门等）是如何通过 CMOS 晶体管实现的，今天我将继续接着这个话题，来看看更高层次一点的数字逻辑运算时如何通过这些门来实现的。

可能这么一说有同学不太明白，那我说一个例子，假设在 C 语言中两个 int 类型的数值相加，那么你知道这个在计算机底层是如何实现的么？又是如何映射到数字电路门的，这里就开始介绍一下。

加法器

一开始我还是从一个一个 Bit 来讲起吧，毕竟各种门一般都是对应的两个 Input 和一个 Output 的，而这两个 Input 往往就是对应着两个输入的 Bit，然后经过晶体管之后，成为一个 Output。对于与、或 和 非这几个就不说了，因为和 CMOS 二极管 中的一样实现，这里看的是加法 的实现，为什么是加法，而不是减法或者乘法，因为在计算机中，这些运算都是通过加法实现的，A - B 其实实现起来的结果是 A + （\^B），所以我们要看的是加法：

在数字电路中，如果我们只考虑加法的两个加数以及他们的和、进位，那么这种加法器称为：半加器。

上图图示就展示了半加器的示意图、真值表以及逻辑关系，通过这个图我们就实现了单个 Bit 的加法，因为这叫做 半加器，所以还有个对应的叫做 全加器 的器件：半加器和全加器的不同之处在于全加器还多了个 Cin，也就是前置进位，图示：

这里更复杂一下了，不过我们清楚它的功能就可以了，支持前置进位！。

加法实现

OK，有了 全加器 之后我们就可以来看一下加法的实现了，第一种比较粗糙的实现叫做：行波进位加法器，可以这么理解，就从假设要加两个 32bit 的 int，那么从最低位开始使用全加器运算，全加器运算完第 32 位之后，将第 32 位的进位作为第 31 位的 Cin 运算第 31 位，以此类推，也就是说计算 32bit 的加法需要进行 32 个周期。示意图为：

可以看出，这种加法的实现效率很低，但是，因为碍于进位的存在，比较难实现并发，所以为了加速，大神们想出了 先行进位加法器，这里的核心思想是，将 32bit 分为 8 组，每组 4bit，然后每组都自行组成一个单元，然后再将 8 组以 行波进位加法器 的方式实现，示意图为：

这样做的好处就是直观上是 4 倍的速度提升（实际上没那么多），这里的思想很重要，因为后面你会发现这类思想在硬件层面上有很多应用。尽管，这样的速度提升明显，但是，并不够，于是乎就有了 前缀加法器，前缀加法器的思想更进一步，我们前面是合并 4bit 之后做并行，而 前缀加法器 却是以指数的形式收敛，示意图如下：

从这样来看，效率就提升得更多了。这里用一些数值计算一下具体的提升效果，当然，这些数值都是理论值，真实情况会相对来说有所降低：

总结

从上面来看，很容易发现硬件基础就是在各种逻辑运算的基础上构建的，所以这也就是为什么数字逻辑如此重要。同时，另外一个感受就是在考虑进位的时候，然后我想起了当初毕业设计的时候编写 MD5 碰撞代码时考虑的位影响，例如一个 MD5 结果的一个位是 0，那么从 MD5 的定义的一轮运算中因为最后一轮是异或，那么我们可以推断出输入要么是 1 和 0，要么是 0 和 1，而不会全是 1 和全是 0，虽然就这么简单，但就这简单的一项就将 MD5 碰撞的速度提升了一倍，惊不惊讶！