两个数相乘的算法

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

在某些体系结构上，可以使用一条指令在一个字中设置 first/last 位。

例如GCC __builtin_clz (unsigned int x) 其中 returns X 中前导 0 位的数量。

或者strings.h中有int ffs(int i)，其中returns字i中设置的第一个（最低有效）位的位置。

使用其中之一，您可以仅枚举一个字中的设置位。这可以减少所需的迭代次数。

#include <stdlib.h>
#include <stdio.h>
#include <strings.h>

int main(int argc, char** argv)
{
  if(argc >= 2) {
    int a = atoi(argv[1]);
    int b = atoi(argv[2]);
    printf("%i * %i = %i", a, b, a*b);
    int r = 0;
    while (a) {
      int i = ffs(a) - 1;
      a ^= 1<<i;
      r += b<<i;
    }
    printf(" = %i\n", r);
  }
}

使用此代码，乘法 1048576 * 123 = 128974848 将在单次迭代中完成，因为 1048576 = 0x100000 仅设置了一位。

Answer 2

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

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 然后。

Answer 3

不加乘法*

带整数的解决方案 1：

我假设你可以使用 +

做一个循环：x + x + .. + x（y 次）。或 y + ... + y（x 次）。

方案二：

分解一切，为每个数字0-9保留一个table的x*y，重现小学时的手工操作。

解决方案3：结合其他两个，最简单和健壮：

对于整数：以二进制形式进行

13 * 7 :

1101 * 111 = 1101 + 11010 + 110100 = 1011011 = 91

处理器就是这样工作的。没有+，只有二元运算(and,or,xor)

对于非整数：用整数管理 0

对于负数：同样的事情，管理 +/-

时间复杂度对于 32 位是常量：这无关紧要，因为一切都是常量。

一般时间复杂度：二元运算相当有效：

位数 = O(log n)

=> x*y => O(log x) * O(log y)

两个数相乘的算法

Algorithm for multiplying two numbers

algorithm

bits