算法使用32位无符号整数乘64位数

我有64位数（63位+符号位），用二进制补码表示，存储在两个无符号的32位整数中。算法使用32位无符号整数乘64位数

struct Long 
{ 
    uint32 high; 
    uint32 low; 
}

我如何能实现乘法算法，只使用32位数字，并检查结果在63位配合，我想返回指示溢出如果结果不符合的错误代码。

2011-09-27 José

大多数编译器都有一个很长的64位的类型，应该使用乘法。 – Pubby

我需要算法，假设没有64位支持。 –

维基百科描述了计算机使用的算法：http://en.wikipedia.org/wiki/Multiplication_algorithm –

通常你需要2 * n位来存储两个n位数的乘积（最大结果是（2^n）^ 2 = 2 ^（2 * n）），所以我最好的想法是将编号分为四个16位部分，将它们逐个相乘并将它们相加。总共16次乘法，但错误检查是微不足道的。

2011-09-27 13:35:31 thiton

错误检查可能是微不足道的，但我怀疑维护进位会有点复杂。 –

应该可行。乘法的低部分必须检查溢出并进入高部分，但无论如何这是无法避免的。 – thiton

确保将变量更改为正值并进行无符号乘法运算，然后在完成时将其更改为签名。 – Pubby

查看GNU MP library中的'longlong.h'头文件。我相信这个头文件的版本也在GNU C源代码中。宏：smul_ppmm根据无符号双字产品定义：umul_ppmm。这使您可以使用32x32 => 64位乘法来实现64x64 => 128位乘法。

2011-09-28 12:39:25

回答