32-битное дробное умножение с методом перекрестного умножения (без 64-битного промежуточного результата)

Это та же самая формула. Для N > 16 сдвиги просто означают, что вы выбрасываете целое 16-битное слово, которое было бы переполнено или потеряно. low*low >> N означает просто сдвиг N-16 бит в старшем слове 32-битного результата умножения и добавление к младшему слову результата. high * high ‹‹ N означает просто использовать младшее слово результата умножения, сдвинутое влево N-16, и добавить к старшему слову результата.

Есть несколько идей в игре.

Во-первых, умножение 2 более коротких целых чисел для получения более длинного произведения. Рассмотрим беззнаковое умножение 2 32-битных целых чисел на умножение их 16-битных «половинок», каждое из которых дает 32-битное произведение, а общее произведение 64-битное:

a * b = (a_hi * 2¹⁶ + a_lo) * (b_hi * 2¹⁶ + b_lo) =

a_hi * b_hi * 2³² + (a_hi * b_lo + a_lo * b_hi) * 2¹⁶ + a_lo * b_lo.

Теперь, если вам нужно знаковое умножение, вы можете построить его из беззнакового умножения (например, из приведенного выше).

Предположим, что a ‹ 0 и b >= 0, a *_signed b должно быть равно

2⁶⁴ - ((-a) *_unsigned b), где

-a = 2³² - a (потому что это дополнение до 2)

ИОВ,

a *_{подписано} b =

2⁶⁴ - ((2³² - a) *_{без знака} b) =

2⁶⁴ + (a *_unsigned b) - (b * 2³²), где 2⁶⁴ может быть отброшен, так как мы используем только 64 бита.

Точно таким же образом вы можете вычислить a *_signed b для a >= 0 и b ‹ 0 и должны получить симметричный результат:

(a *_unsigned b) - (a * 2³²)

Вы можете аналогичным образом показать, что для a ‹ 0 и b ‹ 0 знаковое умножение может быть построено поверх беззнакового умножения следующим образом:

(a *_unsigned b) - ((a + b) * 2³²)

Итак, вы сначала умножаете a и b как беззнаковые, затем, если a ‹ 0, вы вычитаете b из старших 32 битов произведения, а если b ‹ 0, вы вычитаете a из старших 32 битов произведения, готово.

Теперь, когда мы можем умножать 32-битные целые числа со знаком и получать 64-битные произведения со знаком, мы наконец можем обратиться к дробным числам.

Предположим теперь, что из этих 32 битов в a и b N бит используются для дробной части. Это означает, что если вы посмотрите на a и b как на простые целые числа, они будут в 2^N раз больше, чем они представляют на самом деле, например. 1.0 будет выглядеть как 2^N (или 1 ‹‹ N).

Итак, если вы умножите два таких целых числа, произведение будет в 2^N*2^N = 2^2*N раз больше, чем оно должен представлять, например 1,0 * 1,0 будет выглядеть как 2^2*N (или 1 ‹‹ (2*N)). IOW, простое целочисленное умножение удвоит количество дробных битов. Если вы хотите, чтобы в произведении было такое же количество дробных битов, как и в множимых, что вы делаете? Вы делите произведение на 2^N (или сдвигаете его арифметически на N позиций вправо). Простой.

Несколько слов предостережения, на всякий случай...

В C (и C++) вы не можете законно сдвинуть переменную влево или вправо на такое же или большее количество битов, содержащихся в переменной. Код скомпилируется, но не будет работать так, как вы ожидаете. Итак, если вы хотите сдвинуть 32-битную переменную, вы можете сдвинуть ее от 0 до 31 позиции влево или вправо (максимум 31, а не 32).

Если вы сдвинете целые числа со знаком влево, вы не сможете законно переполнить результат. Все знаковые переполнения приводят к неопределенному поведению. Итак, вы можете придерживаться неподписанного.

Сдвиг вправо отрицательных целых чисел со знаком зависит от реализации. Они могут выполнять либо арифметический сдвиг, либо логический сдвиг. Какой именно, зависит от компилятора. Итак, если вам нужен один из двух, вам нужно либо убедиться, что ваш компилятор просто поддерживает его напрямую, либо реализовать каким-то другим способом.