谁能解释一下这个算法的作用

Question

我遇到了这个算法，但无法弄清楚它的作用。作者说它优雅美丽，但我无法弄清楚它的作用。谁能帮忙？

multiply(n, m)
  sum = 0
  while true
     if n is odd then
        sum += m
     if n = 1 then
        return sum
     n = n / 2
     m = m * 2

Answer 1

基本上它做乘法。

它遍历设置的 n 位，并将 m 添加到变量总和中，一旦算法终止，变量总和将保存结果。在每一步中，m 更新为乘以 2。同样在每个步骤中，n 除以 2，这会导致长度为 1 的位向右移动。

给定算法利用的方程可以用以下表达式描述。

m * n = (n / 2) * (m * 2)        if n is even
m * n = (n / 2) * (m * 2) + m    if n is odd

循环导致 n 连续减少，同时将 m 添加到最终结果中，其中 n 是奇数。（即设置n的最右边位）

我认为这种算法对于大多数语言中的典型 int 数据类型并不有效，因为乘法可以通过对 CPU 的单个指令来完成。但是，检查位可能是作者可能认为的优雅。

使用设置为乘法的位（或数字）是许多算法中使用的一种想法，例如帮助实现数字的 O（logn） 时间幂运算，尤其是在大整数实现中。

简单地说，当找到 b 而不是将 a 乘以自身 （^b-1） 次时，您会发现 a 的幂，例如 a、a²、^{a 4}、a⁸,...通过预处理，当您想找到⁶ 时，您只需将⁴ 乘以²，两者都是在预处理期间找到的。例如，在此示例中，3 次乘法就足够了，而不是需要 5 次乘法的线性情况。