32-битное умножение без использования 64-битного типа данных?

Ответ 1

Подписанный формат Q1.31 - это полностью дробный формат, способный представлять операнды между -1 и почти +1. Масштабный коэффициент равен 2 ³¹. Это означает, что, когда каждый операнд Q1.31 хранится в 32-битовом значении целого числа, мы можем сгенерировать продукт Q1.31, вычислив полное произведение двойной ширины знаковых целых чисел, а затем переведем результат на 31 бит. Правый сдвиг необходим, потому что продукт включает в себя масштабный коэффициент дважды, а сдвиг действует как деление, которое удаляет один экземпляр масштабного коэффициента.

Мы можем вычислить произведение двойной ширины двух 32-битных целых чисел, отдельно вычисляя верхний и нижний 32 бита полного продукта. Нижние 32 бита вычисляются тривиально как обычный продукт двух входов. Чтобы вычислить верхние 32 бита, нам нужно написать функцию mul32hi(). Чтобы избежать использования более широкого типа (т.е. Использующего более 32 бит) в промежуточных вычислениях, нам нужно разбить исходные операнды на половинки, вычислить их частичные продукты и затем соответствующим образом суммировать эти частичные продукты.

Обратите внимание, что различные процессоры предоставляют аппаратную инструкцию, которая реализует функциональные возможности mul32hi(). В этом случае вы хотели бы использовать соответствующий внутренний код или бит встроенного ассемблерного кода, если он не существует, а не использовать приведенный здесь код эмуляции.

Это помогает сначала свести проблему к соответствующему беззнаковому умножению, umul32hi(), а затем вывести полученный из него результат с помощью определения 2 дополнения дополнения (которое предполагается в следующем C-коде):

#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));
}

Я интерпретировал запрос "оставить случай переполнения" означающим игнорировать переполнение. Как следствие, умножение -1 (0x80000000) на -1 (0x80000000) с помощью mul_q_1_31() будет возвращать -1 (0x80000000).

Ответ 2

Следующий сайт намерен предложить 32-битную реализацию библиотеки ANSI-C для работы с Q-номерами в целом: http://www.ti.com/tool/sprc542

Я не пробовал это и не могу ручаться за то, что он будет или не будет делать для вас, но на этом сайте есть ссылка, где вы можете запросить исходный код.