Мы делаем 32-битное * 32-битное умножение, используя следующий алгоритм.
Допустим, мы хотим умножить a (32 бита) на b (32 бита), оба со знаком,
a = ah * 2^16 + al [ah — старшие 16 бит, al — младшие 16 бит]
b = bh * 2^16 + bl [bh — старшие 16 бит, bl — младшие 16 бит]
Мы эффективно делаем
Результат = (al * bl) + (((ah * bl) + (al * bh)) * 2^16) + ((ah * bh) * 2 ^ 32) ~~~
Мой вопрос,
Есть ли лучший способ сделать это?
В любом обычном компиляторе эмуляция 64-битных целых чисел на 32-битной платформе будет примерно такой же эффективной, как и самостоятельное выполнение многошаговой математики. Но это будет гораздо надежнее правильно.
При выполнении простых арифметических операций со значениями, достаточно большими для переполнения, даже самая хорошо настроенная математическая библиотека, которую я видел, просто использует int64.
Погуглите "умножение Карацубы".
OIh, а в своем коде измените константу 2^15 (она появляется дважды) на 2^16.
Ответ заключается в том, что нет лучшего способа сделать что-то, кроме использования смещения битов и масок вместо 2 ^ n. А именно:
a * 2^n <=> a << n
Во-вторых, ваши целые числа подписаны или не подписаны? Если они подписаны, это меняет дело.
В-третьих, я не уверен, что ваши 2 ^ 15 верны. Если он по крайней мере без знака, вы хотите сдвинуть биты на 16, а не на 15.
Наконец, вы должны остерегаться целочисленного переполнения в int младшего разряда. Если вы складываете числа в младшем разряде int, которые переполняют его емкость, вам необходимо правильно увеличить старший разряд int.
Вам нужно знать (указать), как должно храниться 64-битное значение - предположительно, это пара 32-битных значений, возможно, два элемента массива или два элемента структуры. Вам также необходимо учитывать, как информация о знаке будет храниться в результате.
Механически вы, вероятно, захотите преобразовать оба знаковых значения в беззнаковые, а затем выполнить разделение и повторную сборку в соответствии с линиями, которые вы показали, следя за тем, чтобы переносы из 32-битного значения младшего порядка правильно управлялись в 32-битном старшем порядке. стоимость.
В зависимости от ваших первоначальных дизайнерских решений вам также может понадобиться настроить представление знака результата и, возможно, даже всех остальных битов.
Аналогичные комментарии относятся к умножению двух 16-битных чисел без каких-либо 32-битных результатов, что когда-то было важно, но большинству людей не о чем беспокоиться.
