2020-04-07
356
Операция умножения сводится к операциям сдвига и суммирования. Для начала рассмотрим несколько примеров умножения на 2 чисел в десятичном и двоичном виде:
1*2=2, 00000001В*00000010В=00000010В;
2*2=4, 00000010В*00000010В=00000100В;
3*2=6, 00000011В*00000010В=00000110В;
4*2=8, 00000100В*00000010В=00001000В;
5*2=10, 00000101В*00000010В=00001010В;
6*2=12, 00000110В*00000010В=00001100В;
7*2=14, 00000111В*00000010В=00001110В;
8*2=16, 00001000В*00000010В=00010000В.
Обратим внимание на то, что умножение на 2 в двоичном виде сводится к добавлению нуля справа к умножаемому, подобно умножению на 10 в десятичной системе. Или иными словами умножение на 2
сводится к сдвигу влево умножаемого на один двоичный разряд. Очевидно, что умножение на 2n сводится к сдвигу умножаемого влево на n двоичных разрядов. Например:
11*24=11*16=176, 00001011В*00010000В=10110000В=В0Н=0*160+11*161=176.
Для того чтобы понять, как умножать в двоичном виде на любое число, рассмотрим в общем виде умножение двух чисел, причем множитель представим в виде полной записи однобайтного двоичного числа:
A*B=A*(b0*20 + b1*21 + b2*22 + b3*23 + b4*24 + b5*25 + b6*26 + b7*27)=
|
|
|
A*b0*20+ A*b1*21+ A*b2*22+ A*b3*23+ A*b4*24+ A*b5*25+ A*b6*26+ A*b7*27=
7
= ∑ A*bi*2i,
i=0
где А - умножаемое, В - множитель, i – номер разряда, 2i – вес разряда, bi – двоичная цифра (0 или 1).
Таким образом, умножение числа А на число В можно свести к суммированию результатов умножения числа А на 2i. Окончательно умножение сводится к операциям сдвига умножаемого влево на i двоичных разрядов (при умножении числа А на 2i) и суммирования, причем если двоичная цифра bi множителя В равна 1, то соответствующее слагаемое А*bi*2i учитывается, а если bi=0, то соответствующее слагаемое А*bi*2i не учитывается.
Смысл одного из алгоритмов умножения поясним на примере умножения числа 37 (умножаемое) на 21 (множитель) (00100101В на 00010101В). Слева в столбик в двоичном виде запишем результаты сдвига умножаемого на 0,1…7 двоичных разрядов влево, а справа – двоичные цифры множителя при 20, 21…27. Затем просуммируем двоичные числа в левой части, напротив которых справа находятся единицы. В результате суммирования получим число 001100001001В (309Н=3*162+0*161+9*160= 777).
| + 00100101 | 1*20 суммируем |
| 001001010 | 0*21 не суммируем |
| + 0010010100 | 1*22 суммируем |
| 00100101000 | 0*23 не суммируем |
| + 001001010000 | 1*24 суммируем |
| 0010010100000 | 0*25 не суммируем |
| 00100101000000 | 0*26 не суммируем |
| 001001010000000 | 0*27 не суммируем |
| 001100001001 |
При реализации данного алгоритма необходимо: в цикле получать умножаемое, сдвинутое на соответствующее количество двоичных разрядов влево (0,1…7), и анализировать очередной бит множителя, причем, если бит равен 1, то прибавлять очередное сдвинутое умножаемое к накапливаемой частичной сумме, а если бит равен 0, то суммирование не производить. В итоге накопления частичных сумм получим результат.
|
|
|
В предыдущем варианте сдвиг умножаемого происходит относительно частичной суммы, т.е. частичная сумма как бы “стоит на месте”. Во втором варианте сдвигается частичная сумма относительно “стоящего на месте” умножаемого. Второй вариант труднее для понимания чем первый, но более эффективен при реализации, т.к. не требует выделения части ОЗУ для хранения текущего сдвинутого умножаемого. При этом необходимо: в цикле производить сдвиг частичной суммы и анализировать очередной бит множителя, начиная со старшего; если бит равен 1, то производится суммирование частичной суммы и умножаемого, а если бит равен 0, то суммирование не производится. Табл.4 поясняет смысл второго варианта алгоритма умножения на примере тех же чисел.
Таблица 4 - Поясняющий пример для второго варианта алгоритма
| № цикла | Умножаемое: 00100101 Частичная сумма (ЧС): 00000000 | Биты множителя |
| 1 | Сдвиг ЧС: 000000000 | 0*27 |
| 2 | Сдвиг ЧС: 0000000000 | 0*26 |
| 3 | Сдвиг ЧС: 00000000000 | 0*25 |
| 4 | Сдвиг ЧС: 000000000000 Прибавление к ЧС умножаемого: + 00100101 000000100101 | 1*24 |
| 5 | Сдвиг ЧС: 0000001001010 | 0*23 |
| 6 | Сдвиг ЧС: 00000010010100 Прибавление к ЧС умножаемого: + 00100101 00000010111001 | 1*22 |
| 7 | Сдвиг ЧС: 000000101110010 | 0*21 |
| 8 | Сдвиг ЧС: 0000001011100100 Прибавление к ЧС умножаемого: + 00100101 Окончательный результат: 0000001100001001 | 1*20 |
На рис.1 представлена блок-схема для второго варианта алгоритма умножения.
Да
Нет
|
Нет
Нет
Да
Рис.1 - Блок-схема алгоритма умножения
Ниже приводится пример простой программы по данной теме.
; (R6,R5)<--(R4)*(R3)
; (R6,R5) - результат и частичная сумма
; (R4) – умножаемое
; (R3) - множитель
;установка начальных значений
CLR A; очистка A
MOV R6,A; R6
MOV R5,A; R5
MOV R7,#08H; 8 циклов (по числу битов множителя)
MOV A,R3; загрузить множитель в A
;сдвиг частичной суммы влево (через C)
M0: CLR C; очистка C
XCH A,R5; сдвиг R5 влево
RLC A; через C без
XCH A,R5; потери (A)
XCH A,R6; сдвиг R6 влево
RLC A; через C без
XCH A,R6; потери (A)
;сдвиг множителя влево через C
RLC A; сдвиг множителя
JNC M1; при (C)=0 обход суммирования
;прибавление к частичной сумме умножаемого (R6,R5)<--(R6,R5)+(R4)
XCH A,R5; сложить младший байт частичной суммы и
ADD A,R4; умножаемое без потери (A),
XCH A,R5; результат в R5
XCH A,R6; сформировать старший байт частичной
ADDC A,#00H; суммы с учетом (C) без потери (A),
XCH A,R6; результат в R6
M1: DJNZ R7,M0; проверка конца цикла для 8 битов
END
Операция деления сводится к операциям сдвига и вычитания. Смысл алгоритма деления можно пояснить при выполнении деления “в столбик”.
Например, требуется разделить нацело 1246734 (делимое) на 13 (делитель). Формально надо поступать следующим образом. Сносим старший разряд делимого - 1 и пытаемся разделить нацело на делитель 13 – не делится (т.е. разница 1-13 отрицательная), поэтому в частное необходимо записать 0. Далее сносим следующий разряд делимого - 2, получаем число 12 и пытаемся разделить на 13 нацело – не делится (разница 12-13 отрицательная), поэтому в частное записываем 0. Затем сносим следующий разряд - 4, получаем число 124 и пытаемся разделить на 13 – получится 9 и 7 в остатке, поэтому в частное записываем 9. Теперь к полученному остатку 7 сносим следующий разряд делимого - 2, получаем число 75 и делим на 13 – получится 5 (записываем в частное) и 11 в остатке. К остатку 11 сносим 7, получаем число 117 и делим на 13 – получится 9 (записываем в частное) и 0 в остатке. К остатку 0 сносим 3, получаем число 3 и делим на 13 – не делится, поэтому в частное записываем 0. К 3 сносим 4 – получаем число 34 и делим на 13 – получится 2 (записываем в частное) и 8 в остатке. Таким образом, окончательный результат – частное: 95902, остаток: 8 (см. табл.5, левая часть).
|
|
|
Таблица 5 - Пример деления “в столбик” для десятичных и двоичных чисел
| Пример деления в десятичном виде | Пример деления в двоичном виде |
| 12 4 6 7 3 4 | 1 3 __________ 1 | 0 0 9 5 9 0 2 (8) 12 _1 24 1 1 7 _ 7 6 6 5 _ 1 1 7 1 1 7 0 3 _34 2 6 8 | 10 1 1 1 0 1 0 | 1 0 1 _________ 1 | 0 0 1 0 0 1 0 1 (1) 10 _1 01 1 0 1 0 1 1 1 _1 10 1 01 1 1 _1 10 1 0 1 1 |
Аналогично можно выполнить деление над числами в двоичном виде. Например, требуется разделить нацело 10111010В на 00000101В (т.е. ВАН на 05Н или 186 на 5). Сносим старший разряд делимого - 1В и делим 101В – не делится, поэтому в частное записываем 0В. Далее сносим следующий разряд делимого - 0В, получаем число 10В и делим на 101В – не делится, поэтому в частное записываем 0В. Затем сносим 1В, получаем число 101В и делим на 101В – получится 1В (в частное записываем 1В) и 0В в остатке. Теперь к полученному остатку 0В сносим 1В, получаем число 01В и делим на 101В – не делится, поэтому в частное записываем 0В. Сносим следующий разряд 1В, получаем число 11В и делим на 101В - не делится, поэтому в частное записываем 0В. Сносим следующий разряд 0В, получаем число 110В и делим на 101В - получится 1В (в частное записываем 1В) и 1В в остатке. К полученному остатку 1В сносим 1В, получаем число 11В и делим на 101В – не делится, поэтому в частное записываем 0В. Сносим 0В, получаем число 110В и делим на 101В - получится 1В (в частное записываем 1В) и 1В в остатке. Таким образом, окончательный результат – частное: 00100101В, остаток: 00000001В, т.е. ВАН / 05Н = 25Н (01Н) или 186 / 5 = 37 (1) (см. табл.3, правая часть).
|
|
|
На рис.2 представлена блок-схема алгоритма деления, в табл.6 – поясняющий пример для алгоритма деления.
Да
|
Нет
Да
Рис.2 - Блок-схема алгоритма деления
Таблица 6 – Поясняющий пример для алгоритма деления
| № цикла | Остаток 00000000В | С 0В | Делимое 10111010В | Делитель 00000101В | Частное 00000000В |
| 1 | _00000001 ← 00000101 отрицательн. 00000001 |  1
1
   0
