移位运算

移位的意义

1. 举个例子： 机器用语:15相对于小数点左移两位 左移：绝对值扩大 右移：绝对值缩小 当某个十进制数相对于小数点左移n位相当于该数乘10的n次方，右移n位相当于该数除以10的n次方 计算机中的小数点位置是事先约定好的，因此二进制表示的机器数在相对于小数点左移/右移，实质上就是该数乘以/除以2的n次方
2. 在计算机中，移位与加减配合，能够实现乘除运算

算术移位的规则

对有符号数的移位称为算术移位

• 不论是正数还是负数，移位后其符号位均不变
• 算术移位不是移二进制位，而是对应真值的放大和缩小
  • 左移一位x2 右移一位x1/2
• 对于规则的解读
  • 对于正数，原码=反码=补码=真值，故移位后出现的空位均以0添之
  • 对于负数
    • 由于负数的原码数值部分与真值相同，故在移位时只要使得符号位不变，其空位均添0即可
    • 由于负数的反码各位除符号位外与负数的原码正好相反，故移位后所添的代码应与原码相反，全部添1
    • 由于分析负数的补码发现，当其由低位向高位找到第一个‘1’时，在此‘1’左边的各位均与反码相同，右边的各位均与对应的原码相同
      • 负数的补码左移---空位出现在低位---添补的代码与原码相同---添0
      • 负数的补码右移---空位出现在高位---添补的代码与反码相同---添1 总结一些规律：
• 补码算术右移相当于除以 2的n次方 向负无穷舍入
• 原码/反码算术右移相当于除以 2的n次方 向 0 舍入
• 左移丢位 不等于 右移补位 ⇒ 错误
• 右移丢位 不等于 左移补位 ⇒ 误差 本质上就是一个丢掉的位是否能通过反方向移位补回来！ ---右移丢的是低位的细节信息（影响精度），左移丢的是高位的有效数据（产生错误） 移位时丢掉的位，能不能通过 “反方向的移位操作” 给补回来。能补，结果就准；补不回来，要么错得彻底（左移丢位后右移补），要么有偏差（右移丢位后左移补）

算数移位的硬件实现

算数移位 vs 逻辑移位

算术移位：有符号数的移位 逻辑移位：无符号数的移位 逻辑移位的规则： 逻辑左移：高位移丢，低位添0 逻辑右移：低位移丢，高位添0

加减法运算

因减法运算可看作被减数加上一个减数的负值，故在此将机器中的减法和加法运算合在一起讨论

补码加减法

现代计算机中都采用补码作加减法运算

公式

补码加法：

$$\begin{align} 整数：[A]_{补}+[B]_{补}&=[A+B]_{补}(mod\quad2^{n+1})\\ 小数：[A]_{补}+[B]_{补}&=[A+B]_{补}(mod\quad2)\\ \end{align}$$

把符号位与数值位同等处理 补码减法：A-B=A+(-B)

$$\begin{align} 整数：[A-B]_{补}&=[A+(-B)]_{补}=[A]_{补}+[-B]_{补}(mod\quad2^{n+1})\\ 小数：[A-B]_{补}&=[A+(-B)]_{补}=[A]_{补}+[-B]_{补}(mod\quad2)\\ \end{align}$$

先求[-B]_{补}（由[B]补连同符号位在内，按位取反，末尾相加）后按照补码加法的规则进行运算 连同符号位一起相加，符号位产生的进位自然丢掉（mod的作用）

溢出（overflow）

运算结果超出结果数据类型的表示范围（超出机器字长的表示范围）

• 正溢：超过最大正数
• 负溢：超过最小负数

一位符号位判断溢出

• 参与加法操作的两个数符号相同，其结果的符号与原操作数的符号不同，即为溢出
• 最高位数值位向符号位进位C与符号位产生的进位Cf不同 当A与B符号相同时，符号位产生的进位始终等于原加数的符号（SA/SB） 举例： 异或结果为1---溢出（不同） 异或结果为0---无溢出

两位符号位判断溢出

变形补码/双符号位的补码：以4为模

思想：将符号位扩展为两位，信息量加大，判断是否有溢出以及结果的符号 若两个符号位不一致时表示溢出 结果符号： 00：结果为正 无溢出 01：结果正溢 10：结果负溢 11：结果为负，无溢出 不论是否产生溢出，高位符号位都是真正的符号位（代表运算结果应该有的符号位） 本质：

• 可以把双符号位的补码看作一个n+1位数值位的补码（将补码的有效位数从 n 位（单符号位时）扩展为 (n+1) 位）
• 双符号位补码的符号位相异时，看作n+1位数值位的补码则代表真绝对值超过2的n次方，即结果溢出 双符号位与进位判断的辩证统一

补码加减法的硬件配置（不考）

🔆定点乘法（必考）

原码乘法

分析笔算乘法

可见包含着被乘数A的多次左移以及4个位积的相加运算

