32位带符号不使用的64位数据类型乘法？ [英] 32 bit signed multiplication without using 64-bit data type?

问题描述

我想要做的32位有符号乘法，而无需使用64位数据类型。我的输入是在Q1.31（两者）格式。

I want to do 32-bit signed multiplication without using 64-bit data type. My inputs are in Q1.31 (both) format.

input1 = A32 (Ah Al) - higher, lower half's of A32

input2 = B32 (Bh Bl) - higher, lower half's of B32

结果应该是Q1.31格式，离开溢出情况

Result should be in Q1.31 format, leave the overflow case

我需要C code代表以上。请提供格式也解释。

I need C code for the above. Please provide the explanation with formats also.

推荐答案

签名Q1.31格式能够-1，几乎+1之间重新presenting操作数的全小数格式。比例因子为2 ³¹ 。这意味着，当每个Q1.31操作数被存储在32位带符号整数，我们可以通过计算符号整数的全双宽度的产品，那么右移31位移位结果产生的Q1.31产物。右移位是必须的，因为该产品包含比例因子的两倍，并且移位充当一个部门，删除比例因子的一个实例

Signed Q1.31 format is a fully fractional format capable of representing operands between -1 and almost +1. The scale factor is 2³¹. This means that when each Q1.31 operand is stored in a 32-bit signed integer, we can generate the Q1.31 product by computing the full double-width product of the signed integers, then right shifting the result by 31 bits. The right shift is necessary because the product includes the scale factor twice, and the shift acts as a division that removes one instance of the scale factor.

我们可以通过分别计算完整的产品的上表面和低32位计算两个32位整数的双宽度产物。低32位被平凡计算为两个输入的普通产品。为了计算的高32位，我们需要编写一个函数 mul32hi（）。为了避免使用更宽的类型（即，一个使用多于32位）在中间计算，我们需要的原始操作数分成两半，计算它们的部分积，然后适当地总结这些部分积

We can compute the double-width product of two 32-bit integers by separately computing the upper and lower 32 bits of the full product. The lower 32 bits are computed trivially as the ordinary product of the two inputs. To compute the upper 32 bits, we need to write a function mul32hi(). In order to avoid using a wider type (i.e. one using more than 32 bits) in intermediate computations, we need to split the original operands into halves, compute their partial products, and then sum these partial products appropriately.

需要注意的是不同的处理器提供了一个实现 mul32hi的功能的硬件指令（）。在这种情况下，一个会想，如果没有内在的存在，使用适当的内在，还是有点内嵌汇编code，而不是用在这里psented仿真code $ P $。

Note that various processors provide a hardware instruction that implements the functionality of mul32hi(). In this case one would want to use an appropriate intrinsic, or a bit of inline assembly code if no intrinsic exists, rather than use the emulation code presented here.

这有助于第一问题缩小到相应的无符号乘法运算， umul32hi（），然后通过2的补再$ P $的定义从中导出的符号结果psentation（假设下面的C code）：

It helps to reduce the problem first to the corresponding unsigned multiplication, umul32hi(), then derive the signed result from that via the definition of 2's complement representation (which is assumed in the following C code):

#include <stdint.h>

/* compute the upper 32 bits of the product of two unsigned 32-bit integers */
uint32_t umul32hi (uint32_t a, uint32_t b)
{
    /* split operands into halves */
    uint32_t al = (uint16_t)a;
    uint32_t ah = a >> 16;
    uint32_t bl = (uint16_t)b;
    uint32_t bh = b >> 16;
    /* compute partial products */
    uint32_t p0 = al * bl;
    uint32_t p1 = al * bh;
    uint32_t p2 = ah * bl;
    uint32_t p3 = ah * bh;
    /* sum partial products */
    uint32_t cy = ((p0 >> 16) + (uint16_t)p1 + (uint16_t)p2) >> 16;
    return p3 + (p2 >> 16) + (p1 >> 16) + cy;
}

/* compute the upper 32 bits of the product of two signed 32-bit integers */
int32_t mul32hi (int32_t a, int32_t b)
{
    return umul32hi (a, b) - ((a < 0) ? b : 0) - ((b < 0) ? a : 0);
}

/* compute the full 64-bit product of two signed 32-bit integers */
void mul32wide (int32_t a, int32_t b, int32_t *rhi, int32_t *rlo)
{
    *rlo = a * b;           /* bits <31:0> of the product a * b */
    *rhi = mul32hi (a, b);  /* bits <63:32> of the product a * b */
}

/* compute the product of two signed Q1.31 fixed-point numbers */    
int32_t mul_q_1_31 (int32_t a, int32_t b)
{
    int32_t hi, lo;
    mul32wide (a, b, &hi, &lo);
    /* Q1.31 is scaled by 2**31, trim out scale factor */
    return (int32_t)(((uint32_t)hi << 1) | ((uint32_t)lo >> 31));
}

我间preTED请求离开溢出案的意思是忽略溢出。因此，乘以-1（为0x80000000）-1（为0x80000000）与 mul_q_1_31（）将返回-1（为0x80000000）。

I interpreted the request to "leave the overflow case" to mean to ignore overflow. As a consequence, multiplying -1 (0x80000000) by -1 (0x80000000) with mul_q_1_31() will return -1 (0x80000000).

这篇关于32位带符号不使用的64位数据类型乘法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！