algorithm - 二进制长除法时的位运算

Question

这是来自 CLRS 中的数论章节。

我们被要求证明二进制“纸和铅笔”长除法 a/b 与结果 q 和提醒 r 做 O((1+lgq)lgb) 位操作。

我的看法是，我们对 q 中的每一位执行 b 减法 1。所以假设减去 b 执行 lgb 操作(b 中的每个位一个)，那么我们总共有 O(lgblgq ) 操作，这不是请求的。

如果你考虑到你做的第一个减法运算可能会得到一个 0 位(例如，将 100b 除以 11b)，那么，OK，你可以在 lgq 中加 1 来补偿对于这个减法。但是......减法本身也可以这样说 - 它可以采用 lgb 操作，也可以采用 lg(b)+1 操作，具体取决于数字(在以 100b 和 11b 为例，第二次减法将是 100b-11b，需要 3 次运算才能完成)。

因此，如果我们考虑这些情况，那么操作数应该是 O((1+lgb)(1+lgq))。

所以问题是，如何证明除法需要 O((1+lgq)lgb) 操作？

Answer 1

当你减去 100b-11b 时，你实际上可以忽略第一个数字中的前导位，因为你已经知道结果中对应的位将为 0。如果它是 1，你会在上一步中做减法而不是移位。所以减法总是恰好考虑 lg b 位。