1

我需要一个算法，它使用两个 32 位整数作为参数，并返回这些参数的乘积，拆分为另外两个 32 位整数：32 位最高位部分和 32 位最低位部分。

我会尝试：

uint32_t p1, p2; // globals to hold the result

void mult(uint32_t x, uint32_t y){
    uint64_t r = (x * y);

    p1 = r >> 32;
    p2 = r & 0xFFFFFFFF;

}

尽管它可以工作1，但不能保证机器中存在 64 位整数，编译器也不能保证它们的使用。

那么，最好的解决方法是什么？

注1：实际上，它不起作用，因为我的编译器不支持 64 位整数。

Obs：请避免使用boost.

4

4 回答 4

4

只需使用 16 位数字。

void multiply(uint32_t a, uint32_t b, uint32_t* h, uint32_t* l) {
    uint32_t const base = 0x10000;
    uint32_t al = a%base, ah = a/base, bl = b%base, bh = b/base;
    *l = al*bl;
    *h = ah*bh;
    uint32_t rlh = *l/base + al*bh;
    *h += rlh/base;
    rlh = rlh%base + ah*bl;
    *h += rlh/base;
    *l = (rlh%base)*base + *l%base;
}
于 2013-11-11T09:58:51.570 回答
1

正如我所评论的，您可以将每个数字视为长度为 32 的二进制字符串。

只需使用学校算术将这些数字相乘即可。您将获得一个 64 字符长的字符串。

然后只需对其进行分区。

如果您想要快速乘法，那么您可以查看Karatsuba 乘法算法。

于 2013-11-11T07:07:25.203 回答
1

这是Karatsubas-Algorithm的解释和实现。我已经下载了代码并运行了几次。它似乎做得很好。您可以根据需要修改代码。

于 2013-11-11T09:31:55.193 回答
0

如果unsigned long支持该类型，则应该可以：

void umult32(uint32 a, uint32 b, uint32* c, uint32* d)
{
  unsigned long long x = ((unsigned long long)a)* ((unsigned long long)b); //Thanks to @Толя
  *c = x&0xffffffff;
  *d = (x >> 32) & 0xffffffff;
}

从这里借来的逻辑。

于 2013-11-11T07:39:42.003 回答