鲁达 乘法的应用千千万
• 浮点乘法和定点乘法的原理是相同的
• 早期处理器通过软件迭代
• 使用加法和移位
• 现代处理器都实现硬件乘法器
• 提高程序性能
硬件模拟软件的“移位-加”操作
• 两个N位数相乘,结果为2N位
• 使用3组触发器,锁存住乘数、被乘数和结果
• 乘数每次算术右移一位,被乘数每次算术左移一位
如果参与运算的是补码?
• 先判断结果符号位
• 将补码转为原码进行运算
• 补上符号位,转换回补码
• 太麻烦,不如自行推导补码乘法算法
• 问题: 已知[X] 补 和[Y] 补 ,求[X*Y] 补 .
• [X] 补 +[Y] 补 =[X+Y] 补 (方括号内为普通加法,方括号外为补码加法)
• 但[X] 补 *[Y] 补 !=[X*Y] 补
• 若[Y ] 补 =y 31 y 30 ......y 1 y 0 ,
• 则Y= -y 31 *2 31 + y 30 *2 30 +......+y 1 *2 1 +y 0 *2 0
已知[X] 补 和[Y] 补 ,求[X*Y] 补
[X*Y] 补 = [X*( -y 31 *2 31 +y 30 *2 30 +......+y 1 *2 1 +y 0 *2 0 )] 补
= [-X*y 31 *2 31 +X*y 30 *2 30 +......+X*y 1 *2 1 +X*y 0 *2 0 ] 补
= [-X*y 31 *2 31 ] 补 +[X*y 30 *2 30 ] 补 +......+[X*y 1 *2 1 ] 补 +[X*y 0 *2 0 ] 补
= - [X] 补 *(y 31 *2 31 ) +[X] 补 * (y 30 *2 30 ) +......+[X] 补 * (y 1 *2 1 ) +[X] 补 * (y 0 *2 0 ) ???
方括号内为普通加法,方括号外为补码加减(符号位扩充到64位再加)
定理:[X*2 k ] 补 =[X] 补 *2 k
• 运算时,根据y i 取0或1,进行操作
• 结果先置为0, [X] 补 扩展为64位
• 当i = 0 ... 30,若y i 为1,将[X] 补 左移i位,补码加法到结果
• 当i = 31,若y i 为1,将[X] 补 左移i位,补码减法到结果
• 和原码“移位-加”算法类似(除了最高位)
补码运算注意
• 符号位扩充到8位,结果保留8位
• 补码减法:按位取反加1(-11010000 = 00101111+1)
将之前的迭代加乘法器稍微修改,就可以实现补码乘法