使用32位无符号整数将64位数字相乘的算法 [英] algorithm to multiply 64 bit numbers using 32 bit unsigned integers
问题描述
我有64位数字(63位+符号位),表示为二进制补码,存储在两个无符号的32位整数中.
I have 64 bit numbers (63 bits + sign bit), represented as two's complement numbers, stored in two unsigned 32 bit integers.
struct Long
{
uint32 high;
uint32 low;
}
我该如何仅使用32位数字来实现乘法算法,并检查结果是否适合63位,如果结果不合适,我想返回一个指示溢出的错误代码.
How can i implement a multiplication algorithm, using just 32 bit numbers, and check that the result fits in 63 bits, i want to return an error code indicating overflow if the result doesn't fit.
推荐答案
通常,您需要2 * n位来存储两个n位数字的乘积(最大结果是(2 ^ n)^ 2 = 2 ^(2 * n)),所以我最好的主意是将数字分成四个16位部分,将它们一一相乘,然后相加.总共有16个乘法,但是错误检查是微不足道的.
Generally you need 2*n bits to store the product of two n bit numbers (largest result is (2^n)^2 = 2^(2*n)), so my best idea is to split up the number into four 16-bit parts, multiply them one by one and add them together. 16 multiplications all in all, but error checking is trivial.
这篇关于使用32位无符号整数将64位数字相乘的算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!