Frame of 42yeah

Site Defunct

注意！截止到 16/9/2019 ，这个博客已经被搬迁到了 这里 。以后我的东西都会发在那里。拜拜啦！
目录表
Booth 算法
保留余数的除法
加减交替除法

恶心的二进制算法

这几天在学这些玩意…… 然后最恶心的莫过于二进制的乘和二进制的除了！在这儿，为了防止我忘记，我主要说 Booth 乘法和二进制除法 - 保留余数和原码加减交替除法。

Booth 算法

我没打算解释的太过清楚，主要是说一下过程。因为网上相关的文献已经很多了，但是说的很通俗的却没几个。我今天就要用贼几把通俗的语言去解释他们！

先确认一些名词。

在 0011 * 0111 (3 * 7) 内， 0011 被称为 被乘数 ， 0111 被称为 乘数 。

开波！Booth 算法的大体结构如下：

  1. 初始化 P 为 0
  2. 在乘数的最右边加一个 0 (本来被乘数为 0111 ，现在变成了 01110)
  3. 看看乘数的倒数 1，2 位是啥：
    • 00 ? 啥也不做
    • 01 ? 把被乘数加去 P 那
    • 10 ? 把被乘数从 P 中减出来
    • 11 ? 啥也不做
  4. 把被乘数乘以 2 (也就是后面跟个 0)
  5. 看看乘数的倒数 2，3 位是啥，重复第 3 步 和第 4 步
  6. 当被乘数已经一直看过去看到没东西能再看的时候，P 就是乘法的结果了。

咱们来看看 3 * 7:

  1. P = 0
  2. 乘数 = 01110
  3. 最后两位为 01110
  4. P = P - 被乘数, P = 11.1101 (其中 11. 是符号位，用两位符号位是为的防溢出)
  5. 被乘数翻倍, 被乘数 = 00110
  6. 最后两位为 01110
  7. 啥也不做
  8. 被乘数翻倍，被乘数 = 001100
  9. 最后两位为 01110
  10. 啥也不做
  11. 被乘数翻倍，被乘数 = 0011000
  12. 最后两位为 01110
  13. P = P + 被乘数。注意！此时的 P 因为位数实际上和被乘数完全不相等，所以 P 是会顺延的！跟被乘数缺失的位数，P 会全部用符号位相应的数字补上，也就是说 P 现在是 11.1111101 。 11.1111101 + 00.0011000 = 00.0010101 。
  14. 被乘数翻倍（其实已经没必要了），被乘数 = 00110000
  15. 一看，咦，乘数被我走完了！所以答案就是 10101，也就是……
  16. 21! 惊不惊喜？

保留余数的除法

嗯…… 我们假设我们要计算 X / Y ，好吧

  1. 初始化 Q 为 “” (空)
  2. 把 X 取绝对值，把 Y 取绝对值，并且获得 Y 绝对值的负数的反码，我就直接叫 -Y 好了……譬如如果 Y 原本等于 = 3，那么到了这一步，Y = 00.0011 ， -Y = 11.1101，可以吧？
  3. X = X - Y
  4. X < 0 ? X = X + Y (其实就是恢复旧 X) ，并且 Q = Q + “0” 。否则 Q = Q + “1” 注意！这里要看情况加小数点
  5. X = X 左移一位（包括符号位，如果最高位为 1 的话那那个 1 就应该进入符号位的低位）
  6. 就这么循环 3, 4, 5 一直算，直到你算腻了或者 X == 0 为止。结果就是 Q，余数就是结果的小数点位.X 。

咱们来看看 3 / 7：

  1. Q = “”
  2. X = 00.0011, Y = 00.0111, -Y = 11.1001
  3. X = X - Y = 11.1100, 所以 X = X + Y = 00.0011, 且 Q = “0”
  4. X = X 左移一位，X = 00.0110
  5. X = X - Y = 11.1111, 所以 X = X + Y = 00.0110, Q = “0.0” (这个小数点自己看情况加吧……这里就很明显应该加了)
  6. X = X 左移一位 = 00.1100
  7. X = X - Y = 00.0101, Q = “0.01”
  8. X = X 左移一位 = 00.1010
  9. X = X - Y = 00.0011, Q = “0.011”
  10. X = X 左移一位 = 00.0110 发现了吗？这玩意儿死循环了。所以 Q 应该等于 0.011011011011…，所以与此同时，让我们来看看我们算到 Q = “0.011” 的时候的余数吧。
  11. 余数很容易看，我们可以发现， X 如今是 00.0110，因此余数 = 结果的小数点位.X = 0.0000110 (因为结果小数点后有 3 个数字(0.011) ，所以 X 前面补 3 个 0 就是他的余数了)

那么 0.011 是多少呢？0.375! 3/7 又等于多少呢？0.428571428571429 。有人可能问了，这俩玩意完全不想等呀！那是因为我们算的位太少了。假如我们算这个的话：

发现了吧？精度越高，咱算的越准。

加减交替除法

这玩意跟保留余数算法很像，我就不做例子了，你一定能理解的

  1. 初始化 Q 为 “” (空)
  2. 把 X 取绝对值，把 Y 取绝对值，并且获得 Y 绝对值的负数的反码，我就直接叫 -Y 好了……譬如如果 Y 原本等于 = 3，那么到了这一步，Y = 00.0011 ， -Y = 11.1101，可以吧？ 3.XX > 0 ? X = X - Y : X = X + Y
  3. X < 0 ? Q = Q + “0” : Q = Q + “1” 注意！这里要看情况加小数点
  4. 如果你算腻了或者 X == 0 ，退出。
  5. X = X 左移一位（包括符号位，如果最高位为 1 的话那那个 1 就应该进入符号位的低位）

为止。结果就是 Q，余数就是结果的小数点位.X 。注意注意注意！如果你腻了，那么在刚刚算好 Q 之后就不要再移位 X 了！也就是说，这里跟保留余数不一样的另外一个地方就是在最后一次计算时，X 不会移位！所以我把他们俩的顺序调换了，发现了吗？

例子我就不举了，就这样啦！祝大家玩得愉快……吧……

评论区