ALU运算器的计算逻辑以及电路实现
计算机运行机制
Datapath是运算器
问题一：运算器需要完成什么样的功能？
1． 至少完成加、减、乘、除、逻辑的与或非
问题二：除了得到计算的结果还要得到运行结果的状态？
是否进位C，是否为0，是否溢出，是正数还是负数
问题三：数据来源于（寄存器组（运算器内部的组成部分）、数据总线（存储器））
问题四：计算结果放到寄存器组（运算器内部的组成部分）、数据总线（存储器））
问题五：暂存运算的中间结果（Q寄存器，移位寄存器）
问题六：控制器控制计算过程
要想完成加、减、乘、除、逻辑的与或非需要哪些部件呢？
1. 逻辑门电路（完成逻辑运算）
2. 加法器（完成加法运算）
3. 以触发器（保存数据）为基础实现寄存器组
4. 多路选择器、移位器（选择、连通），乘除法需要移位器
一个基本的数据通路如下所示：ALU就是核心，本文将主要学习ALU
1位ALU的逻辑运算实现（1位指的是A和B只有一位）
在数字逻辑中学过与门还有或门，所以只要将两个数A、B输入到与门中那么就是与运算，如果要是输入到或门中就是或运算，我们可以将这两个门结合在一起，然后接上控制器，当我们输入AB的时候，同时计算与和或，然后根据控制器信号来判断究竟是输出与还是输出或。
就信号而言，这里我们认为当OP=1的时候，表示或，当OP=0的时候表示与
现在如何做加法？
如图所示是加法运算，我们可以看到从低位开始，如果是1+1那么则往上进一位，所以对于1位的ALU来说，应该有三个输入：第一个输入是A、第二个输入是B、第三个输入是第维计算的进位CarryIn，同时应该有两个输出：第一个输出是当前位，第二个输出是当前的计算往高位的进位。
所以我们只需要设计一个1位的ALU就可以了，这样从低位开始计算，接收输入A、B、CarryIn,输出Output和Carryout，同时CarryOut作为高位计算时的CarryIn，然后outputs被保存起来，用于最终的结果。现在输入和输出已经知道了，我们只需要将所有的加法逻辑想出来，那么我们就可以按照这个数字逻辑设计一个ALU，就可以了。
加法逻辑如下所示：
所以我们可以按照这个逻辑来设计电路：
最终1位的加法运算器就完成了，当然这个内部的逻辑肯定是有些复杂了，一般来说都是可以通过与和或门组合实现，比如相加，那么就是1+0=1，1+1=0,0+1=1,那么这个可以使用逻辑或门实现，然后1+1=0向高位进1(carryout=0),1+0=0向高位进0，0+1=0向高位进0，所以我们这里可以使用逻辑与门来实现向高位进位，这是基本的逻辑，内部的详细设计这里就不介绍了，如下图所示，全加器可以完成一位的加法：
也就是说我们通过这样的一个全加器就可以完成一位的计算了。但是相加的时候需要多位相加，那么这个时候就需要多个一位全全加器并排使用了，将低维的carryout作为高位的carryin就可以实多位的计算了。所以只要弄懂一个，其它的就全懂了
但是我们可以发现这个是串联的，我们变成的时候一个思维是串行化处理，所以为了解决这个问题，我们需要思考，是否可以并小型化的计算？
如果我们可以知道，每一个的进位，那么就可以同时计算了，我们可以发现有这样的规律
我们把这个看成一个从低位到高位的时间步，那么每个事件步接收上一事件步的进位，
我把当前时刻看成t时刻
当a=b=0,此时的进位为0
当a=b=1，此时的进位为1
当a=0，b=1，或者a=0，b=1时，此时的进位为t-1时刻的进位，也就是说t-1时刻要是进1，那么t时刻就往t+1时刻进1，要是t-1时刻进0，那么t时刻就往t+1时刻进0.
现在规律找到了，我们如何才可以表示这个规律呢？
我们Ci表示i时刻的进位，我们可以得到下面的递推关系：
我们可以看到a1b1表示与，a1+b1表示或
所以在计算加之前，我们可以设计一个进位电路，先将所有的进位算出来，然后并行使用全加器就可以完成最终的计算了
现在加法会了，我们来看一下如何做减法
A- B=A+(-B),补码的负非常简单，所以A-B的核心还是加法，这里就不详细介绍了，先把B变成-B，然后再相加就可以了
下面我们看一下乘法怎么来完成：
对于二进制的乘法可以看到，1*1000=1000，0乘1000=0000，如果我们使用语言来描述这个过程是：
我们需要设置三个寄存器，分别是乘数寄存器，被乘数寄存器，以及部分积寄存器，他们的架构如下所示：
我们可以看到被乘数寄存器为64位，而乘数寄存器为32位，然后部分积寄存器为64位，为了方便显示，我们这里进行等比例得缩放，我们令被乘数寄存器为8位，乘数寄存器为4位，然后部分积寄存器为8位，
这样我们得乘数就是1001，被乘数是00001000，然后部分积初始为00000000，然后先看乘数寄存器得低位为1，那么将被乘数和部分积相加结果为00001000，然后将乘数寄存器右移一位，也就是把刚才得低位溢出掉，此时乘数变为0100，然后将被乘数左移一位，此时为00010000，继续这个过程，此时乘数低位为0，此时跳过，然后将乘数右移一位0010和被乘数左移一位00100000，此时乘数低位为0，此时跳过，然后将乘数右移一位0001和被乘数左移一位01000000，然后此时乘数低位为1，然后将被乘数和部分位相加00001000+
01000000=01001000，最终结果计算完毕。
我们可以发现此时有一个问题就是被乘数居然也要有64位，其实它不需要这么多位，它只需要32位就可以了。因为在上面得时候，我们将被乘数寄存器不断得左移就是为了和部分积相加得时候保证加在了部分积的高位，此时我们可以转变思想，我们可以让部分积右移，同时相加的时候被乘数和部分积的高位相加（左半部分），那么就一样了，由于部分积寄存器是64位，因为它从开始，相加的时候只加左半部分，所以等到加完，最初相加的右半部分也不会溢出，所以就可以将被乘数的寄存器设计为32位了。
我们看看此时是否还可以继续优化，我们发现乘数的最低位每计算完一次，我们就右移一词，我们将其抛弃掉，那么说明这个和我们没有任何意义，正好我们的部分积寄存器的右半部分也是每次就右移一位，因为是左边开始相加的，左右部分对等，所以我们也不担心会丢掉信息，那么我们可以将乘数寄存器放在部分积寄存器的右边，这样在只需要右移部分积寄存器，那么就同时完成了内部积寄存器和乘数寄存器的工作了。是不是乘数寄存器的空间就被省了呢，所以我们可以设计如下所示的部件：
也就是说每次当被乘数最低位为1，则将被乘数相加到部分积寄存器的左边，同时将部分积寄存器右移，如果被乘数最低为为0，只需要将部分积寄存器右移一位就可以了
至此我们就设计出来了非常完善的乘法部件了，但是我们发现上面的使用是全是正数，那么负数我们应该怎样来做呢？
负数可以通过下面的方式来计算：
方案一：将负数的补码转换为原码绝对值，进行原码的正数乘法
然后根据同号为正，异号为负的原则得到符号位，并转换回补码表示
这种方法需要将补码先转换为原码，计算非常的不方便，我们应该探索一种可以通过补码直接计算的方法，这种方法叫做布斯算法
布斯算法的核心思想是将乘法转变为加法和减法，x和y相乘的补码可以通过下面的方式来计算。我们可以看到[x*y]补=[x]补*y的真值，然后将y真值变换，最终可以得到最终的形式，我们可以看到yi-1和yi是补码y的相邻的两个位，当这两个决定了是加[x]补，还是减[x]补，还是加0，减0
那么通过这个式子可以判断到，根据乘数y的补码的相邻两位yi-1和yi有以下两种情况
也就是说通过乘数y的补码的相邻两位，我们可以判断是加被乘数还是减去被乘数，还是加0，下面我们通过一个例子来看一下：
这个就是乘法的部件，根据类比，我们设置被乘数5位，然后部分积寄存器10位，然后部分积寄存器中左边的5位位空，右边的五位存储的是乘数，开始的使用判断被乘数的yi-1和yi，也就是y-1=0（附加位）和y0=1，那么此时按照规则应该是减x，减x就是加负x。然后那么改判断y0和y1了，此时只需要将部分积寄存器右移一位，然后溢出的那位放到附加位中，覆盖原来的，那么反复计算最终可以得到乘法结果。
那么通过上面的方式负数的乘法也可以通过补码来做了。
下面我们来看以下除法：
X=0.10110
Y=0.1101
X/Y其中Y表示除数，X表示被除数，他们的计算过程中会产生商和余数。我们下面看看上面的计算过程是怎么进行的，主要分为两个步骤
① 判断被除数或余数是否比除数大,
如果小，商0
如果大，商1，使用被除数-余数
② 除数右移一位（使用除数寄存器保存）
我们下面通过详细的计算过程来进行分析：
1、被除数0.1011小于除数0.1101，此时商0，除数右移一位为0.01101
2、被除数0.1011大于除数0.01101，此时商1，做减法0.1011-0.01101=0.010010（余数），除数右移一位0.001101
3、余数0.010010 (现在是余数了)大于除数0.001101，此时商1，做减法0.010010-0.001101=0.00010100(余数)，除数右移一位0.0001101
4、余数0.00010100小于除数0.0001101，商0，此时除数右移1位0.00001101
5、余数0.00010100大于除数0.00001101，商1，做减法0.00010100-0.00001101=0.00000111
此时计算文成，此时的商为0.1101，余数为0.00000111
我们可以看到通过这个方式可以来解决问题，但是这个会有一些问题，首先我们如何才可以判断被除数或者余数比除数大，从人类的角度来说需要比较一下，而计算机的做法是需要实际上去减一下，如果减的结果大于0，那么证明被除数或者余数比除数大，如果小于0，那么证明除数或者余数比除数小。这就产生了一个问题，如果大的话还好说，本来就需要减去，但是小的话可不不行，因为根据上面的式子可以看出来，小的话不需要减去，所以从这个角度来说，小的话还得加回来，这就是一个问题了重复计算。
第二个问题除数右移一位，我们可以传到除数从最开始的0.1101右移到了0.00001101，也就是说我们需要两倍的空间来存储它，这显然有些浪费空间了，所以从这个角度考虑我们可以将除数右移转变为余数左移，而被除数不动的思想。我们可以发现随着计算的过程中余数的左边慢慢地为0了，所以它左移没有关系。再仔细地分析一下，0.00000111=0.111*2^-5
而上面我们正好计算了五次，所以我们地余数寄存器最终只需要记住0.111就可以了。、
再思考一下上面的如果小的话需要将减去的再加上，这种重复计算的问题怎么解决呢？
我们需要找到一个规律，我们在计算过程中有三个余数，分别为Ri-1，Ri，Ri+1，除数为Y
会出现以下两种情况：
第i-1次求商，减运算地余数为Ri-1，然后左移1位，变为2Ri-1
然后减去Y判断正负Ri=2Ri-1-Y，如果为正，那么商1，然后左移1位，变为2Ri,然后再做减运算Ri+1=2Ri-Y
如果为负Ri<0，那么商0，将恢复余数，需要将Ri+Y，然后左移一位2（Ri+Y），再作减运算Ri+1=2（Ri+Y）-Y=2Ri+Y
那么至此就可以看到了两种不同的情况，所以我们可以看到当Ri小于0的时候，我们只需要加上Y，如果Ri大于0的时候，我们只需要减去Y，所以正确的方法是得到Ri之后我们就获取到了它的正负，它将决定我们是加Y还是减Y，只要按照这个步骤行进就ok了。
整个模型可以这样来实现，我门将余数左移，然后将左移出来的位置放置商，这样商也ok了。