若在计算机内模拟手工乘法，需要解决三个问题

• 符号问题（符号位的处理）
  • 定点原码乘法，符号位单独处理
  • 定点补码乘法，其符号位可直接参与运算
• 多项部分积相加，进位传递问题（多个数据相加难以实现）
  • 是采用阵列乘法电路实现
  • 将 n 位乘转换为 n 次累加和 n 次移位，这种乘法需分解为多步实现，依靠时序控制分步，称为时序控制乘法器
• 加法器的位数和寄存器位数相同（乘积的字长扩展了一倍，如何存放？）
  • 通过将不再累加的乘积低位右移，则加法器的位数无需扩充

加法器的位数只需匹配 “被乘数的位数（这里被乘数是 4 位）”，但每次累加的部分积要根据 “乘数的位权” 进行位置偏移（保证二进制位的权值对应

笔算乘法的改进

两数相乘的过程，可视为加法和移位两种运算

每次将一位乘数所对应的位积与原部分积相加并移位 设置寄存器： A：存放部分积累加和、乘积高位 B：存放被乘数 C：存放乘数、乘积低位 符号位单独计算 迭代步骤：判断乘数最低位 → 决定是否加被乘数 → 部分积和乘数同时右移

上述运算过程归纳：

• 乘法运算可用加法和移位实现，若 n = 4，加 4 次，移 4 次
• 由乘数的末位决定被乘数是否与原部分积相加，然后 → 1 位形成新的部分积，同时乘数 → 1 位（末位移丢），空出高位存放部分积的低位。（共同移位）
• 每次做加法时，被乘数仅仅与原部分积的高位相加，其低位被移至乘数所空出的高位位置

原码一位乘运算规则

递推公式： 特点：

• 绝对值计算
• 用移位的次数判断乘法是否结束（注：不要忘记最后一次移位）
• 逻辑移位（由于乘法的数值部分是两数绝对值相乘的结果）

硬件配置

X存放被乘数的原码，Q存放乘数的原码

控制流程

补码乘法

补码一位乘运算规则

校正法

• 被乘数x符号任意，乘数y符号为正 (y>0) 当乘数y为正时，不管被乘数x符号如何，都可按照原码乘法的规则进行运算

  $$[x·y]_补=[x]_补·[y]_补=[x]_补·y$$

• 被乘数x符号任意，乘数y符号为负 (y<0)

• 总结： 若乘数 y 为正，不管被乘数 x 符号，则有： [x · y]补 = [x]补 · [y]补 若乘数 y 为负，不管被乘数 x 符号，则先按原码乘法运算（加和移位按补码运算），结果再加一个校正量 −[x]补，即：[x · y]补 = [x]补 · [0.y1y2 . . . yn]补 − [x]补

🔆Booth算法

运算规则

将校正法的两种情况统一起来,此时乘数x和被乘数y符号均为任意 按补码校正法规则，其基本算法可用一个统一的规则表示： booth算法递推公式的推导： 特点：

• 乘数末位设置附加位yn+1，初值为0，yi-yi+1组成判断位，决定运算操作（加[x]_补/[-x]_补/0），再右移一位得到新的部分积
• 乘数取单符号位，符号位参加运算，以决定最后是否修正
• x 取双符号位，让最高符号位始终指示正确符号位（加的时候可能产生溢出）---被乘数
• 作n次循环，第n+1次，不移位 优势：当1比较多时加法少

硬件配置

控制流程

原码乘法 VS 补码乘法

定点除法

原码除法

分析笔算除法

x=-0.1011，y=0.1101，求x/y 思路一：将定点小数转换为定点整数 x/y=-0.1101（商符号心算求得） 余数0.00000111 思路二：直接就是定点小数相除 特点：

• 商符单独处理
• 心算上商---比较余数和除数的大小，确定商为“0”/“1”
• 余数不动低位补0减右移后的除数
• 上商位置不固定

改进形成机器除法

进一步理解： 计算机中实现原码除法运算时，将笔算除法规则向机器可执行的运算规则转化过程中遇到的问题及解决思路

原码除法的规则

约定补充：商的位数和操作数的位数相同/商的位数和被除数位数相同停止

原码除法中由于对余数的处理不同，可分为恢复余数法和不恢复余数法（加减交替法）

恢复余数法

特点：当余数为负时（被除数-余数不够减），需要加上除数将其恢复为原来的余数，上商0 系统分析流程：

总结： 以下式子表示左移一位（x2）后减y*： 上商n+1次，第一次上商在整数位（对小数除法，可以做溢出判断） 移位n次

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

根据上述恢复余数法总结出的规律，可认为是恢复余数法的一种改进算法 特别注意：是有时候加，有时候减，不是加一下减一下 上商n+1次，第一次上商用来判断是否溢出 逻辑左移n次，加/减法n+1次，用移位的次数可判断除法是否结束

补码除法（略讲，不太考）