两个数相乘的算法

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

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

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

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

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

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

最佳答案

假设两个数字都是无符号的，一个可以做(这或多或少相当于你的第二种方式)

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 那么。

关于两个数相乘的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34692115/