加法、减法、乘法与除法
1. 加法和减法
计算机中的数据从右到左逐位相加，进位向左传播。减法可以通过将被减数取反（二进制补码）后与减数相加来实现。
1.1. 二进制加法
- 原理：逐位相加，并处理进位。
- 示例：计算 7 + 6 (0000 0111₂ + 0000 0110₂) (0)(0)(1)(1) (进位) 0000 0111 (7₁₀)
- 0000 0110 (6₁₀)
0000 1101 (13₁₀)
1.2. 二进制减法
- 直接操作：类似于手动减法，需要借位。
- 示例：计算 7 - 6 (0000 0111₂ - 0000 0110₂)
```
0000 0111 (7₁₀)
- 0000 0110 (6₁₀)
0000 0001 (1₁₀)```
- 通过加法实现：加上减数的二进制补码。
- -6₁₀的二进制补码 (假设32位)：
- 6₁₀ = 00...0000 0110₂
- 取反：11...1111 1001₂
- 加1 ：11...1111 1010₂ (-6₁₀)
- 示例：7 + (-6)
```
0000 0000 ... 0000 0111 (7₁₀)
+ 1111 1111 ... 1111 1010 (-6₁₀)
(1) 0000 0000 ... 0000 0001 (1₁₀) (最高位进位被舍弃) ```
1.3. 溢出 (Overflow)
当运算结果超出计算机字长（如32位）能表示的范围时发生。
-
加法溢出：
- 不发生溢出：两个源操作数符号相异时（如 -10 + 4 = -6）。
- 发生溢出条件：
- 正数 + 正数 = 负数
- 负数 + 负数 = 正数
- 实质：结果的符号位被数值位占用。
-
减法溢出 (A - B)：
- 不发生溢出：两个源操作数符号相同时 (因为 A - B = A + (-B)，变成异号相加)。
- 发生溢出条件：
- 正数 - 负数 = 负数 (相当于 正数 + 正数 = 负数)
- 负数 - 正数 = 正数 (相当于 负数 + 负数 = 正数)
- 实质：借位占用了符号位。
- 图 3-2 加减法溢出条件总结： | 操作 | 操作数 A | 操作数 B | 结果 | 溢出情况 | |------|----------|----------|--------|----------| | A+B | ≥0 | ≥0 | <0 | 溢出 | | A+B | <0 | <0 | ≥0 | 溢出 | | A+B | ≥0 | <0 | N/A | 不溢出 | | A+B | <0 | ≥0 | N/A | 不溢出 | | A-B | ≥0 | <0 | <0 | 溢出 | | A-B | <0 | ≥0 | ≥0 | 溢出 | | A-B | ≥0 | ≥0 | N/A | 不溢出 | | A-B | <0 | <0 | N/A | 不溢出 |
-
无符号整数溢出：通常用于内存地址计算，溢出一般被忽略。
1.4. MIPS 中的加减法指令与溢出处理
- 算术逻辑单元 (ALU)：执行加减法、逻辑运算的硬件。
- 异常 (Exception) / 中断 (Interrupt)：打断正常程序执行的事件，用于溢出检测等。
- 异常程序计数器 (EPC)：MIPS 中保存导致异常的指令地址的寄存器。
mfc0指令：将系统控制寄存器（如EPC）内容移至通用寄存器。
- MIPS 算术指令：
add,addi,sub: 溢出时产生异常。addu,addiu,subu: 溢出时不产生异常 (u 代表 unsigned，但更准确地说是“不捕获溢出”)。 精解 (addiu):u表示不产生溢出异常，但其16位立即数字段仍进行符号扩展为32位。
- 硬件/软件接口 (溢出处理)：
- C 和 Java 等语言忽略整数溢出。
- Ada 和 Fortran 等语言需要通知程序溢出。
- MIPS C 编译器通常使用
addu,addiu,subu来避免异常。
- 硬件/软件接口 (异常返回)：
- MIPS 允许程序员将寄存器
$k0和$k1预留给操作系统，用于异常处理时保存返回地址等信息，避免破坏用户寄存器状态。
- MIPS 允许程序员将寄存器
1.5. 其他相关概念
-
**字节/半字算术：MIPS只有整字整数算术操作。处理字节/半字：
- 取数：
lb(load byte),lbu(load byte unsigned),lh(load halfword),lhu(load halfword unsigned)。 - 算术操作：使用标准
add,sub等。 - 结果处理：使用
AND指令屏蔽结果到8位或16位（如果需要截断）。 - 存数：
sb(store byte),sh(store halfword)。 正确选项为 3
- 取数：
-
饱和 (Saturating) 操作：
- 结果溢出时，被设置为最大正数或最小负数，而非取模。
- 适合多媒体操作（如音量调节）。标准MIPS指令集不包含，但媒体扩展指令可能提供。
-
MIPS 软件检测溢出 (示例代码片段)：
- 有符号加法 ($t0 = $t1 + $t2$)：
assembly addu $t0, $t1, $t2 # $t0 = sum, don't trap xor $t3, $t1, $t2 # Check if $t1, $t2 signs differ slt $t3, $t3, $zero # $t3 = 1 if signs differ (i.e., $t3 is negative if signs differ) bne $t3, $zero, No_overflow # If signs differ, no overflow # Signs are the same, check if sum's sign is different xor $t3, $t0, $t1 # $t3 negative if sum sign different from $t1's sign slt $t3, $t3, $zero # $t3 = 1 if sum sign different bne $t3, $zero, Overflow # If different, then overflow No_overflow: ... Overflow: ... - 无符号加法 ($t0 = $t1 + $t2$)：
assembly addu $t0, $t1, $t2 # $t0 = sum # Overflow if $t0 < $t1 (or $t0 < $t2) sltu $t3, $t0, $t1 # $t3 = 1 if $t0 < $t1 bne $t3, $zero, Overflow # If $t0 < $t1, then overflow No_overflow_u: ... Overflow_u: ...
- 有符号加法 ($t0 = $t1 + $t2$)：
-
加速进位：
- 超前进位 (Carry Lookahead) 加法器：通过更复杂的逻辑电路并行计算进位，减少进位传播延迟，加速加法。最坏情况进位时间是加法器位长的 log₂ 函数。
2. 乘法
乘法比加减法复杂，结果位数可能翻倍。
2.1. 基本原理 (十进制回顾)
- 术语：被乘数 (Multiplicand), 乘数 (Multiplier), 积 (Product)。
- 方法：逐位取乘数的一位，乘以被乘数，得到部分积，然后将部分积左移并累加。
- 位数：n 位被乘数 × m 位乘数 ⇒ n+m 位积。
2.2. 二进制乘法 (顺序算法)
- 简化：乘数位为1，复制被乘数；乘数位为0，部分积为0。
-
**2.2.1. 第一版硬件
- 被乘数寄存器 (64位，初值在右半部分)、ALU (64位)、积寄存器 (64位，初值为0)、乘数寄存器 (32位)。
- 算法：重复32次
- 检查乘数寄存器最低位 (LSB)：
- 若为1：积 = 积 + 被乘数。
- 若为0：无操作。
- 被乘数寄存器左移1位。
- 乘数寄存器右移1位。
- 检查乘数寄存器最低位 (LSB)：
-
2.2.2. 改进版硬件
- 被乘数寄存器 (32位)、ALU (32位)、积寄存器 (64位，乘数初始放在其右半部分)。
- 算法优化：
- 检查积寄存器最低位 (原乘数位)：
- 若为1：积的高32位 = 积的高32位 + 被乘数。
- 积寄存器右移1位 (将部分积和乘数一起右移)。
- 检查积寄存器最低位 (原乘数位)：
- 这种方法更节省硬件，积寄存器右移代替了被乘数左移和乘数右移。
2.3. 有符号乘法
- 简单方法：
- 记录操作数的原始符号。
- 将操作数转为正数进行乘法运算。
- 根据原始符号确定积的符号（同号为正，异号为负）。
- 注意：移位操作需要考虑符号扩展（尽管上述算法通常先转为正数处理）。
2.4. 更快速的乘法 (并行乘法器)
- 思想：并行处理，使用多个加法器。
- 硬件结构：
- 为乘数的每一位（或多位）设置一个加法器。
- 32个被乘数（或0）根据乘数各位的值，通过一个加法器树（如 Wallace 树）相加。
- 延迟从 O(N) 降低到 O(log₂N) 次加法时间。
- 可使用进位保留加法器 (Carry-Save Adders, CSA) 进一步提速。
- 易于流水线化。
2.5. MIPS 中的乘法
- 专用寄存器：
Hi和Lo(各32位) 存储64位乘积。Hi存高32位，Lo存低32位。 - 指令：
mult rs, rt: 有符号乘法。结果存入Hi,Lo。multu rs, rt: 无符号乘法。结果存入Hi,Lo。
- 获取结果：
mflo rd: 将Lo寄存器的内容移至通用寄存器rd。mfhi rd: 将Hi寄存器的内容移至通用寄存器rd。
- 硬件/软件接口 (溢出检测)：
- MIPS
mult和multu指令本身不报告溢出。 - 软件需要检查
Hi寄存器来判断溢出：- 对于
multu：如果Hi非0，则发生溢出（结果超过32位无符号数范围）。 - 对于
mult：如果Hi不是Lo的符号扩展，则发生溢出（结果超过32位有符号数范围）。
- 对于
- MIPS
硬件/软件接口 (乘常数优化): 编译器常将乘以2的幂的乘法优化为左移指令 (sll)。乘以其他小常数可能优化为一系列移位和加法指令。
3. 除法
除法是乘法的逆操作，相对复杂且使用频率较低。需要处理除数为0的特殊情况。
3.1. 基本原理 (十进制回顾)
- 术语：被除数 (Dividend), 除数 (Divisor), 商 (Quotient), 余数 (Remainder)。
- 关系：被除数 = 商 × 除数 + 余数 (其中 |余数| < |除数|，且余数与被除数同号或为0)。
- 方法：尝试从被除数中减去尽可能多倍的除数。
3.2. 二进制除法 (顺序算法 - 恢复余数法)
- 简化：每一步减去除数或者减去0。
-
**3.2.1. 第一版硬件
- 除数寄存器 (64位，初值在左半部分)、ALU (64位)、余数寄存器 (64位，初值为被除数)、商寄存器 (32位，初值为0)。
- 算法：重复 N+1 次 (N为位数，如33次处理32位数据，多一步确保最后余数正确)
- 余数 = 余数 - 除数。
- 检查余数符号：
- 若余数 ≥ 0 (非负)：商寄存器左移1位，最低位设为1。
- 若余数 < 0 (负)：余数 = 余数 + 除数 (恢复原值)。商寄存器左移1位，最低位设为0。
- 除数寄存器右移1位。
-
3.2.2. 改进版硬件 "不恢复余数法"的硬件基础或优化版恢复余数法
- 除数寄存器 (32位)、ALU (32位)、余数寄存器 (64位，初值为被除数)、商寄存器 (32位，可视为余数寄存器右半部分)。
- 算法优化：余数寄存器左移1位，然后用余数的高位减去除数。
- 余数寄存器左移1位。
- 从余数寄存器的高半部分减去除数，结果存回余数高半部分。
- 若结果 ≥ 0：商的新位为1。
- 若结果 < 0：恢复余数高半部分（加上除数），商的新位为0。
- 这种设计与乘法器的改进版硬件相似，可以复用部分硬件。
3.3. 有符号除法
- 规则：
- 记录操作数原始符号。
- 将被除数和除数转为正数进行除法运算，得到商的绝对值和余数的绝对值。
- 商的符号：若被除数和除数符号相异，则商为负；否则为正。
- 余数的符号：余数的符号与被除数的符号相同。
- 公式必须满足：被除数 = 商 × 除数 + 余数。
- 示例：
- (+7) ÷ (+2) = 商 +3, 余数 +1 (7 = 3×2 + 1)
- (-7) ÷ (+2) = 商 -3, 余数 -1 (-7 = (-3)×2 + (-1))
- (+7) ÷ (-2) = 商 -3, 余数 +1 (7 = (-3)×(-2) + 1)
- (-7) ÷ (-2) = 商 +3, 余数 -1 (-7 = 3×(-2) + (-1))
精解: 保持 (余数符号 == 被除数符号) 可以避免
-(X/Y) != (-X)/Y这类问题，简化编程。
3.4. 更快速的除法
- SRT 除法 (Sweeney, Robertson, Tocher)：
- 每次迭代能产生多个商位（如2位或4位）。
- 使用查找表，根据余数和除数的高位部分来猜测商的若干位。
- 如果猜测错误，后续步骤会进行修正。
- 依赖查找表的正确性（Pentium FDIV bug即与此相关）。
- 不恢复余数法 (Non-Restoring Division)：
- 当余数为负时，不立即加回除数恢复。
- 下一步操作调整为将被除数（或部分余数）加上移位后的除数。
- (r - d) * 2 + d vs. (r2) - d (如果r-d<0, 则下一步用 (r-d)2+d，否则用 r*2-d )
- 每步一个时钟周期。
- 不执行除法 (Non-Performing Division)：
- 当余数为负时，不保存减法结果，进一步减少算术操作。
3.5. MIPS 中的除法
- 共用硬件：乘法和除法常共用
Hi和Lo寄存器。 - 结果存储：
Lo寄存器：存放32位商。Hi寄存器：存放32位余数。
- 指令：
div rs, rt: 有符号除法。Lo = rs / rt,Hi = rs % rt。divu rs, rt: 无符号除法。
- 获取结果：
mflo rd: 将商 (Lo) 移至通用寄存器rd。mfhi rd: 将余数 (Hi) 移至通用寄存器rd。
- 硬件/软件接口 (异常与错误)：
- MIPS 除法指令本身不处理溢出 (商过大无法用32位表示) 或除以零的情况。
- 软件必须在执行除法前检查除数是否为0，并可能需要检查商是否溢出。
4. MIPS 算术相关指令汇总 (部分回顾与补充)
| 指令类别 | 指令 | 示例 | 含义 | 备注 | |
|---|---|---|---|---|---|
| 加法 | add |
add $s1, $s2, $s3 |
$s1 = $s2 + $s3 |
检测溢出 | |
addi |
addi $s1, $s2, 100 |
$s1 = $s2 + 100 |
立即数加法, 检测溢出 | ||
addu |
addu $s1, $s2, $s3 |
$s1 = $s2 + $s3 |
不检测溢出 | ||
addiu |
addiu $s1, $s2, 100 |
$s1 = $s2 + 100 |
立即数加法, 不检测溢出, 立即数符号扩展 | ||
| 减法 | sub |
sub $s1, $s2, $s3 |
$s1 = $s2 - $s3 |
检测溢出 | |
subu |
subu $s1, $s2, $s3 |
$s1 = $s2 - $s3 |
不检测溢出 | ||
| 乘法 | mult |
mult $s2, $s3 |
Hi,Lo = $s2 * $s3 (有符号) |
64位积存入Hi,Lo | |
multu |
multu $s2, $s3 |
Hi,Lo = $s2 * $s3 (无符号) |
64位积存入Hi,Lo | ||
| 除法 | div |
div $s2, $s3 |
Lo=$s2/$s3, Hi=$s2%$s3 (有符号) |
商在Lo, 余数在Hi | |
divu |
divu $s2, $s3 |
Lo=$s2/$s3, Hi=$s2%$s3 (无符号) |
商在Lo, 余数在Hi | ||
| 数据移动(Hi/Lo) | mfhi |
mfhi $s1 |
$s1 = Hi |
从Hi移到通用寄存器 | |
mflo |
mflo $s1 |
$s1 = Lo |
从Lo移到通用寄存器 | ||
| 数据移动(协处理) | mfc0 |
mfc0 $s1, $epc |
$s1 = $epc |
从协处理器0 (系统控制) 寄存器移到通用寄存器 | |
| 逻辑运算 | and |
and $s1, $s2, $s3 |
$s1 = $s2 & $s3 |
按位与 | |
or |
or $s1, $s2, $s3 |
$s1 = $s2 | $s3 |
按位或 | ||
xor |
xor $s1, $s2, $s3 |
$s1 = $s2 ^ $s3 |
按位异或 (图中未列出, 但常见) | ||
nor |
nor $s1, $s2, $s3 |
$s1 = ~($s2 | $s3) |
按位或非 | ||
andi |
andi $s1, $s2, 100 |
$s1 = $s2 & 100 |
与立即数按位与 | ||
ori |
ori $s1, $s2, 100 |
$s1 = $s2 | 100 |
与立即数按位或 | ||
xori |
xori $s1, $s2, 100 |
$s1 = $s2 ^ 100 |
与立即数按位异或 (图中未列出) | ||
| 移位运算 | sll |
sll $s1, $s2, 10 |
$s1 = $s2 << 10 |
逻辑左移 | |
srl |
srl $s1, $s2, 10 |
$s1 = $s2 >> 10 (逻辑) |
逻辑右移 | ||
sra |
sra $s1, $s2, 10 |
$s1 = $s2 >> 10 (算术) |
算术右移 (图中未列出, 但常见) | ||
| 比较与跳转 | slt |
slt $s1, $s2, $s3 |
if($s2<$s3)$s1=1 else $s1=0 (有符号) |
小于则置位 | |
slti |
slti $s1, $s2, 100 |
if($s2<100)$s1=1 else $s1=0 (有符号) |
小于立即数则置位 | ||
sltu |
sltu $s1, $s2, $s3 |
if($s2<$s3)$s1=1 else $s1=0 (无符号) |
无符号小于则置位 | ||
sltiu |
sltiu $s1, $s2, 100 |
if($s2<100)$s1=1 else $s1=0 (无符号) |
无符号小于立即数则置位 | ||
beq |
beq $s1, $s2, Label |
if($s1==$s2) goto Label |
相等则跳转 (PC相对) | ||
bne |
bne $s1, $s2, Label |
if($s1!=$s2) goto Label |
不相等则跳转 (PC相对) | ||
| 无条件跳转 | j |
j Label |
goto Label |
跳转到目标地址 | |
jr |
jr $ra |
goto $ra |
跳转到寄存器地址 (用于返回、switch) | ||
jal |
jal Label |
$ra=PC+4; goto Label |
跳转并链接 (用于过程调用) | ||
| 数据加载 | lw |
lw $s1, 20($s2) |
$s1 = Memory[$s2+20] |
从内存取字 | |
lh |
lh $s1, 20($s2) |
$s1 = Memory[$s2+20] (符号扩展) |
从内存取半字 (图中未列, 但常见) | ||
lhu |
lhu $s1, 20($s2) |
$s1 = Memory[$s2+20] (零扩展) |
从内存取无符号半字 | ||
lb |
lb $s1, 20($s2) |
$s1 = Memory[$s2+20] (符号扩展) |
从内存取字节 (图中未列, 但常见) | ||
lbu |
lbu $s1, 20($s2) |
$s1 = Memory[$s2+20] (零扩展) |
从内存取无符号字节 | ||
lui |
lui $s1, 100 |
$s1 = 100 << 16 |
将立即数装入寄存器高16位, 低16位清零 | ||
| 数据存储 | sw |
sw $s1, 20($s2) |
Memory[$s2+20] = $s1 |
字存入内存 | |
sh |
sh $s1, 20($s2) |
Memory[$s2+20] = $s1 (低16位) |
半字存入内存 | ||
sb |
sb $s1, 20($s2) |
Memory[$s2+20] = $s1 (低8位) |
字节存入内存 | ||
| 原子操作 | ll |
ll $s1, 20($s2) |
$s1 = Memory[$s2+20] |
链接加载 (用于原子操作) | |
sc |
sc $s1, 20($s2) |
Memory[$s2+20]=$s1; $s1=(1 if ok else 0) |
条件存储 (用于原子操作) |