МНОЖЕННЯ ЧИСЕЛ

Алгоритми множення двійкових чисел

Розглянемо алгоритмічні особливості реалізації операції множення позитивних і-розрядних двійкових чисел А = а { а п _ 2 ... a k ... a i a 0 і В = Ь п _ { Ь п _ 2 ... b k .. .b x b Q, де А - множимое, В - множник. Окремі розряди а до і Ь до довічних чисел перемножуються за правилами, наведеними в табл. 2.10.

Таблиця 2.10

k

a k

> h

Арифметичне множення Pk = "k * Ь до

Логічне множення Рк ~ а Ь Л Ь до

Додавання за модулем 2 Рк = <4® Ь до

0

0

0

0

0

0

1

0

1

0

0

1

2

1

0

0

0

1

3

1

1

1

1

0

Слід зазначити, що операція арифметичного множення однорозрядних двійкових чисел тотожна операції логічного множення. Тому при її апаратної реалізації можна використовувати логічні елементи.

Представивши множник у вигляді розгорнутого двійкового числа

можна отримати такий вираз для твору двійкових чисел:

(2.18)

де - ke часткове твір.

З виразу (2.18) випливають два відомих правила множення: починаючи з молодших і зі старших розрядів Ь до множника В.

Приклад 2.23. Проілюструємо правила множення 3-розрядних двійкових чисел А = 111 і В = 101, починаючи з молодших і старших розрядів множника (рис. 2.12).

Правила множення

Мал. 2.12. Правила множення

Множення двійкового числа Ь до ■ А на 2 до рівносильно його зсуву вліво на до розрядів. Як випливає з виразу (2.18), при множенні з молодшого розряду множника Ь 0 показники ступеня k коефіцієнта 2 до збільшуються, послідовно приймаючи значення до = 0, 1, 2, ..., п - 1. Це означає, що кожне наступне часткове твір зсувається на один розряд вліво. При множенні зі старшого розряду множника Ь п, спостерігається зворотна картина: ступеня до коефіцієнта 2 до зменшуються, послідовно приймаючи значення до = п - 1, я-2, ..., 2, 1, 0. Тому кожне наступне часткове твір зсувається на один розряд вправо.

Скориставшись методом Горнера, перетворимо вираз (2.18) до виду (2.19):

(2.19)

Згідно (2.19) множення починається зі старшого розряду b n [ = Ь Т Після цього множенням на 21 реалізується зрушення вліво (тг-1) -го часткового твори, а потім кожна наступна сума часткових творів (за винятком останньої) також зсувається вліво на один розряд.

Приклад 2.24. Множення 3-розрядних двійкових чисел А = 111 і В = 101 (рис. 2.13) за алгоритмом, описуваного формулою (2.19), що має для п = 3 такий вигляд:

де b 2 = 1, Ь х = 0, b 0 = 1 (рис. 2.13).

Множення за алгоритмом (2.19) з лівим зрушенням проміжних результатів

Мал. 2.13. Множення за алгоритмом (2.19) з лівим зрушенням проміжних результатів

Можлива інша форма представлення твору (2.18) за схемою Горнера

(2.20)

З (2.20) випливає, що множення починається з молодшого розряду Ь 0 множника В. Після цього множенням на 2 1 провадиться зрушення часткового твори Ь 0 ■ А вправо на один заряд, а потім кожна наступна сума часткових творів (за винятком останньої) зсувається також вправо на один розряд.

Приклад 2.25. Множення 3-розрядних двійкових чисел А = 111 і В = 101 але алгоритму, описуваного формулою (2.20), що має для п = 3 такий вигляд:

де (рис. 2.14).

Множення за алгоритмом (2.20) з правим зрушенням проміжних результатів

Мал. 2.14. Множення за алгоритмом (2.20) з правим зрушенням проміжних результатів

При множенні цілих позитивних "розрядних двійкових чисел кількість розрядів твори не перевищує 2га. У тому випадку, коли множимое А і множник В можуть мати різні знаки, виникає необхідність визначення знака твори. Для цього над знаковими розрядами співмножників виконується логічна операція додавання по модулю два або неравнозначности (див. табл. 2.10):

(2.21)

де р 2п , а п , видання п - значення знакових розрядів твори Р і сомножителей Лі В; ® - позначення логічної операції неравнозначности.

Якщо множимое А і множник В мають різні знаки, то результат операції неравнозначности дорівнює одиниці, а якщо - однакові знаки, то результат дорівнює нулю. Тому, якщо А і В мають:

  • • різні знаки, то p 2n = а п ® b n = 1 Ф 0 = 0 © 1 = 1, що відповідає негативному знаку твори Р;
  • • однакові знаки, то p 2n = a n ® b n = 1 ® 1 = 0 © 0 = 0, що відповідає позитивному знаку твори Р.

При відомому знаку твори визначається його абсолютне значення перемножением модулів співмножників (без урахування їх знаків).

 
< Попер   ЗМІСТ   Наст >