算数运算整理（一）

文章目录

• 算数运算整理（一）
• • 1 移位运算
  • • 1.1 逻辑移位
    • 1.2 循环移位
    • 1.3 算数移位
  • 2 加减运算
  • • 2.1 补码加减法运算规则
    • 2.2 补码加减法的硬件实现
    • • 2.2.1 全加器
      • 2.2.2 行波进位加法器（Ripple-Carry Adder，RCA）
      • 2.2.3 超前进位加法器
      • 2.2.4 减法的实现
      • 2.2.5 溢出的判断
      • • （1）采用两个操作数和结果的符号来判断
        • （2）采用最高数值位产生的进位与符号位产生的进位来判断
        • （3）采用变形补码来判断
      • 2.2.6 进位旁路加法器
      • 2.2.7 进位选择加法器
      • 2.2.8 进位保存加法器（3-2压缩）
      • 2.2.9 Sklansky加法器
      • 2.2.10 Kogge-Stone加法器
      • 2.2.11 Brent-Kung加法器
  • 参考

算数运算整理（一）

1 移位运算

1.1 逻辑移位

逻辑移位中，被移位的数据是逻辑数，没有符号和大小
（1）逻辑左移：右侧补“0”
（2）逻辑右移：左侧补“0”

1.2 循环移位

循环移位与逻辑移位相似，不同之处是：循环移位将一端移出的数据补在另一端，形成闭合的位移环路。

1.3 算数移位

算数移位对带符号的数进行移位，移位会引起数值的变化，算数右移相当于将原数除以2，算数左移相当于将原数乘以2

对于不同数字表示形式，算术移位的规则也不同。

（1）原码算数移位

符号位不参与移位，移位后补“0”

（2）补码算数移位

对补码表示的数字移位时，符号位一起参与移位，规则如下：

• 算数左移：右侧补“0”
• 算数右移：移位前符号位是什么，移位后左侧就补什么
  需要注意，对补码表示的数字进行算数左移操作时，可能发生溢出！！

（3）反码算数移位

正数反码的移位规则与补码一样，左移时右侧补“0”，右移时左侧补符号位的数字。负数反码比较特殊，左移时右侧补“1”，右移时左侧补符号位的数字。

2 加减运算

以下只讨论补码表示的数字的加减运算。

2.1 补码加减法运算规则

设 [ X ] 补 [X]_{补} [X]补​与 [ Y ] 补 [Y]_{补} [Y]补​均为$n$位补码数字，其中包含一位符号位，则
[ X + Y ] 补 = [ X ] 补 + [ Y ] 补 [ X − Y ] 补 = [ X ] 补 + [ − Y ] 补 [X + Y]_{补} = [X]_{补} + [Y]_{补}\\ [X - Y]_{补} = [X]_{补} + [-Y]_{补} [X+Y]补​=[X]补​+[Y]补​[X−Y]补​=[X]补​+[−Y]补​
由上式可知，补码加减法运算的基本规则：

• 参加运算的两个操作数和运算结果均用补码表示
• 符号位和数值位一起参加运算
• 补码加法时，直接将两个补码数相加，即得两数之和的补码
• 补码减法运算转换成加法进行
• 补码是在模M的意义下相加减，如果运算结果超过了模，则将该进位自动丢弃（如果$X,Y$是定点小数，则$M=2$；如果$X,Y$是定点整数，则 M = 2 n M=2^n M=2n）

2.2 补码加减法的硬件实现

2.2.1 全加器

一位全加器时最简单的加法器，它有三个输入端：两个数字$A,B$和进位输入 C i n C_{in} Cin​，输出有两个：求和结果$S$和进位输出 C o u t C_{out} Cout​，其电路图如下所示：

S = A ⊕ B ⊕ C i n C o u t = A ⋅ B + C i n ⋅ ( A ⊕ B ) S = A \oplus B \oplus C_in\\ C_{out} = A \sdot B + C_{in} \sdot (A \oplus B) S=A⊕B⊕Ci​nCout​=A⋅B+Cin​⋅(A⊕B)

2.2.2 行波进位加法器（Ripple-Carry Adder，RCA）

当需要进行多bit二进制数相加的时候，比如两个4bit数字相加，就需要用到四个全加器。最直观的想法就是将四个全加器串联起来，前一级的进位输出端连接上后一级的进位输出端，如下图所示，客样就可以实现一个4bit二进制数相加的加法器。

这样的加法器的进位端的数值从1号全加器开始，逐级向右传播，只有当低位的进位数据准确传递到本级全加器的进位输入端后，本级加法器才能输出正确的求和数据，因此得名行波进位加法器。
行波进位加法器的优点是电路布局简单、设计方便。但是缺点也很明显，就是高位的运算必须等待低位的进位信号，这就造成了整个加法器的延迟很长。
将上图中的4bitRCA展开，其用门电路实现的电路图如下所示：

该电路中的关键路径已经用红色表示出来。如果只考虑门延迟，且每个门延迟都为$T$的话，该4bit加法器的总延迟时间为$9T$，同理，如果是一个32bit的加法器，则总延迟应该为$65T$。
这是什么概念呢？举个例子，iPhone 5s的A7 SoC处理器采用28nm制造工艺，主频1.3GHz（0.66ns）。按照这个工艺水平，门延迟T设为0.02ns，那么32-bit RCA的延迟时间为1.3ns ，时钟频率为769MHz，远超A7处理器的主频延迟时间，更别说这个32bit的RCA只是一个加法运算器，更更别说，我们在计算过程中只考虑了门延迟，还有线延迟等各种延迟没有加入计算。因此实际ALU单元中很少采用行波进位加法器。

2.2.3 超前进位加法器

通过分析行波加法器的计算过程，我们发现主要是由于进位信号需要等待低位的计算的完成从而影响了加法的效率。因此有没有办法能够“提前得到进位信号”呢？

对于一个1bit全加器，我们都可以将进位输出信号表示为如下的形式：
C i + 1 = A i ⋅ B i + ( A i + B i ) ⋅ C i C_{i+1} = A_i\sdot B_i + (A_i + B_i)\sdot C_i Ci+1​=A

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！