| ← 01110100 |
   0000000 0
| |
| 2 | _00000010 ← 00000101 отрицательн. 00000010 | 0
1
0
| ← 11101000 |
0000000 0
| |
| 3 | _00000101 ← 00000101 00000000 | 1
0
1
| ← 11010000 |
0000000 1
| |
| 4 | _00000001 ← 00000101 отрицательн. 00000001 | 1
1
0
| ← 10100000 |
0000001 0
| |
| 5 | _00000011 ← 00000101 отрицательн. 00000011 | 1
1
0
| ← 01000000 |
0000010 0
| |
| 6 | _00000110 ← 00000101 00000001 | 0
0
1
| ← 10000000 |
0000100 1
| |
| 7 | _00000011 ← 00000101 отрицательн. 00000011 | 1
1
0
| ← 00000000 |
0001001 0
| |
| 8 | _00000110 ← 00000101 00000001 | 0
0
1
| ← 00000000 |
0010010 1
| |
| 00000001В | 00100101В |
Ниже приводится пример простой программы по данной теме.
; (R6.R5)<--(R4)/(R3)
; (R4) - делимое
; (R3) - делитель
; (R6) - частное
; (R5) - остаток (частичная разность)
;установка начальных значений
CLR A; очистка A
MOV R6,A; R6
MOV R5,A; R5
MOV R7,#08H; 8 циклов (по числу битов делимого)
;сдвиг делимого влево через C
D0: CLR C
MOV A,R4; старший бит
RLC A; делимого
MOV R4,A; попадает в C
;сдвиг остатка влево через C
MOV A,R5; бит из C попадает
RLC A; на место младшего
MOV R5,A; бита остатка
;вычисление остатка
;(R5)<--(R5)-(R3)
CLR C;
MOV A,R5;
CPL A;
ADD A,R3;
CPL A;
MOV R5,A;
;анализ остатка
JNC D1; обход восстановления остатка, если он >=0
;восстановление остатка
;(R5)<--(R5)+(R3)
MOV A,R5;
ADD A,R3;
MOV R5,A;
;запись бита частного
D1: CPL C; инверсия С
MOV A,R6; сдвиг частного
RLC A; влево
MOV R6,A; через C
;последний бит делимого?
DJNZ R7,D0; проверка конца цикла для 8 битов
END
Задания к практическому занятию №4:
1) для алгоритма умножение провести анализ со следующими данными: умножаемое 59; множитель 43;
2) для алгоритма деления провести анализ со следующими данными: делимое 234; делитель 23.
