软硬件融合技术内幕 终极篇 (3) 吴某凡应该蹲几年？

上期我们提到，计算机科学家们从摩尔斯电码获得启发，将现实中的物理量转换为二进制的数字信号，让数字电路进行处理，奠定了当代计算机的基础。那么，在计算机中是如何让数字信号进行运算的呢？

让我们从简单的问题开始分析。

假设我们要计算这样两个数字的和：

吴某凡(加麻大国人)，犯有AA罪，判处有期徒刑138个月，犯有BB罪，判处有期徒刑22个月，并处以驱逐出境。那么，吴某凡需要多少年以后才能回到加麻大国？

对小学二年级以上的人类而言，这是一个很简单的问题，但对于计算机而言，这是一个较为复杂的问题。

我们首先要把138和22这两个数字换算成二进制：

138 (十进制) -> 10001010 （二进制）

22 (十进制) -> 00010110 (二进制)

然后让计算机计算出这两个数字的和。

在现代的计算机中，这个问题是很容易解决的，但在最初的“图灵机”中，这却是一个很难的问题！

因为，“图灵机”是一个每次只能计算一位二进制数(以后成为1bit)的计算机！让它计算8位二进制数的加法太难了。

在工程技术中，对于复杂问题的解决方式，一般可以用D&C(Device and Conquer，分治)的方式解决。在加法运算中，这种方法就是：

列竖式。

结果是：

换算为十进制为160。也就是说吴某凡需要在监狱里面呆160个月(相当于13年4个月)，除非减轻处罚。

我们发现，如果我们期望“图灵机”能够计算多于1位的加减法，需要让它具备这些功能：

1. 计算两个1bit输入的相加；

2. 相加时还需要考虑上一位数的进位（cr）；

3. 除输出加法结果外，还能够向下一位输出进位（cr）；

用逻辑框图表示这样的数字加法器，如下图：

图中，A和B是加法的两个输入，CR_IN是上一位的进位输入。SUM是加法结果，CR_OUT是输出；

输入和输出之间的关系可以用表格来表示：

在数字电路中，这种描述输入和输出之间的表格叫做“真值表”。

我们可以将若干个这样1bit的加法器进行级联，构成多位的加法器：

图中是一个4bit + 4bit的带进位加法器。可以看出，8个这样的带进位加法器级联扩展，可以得到32bit的带进位加法器。

但是，这样的加法器存在一个难以避免的缺陷——

由于数字电路固有的特性，A，B和CR_IN输入到加法器之后，还需要一个短暂的时间才能得到输出。如果这个时间是t，那么，32bit的加法器得到结果的时间会乘以32倍，也就是32个t。

工程师们经过辅导自己孩子写作业的启发，发现在列竖式算加法的时候，实际上是可以提前预测到高位发生进位的。在计算机中，我们也可以设法让数字电路提前预知到进位的发生，而无需等待低位计算完成以后再计算高位。这种加法器叫做超前进位加法器。

超前进位加法器的原理是这样的：

我们将低位的输入记为A(i)和B(i)，低位的进位输出记为C(i)，高位的进位输出记为C(i+1)，会发现：

C(i+1) = (A(i) x B(i)) + (A(i) + B(i)) x C(i)

这个公式有点儿复杂，我们用较为简单的办法表达。

我们设G(i) = A(i) x B(i)，P(i) = A(i) + B(i)，那么，C(i+1) = G(i) + P(i) x C(i)。

由于G(i)和P(i)是从两个被加数里面直接抽取得到的，无需经过一次加法运算，实际上，我们就可以在不计算第i位加法的情况下，算出i+1位的进位值！

以4位加法器为例：

C(1) = G(0) + P(0) x C(0)

C(2) = G(1) + P(1) x C(1)

= G(1) + P(1) x (G(0) + P(0) x C(0))

这样可以算出C(3)和C(4)。

用电路进行提前计算加法的实现如下图：

显然，这个图很复杂。那么，如果想实现64 bit的加法，电路设计会变得更为复杂！

工程技术实践，是一门妥协的艺术。在实际中，64-bit的加法器会被拆分为若干个低位加法器实现，如拆成8个8位：

这样可以付出速度的代价，来对实现电路进行简化。

让我们回到开头的问题：吴某凡到底要蹲多久才能回加麻大？

答案是：吴某凡数罪并罚被判处13年，也就是156个月。这是根据《中华人民共和国刑法》，数罪并罚的刑期可以基于各罪名的刑期总和，减去若干个月。

那么，如何用计算机算出来吴某凡实际刑期减少了几个月呢？

请看下期。