32-битное умножение
Автор: xrnd | Рубрика: Исходники | 31-07-2010
Эта статья посвящена разбору примера умножения 32-битных чисел на 16-битном процессоре. Как вы наверно знаете, команда MUL в 16-битном режиме позволяет умножать максимум 16-битные значения, поэтому для умножения 32-битных чисел необходим специальный алгоритм.
Умножать большие числа приходится по частям, а затем складывать эти промежуточные результаты. Чтобы всё стало понятно я напишу небольшую формулу. Допустим, нам надо умножить два 32-битных числа a и b. В результате должно получиться 64-битное число c. Обозначим как a1 — младшее слово a, a2 — старшее слово a, b1 — младшее слово b, b2 — старшее слово b. Тогда получается:
a = (a2<<16) + a1
b = (b2<<16) + b1
Символы <<16 обозначают сдвиг влево на 16 бит. По сути это то же самое, что умножить на 65536.
c = a x b = ((a2<<16) + a1) x ((b2<<16) + b2) =
= (a1 x b1) + ((a2 x b1)<<16) + ((a1 x b2)<<16) + ((a2 x b2)<<32)
Алгоритм очень напоминает способ умножения в столбик. Графически можно изобразить следующим образом:
