整数算术

1. 整数运算在ALU中进行

• 数据、结果、标志都保存在寄存器中
• 控制单元提供控制信号来控制数据的转运和运算的进行
• 

2. 加法全加器

• $S = X + Y $; $S = S_{n}S_{n-1}…S_{1}$; $X = X_{n}X_{n-1}…X_{1}$; $Y = Y_{n}Y_{n-1}…Y_{1}$(可能结果还会多出进位$C_{n}$
• $S_{i} = X_{i} \bigoplus Y_{i} \bigoplus C_{i-1}$; $C_{i} = X_{i}C_{i-1} | Y_{i}C_{i-1} | X_{i}Y_{i}$;
• 与门延迟: 1ty
• 或门延迟：1ty
• 异或门延迟：3ty
• 
• 

3. 串行进位加法器

• 延迟：
  • $C_{n}: 2n ty$
  • $S_{n} : (2n+1)ty$
• 缺点：慢

4. 进位超前加法器

• 1ty: 将所有的$P_{i}, G_{i}$都算好
• 2ty：计算所有的$C_{i}$
• 3ty：计算所有的$S_{i}$

5. 部分进位超前加法器

• 3ty：计算好所有$P_{i}$;$C_{i} (0<=i<=7)$；同时异或好所有$X_{i},Y_{i}$
• 2ty：开始计算$S_{i}(0<=i<=7)$;并且计算好$C_{i}(8<=i<=15)$
• 2ty：计算好$S_{i}(0<=i<=7)$;开始计算$S_{i}(8<=i<=15)$;并且计算好$C_{i}(16<=i<=23)$
• 2ty：计算好$S_{i}(8<=i<=15)$;开始计算$S_{i}(16<=i<=23)$;并且计算好$C_{i}(24<=i<=31)$
• 3ty：计算好$S_{i}(16<=i<=23)$;并且计算好$S_{i}(24<=i<=31)$

❌溢出：

• $C_{n} \neq C_{n-1}$: $overflow = C_{n} \bigoplus C_{n-1}$

• $S_{n} \neq X_{n} and S_{n} \neq Y_{n}$:$overflow = X_{n}Y_{n} \overline S_{n} | \overline X_{n} \overline Y_{n}S_{n}$;

• Cn	Cn-1	Xn	Yn	Sn
  1	0	1	1	0
  0	1	0	0	1

  Xn	Yn	Sn
  0	0	1
  1	1	0

  6. 减法

  • $[X - Y]{c} = [X]{c} + [-Y]_{c}$
  • overflow: same to addition

  

  7. 乘法

  • 模拟手算乘法的变化：

    • 每一步都计算部分积
    • 右移部分积
    • 如果$Y_{i} = 0$,右移部分积

  • example：

  • 问题：$[X \times Y]{c} \neq [X]{c} \times [Y]_{c}$; 即补码乘法结果并不等于其直接乘法结果

  • 粗略的想法：

    • 将补码表示的乘数和被乘数转为符号位表示的数
    • 然后再将计算结果转为补码表示

  • ✔️Booth’s algorithm

    

  • Booth’s algorithm

    1. $Y_{0} = 0$
    2. 根据$Y_{i+1}Y_{i}$;来决定是否是$+X | -X$
    3. 右移部分积
    4. 重复2-3的步骤n次

    

  8. 除法

  • preprocessing:

    • $X = 0$ & $Y \neq 0$: 0
    • $X \neq 0$ & $Y = 0$: exception
    • $X = 0$ & $Y = 0$: NaN
    • $X \neq 0$ & $Y \neq 0$: further processing

  • 手算除法

    • 从左到右检查被除数，直到找到大于等于除数的位置
    • 被除数减去除数，如果部分余大于等于0，商1，否则商0
    • 右移除数，然后重复上述步骤

    

    

  • ALU除法步骤

    • 扩展被除数，增加n位符号位在前面，分别存储在余数和商寄存器中
    • 左移余数和商，判断余数是否足够大
      • 足够大：做减法，然后设置商1
      • 不够大：设置商0
    • 重复上述步骤
    • 如果被除数和除数的符号不同，对计算的商取补就是真正结果
    • 余数在余数寄存器中

  • 这种除法的问题❌：

    • 回复余数的代价太高了，加减做了多次

  • 解决方法✔️: 不去恢复商

    • 只考虑减法：
      • 如果余数足够大：左移后直接减除数
      • 不够大：左移后加上除数

  9. 另一种除法

  1.步骤：

  • 向扩展n位，分别存储在余数和商中
  • 如果除数和被除数符号相同，做减法，否则做加法
    • 如果余数和除数的符号相同，商1；否则商0
  • 如果左移后的余数和除数符号相同，做减法；否则做加法
    • 如果新的余数符号和除数符号相同，商1；否则商0
  • 重复上述步骤
  2. 对商的修正，如果商是负的就加上1
  3. 对除数的修正，如果符号不同的，如果除数和被除数符号是否相同，如果相同，我们需要减去除数。
  4. 还要看余数是否和除数相同，如果相同要进行处理