使用 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屋！