能加offer的加法器你会吗？

一位加法器

半加器
如果不考虑来自低位的进位将两个1二进制数相加，称为半加。
实现半加运算的逻辑电路称为半加器。

逻辑表达式:
s=ab′+a′b
co=ab

全加器
在将两位多位二进制数相加时，除了最低位以外，每位都应该考虑来自低位的进位，即将两个对应位的加数和来自低位的进位3个数相加。这种运算称为全加，所用的电路称为全加器。

逻辑表达式
s=(a′b′ci′+ab′ci+a′bci+abci′)′
co=(a′b′+b′ci′+a′ci′)′
全加器可以用两个半加器来构造，将输入端A和B连接到一个半加器上，然后将其输出信号与进位输入信号分别作为第二个半加器的两个输入，并将前后两个进位输出信号进行逻辑或运算作为最终的进位
在数字电路中，二进制数的减法可以通过加一个负数来间接完成。为了使负数的计算能够直接用加法器来完成，计算中的负数可以使用二补数（补码）来表示。

多位加法器

串行进位加法器/行波进位加法器
依次将低位全加器的进位输出co接到全加器的进位输入端ci，就可以构成多位加法器。
显然，每一位的相加结果都必须等到低一位的进位产生才能建立起来，因此，这种结构的电路称为串行进位加法器（也被称为行波进位加法器）。如果最低位没有进位输入，最低位的全加器可以用半加器替换,串行进位加法器的电路布局形式较为简单，设计这种电路花费时间较短。然而，串行进位加法器的进位输出、输入所经过的路径上比其他布局方式具有较多的逻辑门，高位的计算必须等待低位的进位输出信号被计算出来才能开始，因此造成了更大的延迟时间。交替进位极性和优化的与或非门的设计可以减少一半的延迟时间，详情请看Burgess, N在2011年发表的文章。

超前进位加法器
为了减少多位二进制数加减计算所需的时间，工程师设计了一种比串行进位加法器速度更快的加法器电路，这种加法器被称为“超前进位加法器”，之所以叫超前进位加法器，是因为每一级的进位都不依赖于上一级的进位，因此不需要等待上一个加法器完成计算，超前得到进位结果。下图为两个四位超前进位加法器

超前进位信号的产生原理:
ab = 1 --> Co = 1
a + b = 1,且ci = 1 --> Co =1
两位多位数中第i位相加产生的进位输出Co(i)可以表示位
Coi=aibi+(ai+bi)(Cii)
从全加器的真值表写出第i位和S(i)的逻辑式：
Si=aibi′Cii′+ai′biCii′+ai′bi′Cii+(ai+bi)Cii
上式变换位异或函数位：
Si=ai⊕bi⊕Cii
最终Si和Coi的逻辑表达式为：
Coi=aibi+(ai+bi)(Cii)——内部含有迭代
Si=ai⊕bi⊕Cii——内部含有迭代

将四个加法器串联，迭代可以得到：


通过列出多位加法器各位的进位输出，可以发现高位的进位输出表达式（积之和式）涉及的变量更多，对应的逻辑电路连线会变得更复杂，而且在实际应用中会遭遇逻辑门的扇入问题。因此有必要对位数过高的全加器进行逻辑划分，如将六十四位全加器分为四个十六位超前进位加法器来实现（如下图）

串行进位加法器优缺点：低位全加器的Cout连接到高一位全加器Cin，电路布局简单，设计方便，高位的运算必须等待低位的运算完成，延迟时间长；
超前进位加法器优缺点：每个全加器的进位输入并不来自于前一级的全加器，而是来自超前进位的逻辑，计算Ci+1的延迟时间固定为三级门延迟，与加法器的位数无关，如果进一步拓宽加法器的位数，则电路变得非常复杂。

补充：
使用加法器计算7bit中1的数量，最少用几个？
有7个1bit的数，为他们编号，从b0到b6
使用1bit全加器可以将3个bit相加，得到2bit的结果，那么b0，b1，b2使用一个加法器，b3，b4，b5使用一个加法器
现在7个1bit变成了2个2bit和一个1bit(b6)
然后使用一个2bit全加器将两个2bit数进行相加，1bit的b6作为进位输入。相加后结果为3位，最大可以表示到7个1bit
而2bit全加器可以有2个1bit全加器组成，所以一共使用4个1bit全加器可以完成1的数量的统计
2bit全加器可以有2个1bit全加器组成实现：2bit的低位和b6使用一个全加器，产生的进位作为最终结果的最低位，产生的和与2bit的高位适使用一个全加器，产生的进位作为最终结果的次低位，产生的和作为最终结果的最高位。

哈姆雷特，请保持前行！