两个数相乘的算法

Question

我们必须将两个数字 x 和 y 相乘，但我们不能使用 * 运算符。

一种简单的方法是将 x , y 相加或将 y, x 相加，这很简单并且是线性的。

第二种方法是选择任意数字(比如 x)并查看该数字中设置了哪些所有位，如果设置了第 i 个位，则执行此操作:

product +=y<<i//product is 0 initially and do this for all i.

显然对于 32 位数字，循环运行 32 次并且其时间复杂度是恒定的。

我的问题是，还有其他方法吗？记住我们不能使用 *。

Answer 1

假设两个数字都是无符号的(这或多或少等同于您的第二种方式)

p = 0
while x > 0
    while x is even
        x = x / 2    // a shift right operation
        y = y + y    // a shift left operation
    x = x - 1
    p = p + y

产品现在在 p 中。

要了解为什么这是正确的，请考虑不变量

product = p + x*y

它由算法中的所有循环维护。我们从 p = 0 开始，所以它在 x = 0 时开始和结束时有效，所以我们必须有 product = p。