定点数的运算

定点数的算术运算是计算机最基本的操作。现代计算机普遍采用补码进行加减运算，乘法和除法有多种实现方式。溢出判断是保证运算正确性的关键。

补码加法公式

[X + Y]补 = [X]补 + [Y]补 (mod 2ⁿ⁺¹)

直接将两个补码相加，符号位参与运算，舍弃最高位进位。

补码减法公式

[X - Y]补 = [X]补 + [-Y]补

关键操作：求 $[-Y]_补$ 的方法——$[Y]_补$ 连同符号位全部取反，末位加 1。

加法示例

X = +1011, Y = +0011 → X+Y = +1110
[X]补 = 0,1011
[Y]补 = 0,0011
       0,1011
     + 0,0011
    ----------
       0,1110  → +14 ✓（无溢出）

减法示例

X = +0111, Y = +1001 → X-Y = -0010
[X]补  = 0,0111
[Y]补  = 0,1001
[-Y]补 = 1,0111
        0,0111
      + 1,0111
     ----------
      1,1010 → 负数，取反加1得 -0010 = -2 ✓

原码一位乘法

• 符号位单独处理：异号为负
• 数值部分做无符号乘法
• 步骤：从乘数最低位开始，若为 1 则加被乘数，若为 0 则加 0，每次右移一位

算法（手算模拟）：
1. 初始化：A=0（部分积），B=被乘数，C=乘数
2. 检查C最低位：
   - 若为1：A = A + B
   - 若为0：A不变
3. A和C一起右移一位
4. 重复步骤2-3，共n次

补码一位乘法（Booth 算法）

• 符号位参与运算，结果直接为补码
• 无需单独处理符号
• 乘数末位增加附加位 $Yn+1 = 0$

Booth算法步骤：
1. 初始化：A=0，Yn+1=0
2. 检查(Yn, Yn+1)：
   - 00 或 11：只右移
   - 01：A = A + [X]补，然后右移
   - 10：A = A + [-X]补，然后右移
3. 重复n次，最后一次不移位

Booth 算法示例

X = -3 (1101), Y = -5 (1011)
[-X]补 = 0011

步骤：(A, Y, Yn+1)
初始：0000, 1011, 0
1. YnYn+1=10 → A=A+[-X]=0011 → 右移：0001, 1101, 1
2. YnYn+1=11 → 右移：0000, 1110, 1
3. YnYn+1=01 → A=A+[X]=1101 → 右移：1110, 1111, 0
4. YnYn+1=10 → A=A+[-X]=0001 → 不移位：0001, 1111

结果：0001111 = +15 → 补码：(-3)×(-5) = +15 ✓

原码恢复余数法

1. 符号位单独处理
2. |被除数| - |除数|，够减商1，不够减商0并恢复余数
3. 余数左移一位，重复步骤2
4. 商的符号 = 被除数符号 ⊕ 除数符号

原码加减交替法（不恢复余数法）

1. 够减：余数左移，减除数
2. 不够减：余数左移，加除数（代替恢复余数再减）
3. 最后一次不够减时，需恢复余数

补码除法（加减交替法）

• 符号位参与运算
• 被除数/余数与除数同号：做减法
• 被除数/余数与除数异号：做加法
• 商的符号自动确定

算术移位（保持符号位不变）

逻辑移位

• 左移：低位补 0
• 右移：高位补 0

循环移位

• 带进位位的循环移位
• 不带进位位的循环移位