c++ - 使用 32 位无符号整数乘以 64 位数字的算法

Question

我有 64 位数字(63 位 + 符号位)，表示为二进制补码，存储在两个无符号 32 位整数中。

struct Long
{
    uint32 high;
    uint32 low;
}

如何仅使用 32 位数字来实现乘法算法，并检查结果是否适合 63 位？如果结果不合适，我想返回一个指示溢出的错误代码。

Answer 1

通常你需要 2*n 位来存储两个 n 位数字的乘积(最大结果是 (2^n)^2 = 2^(2*n))，所以我最好的想法是拆分数字分成四个 16 位的部分，将它们一一相乘并相加。总共 16 次乘法，但错误检查很简单。