Заглавная страница
Избранные статьи
Случайная статья
Познавательные статьи
Новые добавления
Обратная связь
FAQ
Написать работу

ТОП 10 на сайте

Приготовление дезинфицирующих растворов различной концентрации

Техника нижней прямой подачи мяча.

Франко-прусская война (причины и последствия)

Организация работы процедурного кабинета

Смысловое и механическое запоминание, их место и роль в усвоении знаний

Коммуникативные барьеры и пути их преодоления

Обработка изделий медицинского назначения многократного применения

Образцы текста публицистического стиля

Четыре типа изменения баланса

Задачи с ответами для Всероссийской олимпиады по праву

Мы поможем в написании ваших работ!

ЗНАЕТЕ ЛИ ВЫ?

Влияние общества на человека

Приготовление дезинфицирующих растворов различной концентрации

Практические работы по географии для 6 класса

Организация работы процедурного кабинета

Изменения в неживой природе осенью

Уборка процедурного кабинета

Сольфеджио. Все правила по сольфеджио

Балочные системы. Определение реакций опор и моментов защемления

Главная Избранные Случайная статья Познавательные Новые добавления Обратная связь FAQ Написать работу

Зсув. Алгоритми множення та дiлення

↑

⇐ ПредыдущаяСтр 8 из 9Следующая ⇒

6.1. Множення, дiлення двiйкових чисел на 2. Операцiї логiчного та арифметичного зсуву

Проаналiзуємо результат множення на 2 беззнакового двiйкового числа, представленого згiдно правила Горнера:

Хⁿ^-1*2ⁿ^-1 + Xⁿ^-2*2ⁿ^-2 +... + X¹*2¹ + X⁰*2⁰) * 2 =

Хⁿ^-1*2ⁿ + Xⁿ^-2*2ⁿ^-1 + Xⁿ^-3*2ⁿ^-2 +... + X⁰*2¹ + 0*2⁰.

Очевидно, що коефiцiєнти Хⁱ, що множились на 2ⁱ у вихiдному множнику, у добутку знаходяться бiля степенiв 2ⁱ⁺¹, тобто змiстились на 1 розряд влiво. Наприклад, представимо двiйковим форматом процедуру множення 86 (dec) * 2 = 172 (dec):

0 1 0 1 0 1 1 0 (bin) * 10 (bin) =

/ / / / / / / /

= 0 1 0 1 0 1 1 0 0 (bin).

Таким чином, для множення беззнакового двiйкового числа на 2 необхідно виконати двi операцiї:

– зсунути всі розряди числа вліво на один розряд,

– в молодший розряд добутку записати 0.

Аналогiчнi операцiї необхідно здiйснити для ділення двійкового числа на 2:

– зсунути всі розряди числа вправо на один розряд,

– в старший розряд частки записати 0.

Вiдмiтимо, що операція множення супроводжується збільшенням розрядності числа, а операція ділення – втратою молодших розрядів.

Процедури множення на 2 беззнакових та знакових чисел є повнiстю аналогiчними.

Приклад. Помножити на 2 беззнакове число 100 (дес.) та знакове число -100 (дес.):

01100100 - двiйкова форма вихідного числа 100 (дес.)

11001000 - зсунуте вліво число iз нулем в молодшому розрядi

(200 дес.)

1.10011100 - додатковий код вихідного числа -100 (дес.)

1.00111000 - зсунуте вліво число iз нулем в молодшому розрядi

(додатковий код числа -200 (дес.)).

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

Приклад. Поділити на 2 беззнакове число 100 (дес.) та знакове число -100 (дес.):

01100100 - двiйкова форма вихідного числа 100 (дес.)

00110010 - зсунуте вправо число iз нулем в старшому розрядi

(50 дес.).

1.10011100 - додатковий код вихідного числа -100 (дес.)

1.11001110 - зсунуте вправо число iз бiтом знаку в старшому

розрядi (додатковий код числа -50 (дес.)).

Зсув беззнакових чисел одержав назву логiчного зсуву. Зсув знакових чисел називається арифметичним зсувом. Вiдмiтимо, що логiчний та арифметичний зсуви влiво спiвпадають.

Необхідно звернути увагу на формування похибки при зсуві вправо непарних від’ємних чисел.

Якщо для парних від’ємних двійкових чисел вираз

(-2n) / 2 = - (2n/2) = - n

є вірним, то для непарних від’ємних двійкових чисел математична рівність

(-(2n-1)) / 2 = - ((2n-1)/2) = - n +1/2

не стверджується за рахунок втрати молодшого розряду при зсуві непарного числа вліво.

Наприклад, зсув вправо знакового двійкового числа 1.1010111 (-41 dec в додатковому коді) матиме результатом число 1.1101011 (-21 dec в додатковому коді). Натомість, якщо спочатку зсунути вправо додатнє двійкове число 0.0101001 (41 dec), а в одержаному результаті змінити знак, то одержимо число 1.1101100 (-20 dec в додатковому коді).

Таким чином, зсув додатнього непарного числа вправо із подальшою зміною знаку результату призводить до формування додатньої похибки:

(-(2n-1)) / 2 = - n +1/2.

Зміна знаку додатнього діленого, яке потім зсувається вправо, формує від’ємну похибку:

(-(2n-1)) / 2 = - n - 1/2.

6.2. Множення, дiлення двiйкових чисел на довiльнi константи

Операцiї зсуву є базовими i в процедурах множення двiйкових змiнних на цiлi константи, значення яких вiдрiзняються вiд цiлої степенi числа 2. Для цього константи представляються сумою цілих степенів двійки наступним чином:

3*X = 2*X + X;

5*X = 4*X + X;

6*X = 4*X +2*X;

...

Легко помiтити, що розкладення констант на цiлi степенi числа 2 при здiйсненнi процедури множення є не чим iншим, як схемою Горнера, що застосовується для представлення двiйкових чисел. Таким чином, множення двiйкової беззнакової змiнної на довiльну цiлу константу здiйснюється згiдно наступного алгоритму:

- константа-множник представляється у двiйковому виглядi, видi-

ляються розряди 2ⁱ iз одиничними бiтами,

- змiнна-множник зсувається влiво n-1 разiв, де n - кiлькiсть бiт у

двiйковому кодi константи-множника,

- зсунутi значення змiнної, що вiдповiдають одиничним бiтам

двiйкового коду константи, запам'ятовуються та додаються; попередньо перед додаванням всi зсунутi значення змiнної доцiльно представити числами однакової розрядностi шляхом записування необхiдної кiлькостi нульових бiтiв до старших розрядiв.

Вiдмiтимо, що результат множення чисел розрядності n1 та n2 має довжину n1 + n2.

Приклад. Помножити 8-розрядну беззнакову змiнну 10110100 (bin) на константу 92 (dec).

1. Представимо константу 92 (dec) у двiйковiй формi:

92 (dec) = 01011100 (bin).

2. Запишемо значення змiнної-множника 10110100, зсунутi влiво 2,3,4 та 6 разiв, згiдно iз наявнiстю одиничних бiтiв у 2, 3,4 та 6 розрядах константи 92 (dec):

1011010000- зсув змiнної-множника 10110100 влiво на 2 розряди,

10110100000 - зсув змiнної-множника 10110100 влiво на 3

розряди,

101101000000 – зсув змiнної-множника 10110100 влiво на 4

розряди,

10110100000000 - зсув змiнної-множника 10110100 влiво на 6

розрядiв.

3. Доповнимо нулями старшi розряди перших трьох зсувiв (змiнна-множник є беззнаковою, тому розширення розрядностi проводиться нулями) та додамо чотири зсунутi значення змiнної-множника:

10110100000000

100000010110000 (bin) = 16560 (dec)

4. Перевiримо результат десятковим множенням:

180 dec * 92 dec = 16560 dec.

Вiдмiтимо також, що результат множення 8-розрядної змiнної на 7-розрядну константу має 15 двiйкових розрядiв.

Множення на константи iз дробовою частиною здiйснюється окремо для цiлої та дробової частин константи iз наступним додаванням одержаних добуткiв.

Множення змiнної на дробову частину константи здiйснюється, в цiлому, способом, аналогiчним вищенаведеному:

– дробова константа-множник представляється у двiйковому виглядi, видiляються розряди iз одиничними бiтами,

– змiнна-множник зсувається вправо n - 1 разiв, де n - кiлькiсть бiт у двiйковому кодi дробової константи-множника; молодшi розряди змiнної, якi виходять за межi розрядної сiтки, як правило, не зберiгаються та, в подальшому, втрачаються,

– зсунутi значення змiнної, що вiдповiдають одиничним бiтам двiйкового коду константи, запам'ятовуються та додаються.

Вiдмiтимо, що результат множення змiнної на дробову константу не збiльшує розрядності змiнної.

Приклад. Помножити 8-розрядну беззнакову змiнну 10110100 bin (180 dec) на константу 0,63 dec.

1. Представимо константу 0,63 (dec) у двiйковiй формi довжиною 1 байт:

0,63

1,26

0,52

1,04

0,08

0,16

0,32

0,64

1,28, тобто 0,63 (dec) = 0,10100001 (bin).

2. Запишемо значення змiнної-множника 10110100, зсунутi вправо 1, 3 та 8 разiв, згiдно iз наявнiстю одиничних бiтiв у 1, 3 та 8 розрядах константи 0,63 (dec):

01011010 - зсув змiнної-множника 10110100 вправо на 1 розряд,

00010110 - зсув змiнної-множника 10110100 вправо на 3 розряди

iз втратою молодшого одиничного бiту,

00000000 - зсув змiнної-множника 10110100 влiво на 8 розрядiв.

Вiдмiтимо, що останнiй зсув змiнної на 8 розрядiв супроводжується повним її зникненням, тобто може бути проiгнорованим. Тому у вищенаведеному правилi зсув вправо рекомендується проводити n - 1 разiв.

3. Додамо два зсунутi значення змiнної-множника:

───────────────

01110000 (bin) = 112 (dec)

4. Перевiримо результат десятковим множенням:

180 dec * 0,63 dec = 113,4 dec.

Похибка -1,4 виникла за рахунок вiдкидання одиничних молодших бiтiв, що втрачаються при зсувi змiнної вправо за межi розрядної сiтки.

Дiлення на константи Х, якi не дорiвнюють цiлiй степенi числа 2, доцiльно перетворювати у множення на константи, що є оберненими до дiльника - 1/Х.

Приклад. Подiлити 8-розрядну беззнакову змiнну 10110100 bin (180 dec) на константу 11,34 dec.

1. Знайдемо константу Y, обернену до дiльника Х

Y = 1/X = 1 / 11,34 = 0.088 dec.

2. Подальша процедура множення змiнної 10110100 bin на константу 0.088 dec аналогiчна вищенаведенiй (перетворення константи у двiйкову форму, тощо).

6.3. Алгоритми множення двiйкових змiнних

Множення змiнної на константу вiдрiзняється вiд множення змiнної на змiнну тим, що для другого випадку невiдомим є склад обидвох множникiв. Розглянемо для прикладу множення двох восьмирозрядних двiйкових чисел 10101010 (назвемо його першим множником) та 11000001 (другий множник):

* 11000001

10101010 - додається

10101010 - не додається

10101010 - додається

Фактично перемноження зводиться до додавання трьох значень першого множника, зсунутих на 0, 6 та 7 розрядiв влiво:

*11000001

+10101010

+10101010.

Вiдмiтимо, що другий множник мiстить одиничнi бiти саме в нульовому, шостому та сьомому розрядах. Таким чином, процедуру множення двох двiйкових змiнних можна представити як n (n – кiлькiсть бiтів другого множника) послiдовних тактiв утворення добутку шляхом додавання або недодавання зсунутих значень першого множника в залежностi вiд стану бiтiв другого множника згiдно наступного алгоритму:

– в кожному з n тактiв вiдбувається зсув влiво першого множника на один розряд, виключення складає самий перший такт, в якому перший множник вважається зсунутим на 0 розрядiв, тобто залишається незсунутим,

– в кожному з n тактiв вiдбувається аналiз одного бiту другого множника, починаючи з молодшого (нульового) бiту,

– якщо в i-му тактi (i = 0,..., n-1) i-тий бiт другого множника до-

рiвнює одиницi, вiдповiдне i-те зсунуте значення першого множника додається до значення добутку, яке на початку множення повинно бути скинутим в нуль; додавання i-го зсунутого значення першого множника до добутку не вiдбуватиметься, якщо i-тий бiт другого множника дорiвнює 0.

Неважко помiтити, що запропонований алгоритм повнiстю вiдповiдає правилу Горнера, за яким розкладається другий множник:

X * Y = X * 2 ⁷ + X * 2 ⁶ + X * 2 ⁰,

де Y = 11000001 bin = 2 ⁷ + 2 ⁶ + 2 ⁰.

У вищенаведеному прикладі зсув першого множника відбувався влiво, а аналіз бітів другого множника починався iз молодших розрядiв.Той самий результат одержується у випадку зсуву першого множника вправо, якщо аналiз другого множника починати iз старших бітiв:

*11000001

+ 10101010

Зсунутий влiво або вправо перший множник називається частковим добутком (ЧД), а сума декiлькох зсунутих перших множників одержала назву суми часткових добуткiв (СЧД).

Процедура множення може бути реалізована і за рахунок зсуву суми часткових добутків вправо або влiво, також двома варіантами – шляхом аналiзу другого множника молодшими або старшими бітами вперед вiдповiдно. Нижче наведені по тактах всі чотири алгоритми множення двох беззнакових чисел: першого множника 10101010, що виступає як частковий добуток, та 11000001, біти якого аналізуються,починаючи з молодших або старших.

1. Алгоритм множення зсуванням влiво множника-часткового добутку аналiзом другого множника молодшими бітами вперед:

1 такт - 0000000010101010 - частковий добуток (ЧД) 1

+ 0000000000000000 - сума ЧД (СЧД) 0

0000000010101010 - СЧД 1

В першому тактi частковий добуток являє собою незсунуте значення першого множника. Додавання до суми часткових добуткiв вiдбувається, тому що молодший (нульовий) бiт другого множника дорiвнює одиницi.

2 такт - 0000000101010100 - ЧД2

0000000010101010 - СЧД1

додавання не відбувається, СЧД2 = СЧД1

В другому тактi частковий добуток являє собою зсунуте на один розряд влiво значення першого множника. Додавання до суми часткових добуткiв не вiдбувається, тому що перший бiт другого множника дорiвнює нулю.

3... 6 такти - додавання не відбувається,

СЧД6 = СЧД5 = СЧД4 = СЧД3 = СЧД2,

0001010101000000 - ЧД6

7 такт - 0010101010000000 - ЧД7

+ 0000000010101010 - СЧД6

0010101100101010 - СЧД7

8 такт - 0101010100000000 - ЧД8

+ 0010101100101010 - СЧД7

1000000000101010 - СЧД8

2. Алгоритм множення зсуванням вправо множника-часткового добутку аналiзом другого множника старшими бітами вперед:

1 такт - 0101010100000000 - ЧД1

+ 0000000000000000 - СЧД0

0101010100000000 - СЧД 1

В першому тактi частковий добуток являє собою значення першого множника, зсунуте на сiм розрядiв влiво. Додавання до суми часткових добуткiв вiдбувається, тому що старший (сьомий) бiт другого множника дорiвнює одиницi.

2 такт - 0010101010000000 - ЧД2

0101010100000000 - СЧД1

0111111110000000 - СЧД2

3 такт - 0001010101000000 - ЧД3

0111111110000000 - СЧД2

додавання не відбувається, СЧД3 = СЧД2

4... 7 такти - додавання не відбувається,

СЧД7 = СЧД6 = СЧД5 = СЧД4 = СЧД3,

0000000101010100 - ЧД7

8 такт - 0000000010101010 - ЧД8

+ 0111111110000000 - СЧД7

1000000000101010 - СЧД8

На рис. 9 наведені блок-схеми алгоритмів множення зсуванням влiво множника-часткового добутку B аналiзом другого множника A молодшими бітами вперед (9а), зсуванням вправо множника-часткового добутку B аналiзом другого множника A старшими бітами вперед (9б).

а) б)

Мал.9. Блок-схема алгоритму множення зсуванням влiво (а) та вправо (б) множника-часткового добутку B аналiзом другого множника A молодшими бітами (а) та старшими бітами (б) вперед

3. Алгоритм множення зсувом влiво суми часткових добутків аналiзом другого множника старшими бітами вперед:

1 такт - 0000000010101010 - ЧД1

+ 0000000000000000 - СЧД0

0000000010101010 - СЧД1

2 такт - 0000000010101010 - ЧД2

0000000101010100 - СЧД1*2

0000000111111110 - СЧД2

3... 7 такти - додавання не відбувається,

0011111111000000 - СЧД7 = СЧД2*64

8 такт - 0000000010101010 - ЧД8

+ 0111111110000000 - СЧД7*2

1000000000101010 - СЧД8

На мал. 10а наведена блок-схема алгоритму множення зсувом влiво суми SM часткових добутків аналiзом другого множника A старшими бітами вперед.

4. Алгоритм множення зсувом вправо суми часткових добутків аналiзом другого множника молодшими бітами вперед:

1 такт - 0101010100000000 - ЧД1

+ 0000000000000000 - СЧД0

0101010100000000 - СЧД 1

2 такт - 0101010100000000 - ЧД2

0010101010000000 - СЧД1/2

додавання не відбувається

3... 6 такти - додавання не відбувається,

0000001010101000 - СЧД6 = СЧД1/32

7 такт - 0101010100000000 - ЧД7

+ 0000000101010100 - СЧД6/2

0101011001010100 - СЧД7

8 такт - 0101010100000000 - ЧД8

+ 0010101100101010 - СЧД7/2

1000000000101010 - СЧД8

На мал. 10б наведена блок-схема алгоритму множення зсувом вправо суми SM часткових добутків аналiзом другого множника A молодшими бітами вперед.

а) б)

Мал.10. Блок-схема алгоритму множення зсуванням влiво (а) та вправо (б) суми SM часткових добутків аналiзом другого множника A старшими бітами (а) та молодшими бітами (б) вперед

Аналіз алгоритмів 1...4 показує, що найбільш простим є множення старшими байтами вперед зсуванням сум часткових добутків (алгоритм 3), в якому для зберігання часткового добутку достатньо байтового регістру. Алгоритми із зсуванням множника вимагають двобайтового регістру для зберігання часткових добутків та містять операцію додавання двобайтових чисел, що ускладнює програму множення.

Для виконання множення знакових чисел необхідно:

– визначити знак добутку (найбільш просто це робиться за допомогою логічної функції Виняткове ЧИ),

– утворити абсолютні значення множників та перемножити їх із використанням будь-якого алгоритму,

– утворити додатковий код результату.

Приклад. Потактно виконати множення беззнакових змiнних Х та У. Використати алгоритм множення зсувом множника Х (надалi – часткового добутку) у вiдповiдностi iз аналiзом змiнноi У молодшими бітами вперед. Шiстнадцятковi значення змiнних: X = A5B, У = 6D38.

Визначимо, що добуток 12-розрядноi змiнноi Х на 16-розрядну змiнну У матиме 28 розрядiв. Збiльшимо розряднiсть змiнноi Х до 28 нульовими бiтами i запишемо змiннi Х та У у двiйковiй формi:

Х = 0000 0000 0000 0000 1010 0101 1011

У = 0110 1101 0011 1000

Вiдмiтимо також, що в перших трьох тактах додавання не вiдбуватиметься - три молодшi бiти змiнноi У дорiвнюють нулю. Тому запишемо зразу стан четвертого такту, враховуючи, що змiнна Х вже буде тричi зсунута влiво:

Такт 4:

0000 0000 0000 0101 0010 1101 1000 - змiнна Х iз зсувом влiво

0000 0000 0000 0000 0000 0000 0000 - початкова сума часткових

добуткiв (CЧД0 = СЧД3)

0000 0000 0000 0101 0010 1101 1000 - СЧД пiсля четвертого

такту (СЧД4)

Такт 5:

0000 0000 0000 1010 0101 1011 0000 - змiнна Х iз зсувом влiво

0000 0000 0000 0101 0010 1101 1000 - СЧД4

0000 0000 0000 1111 1000 1000 1000 - СЧД5

Такт 6: 0000 0000 0001 0100 1011 0110 0000 - змiнна Х iз зсувом влiво

0000 0000 0000 1111 1000 1000 1000 - СЧД5

0000 0000 0010 0100 0011 1110 1000 - СЧД6

В тактах 7 та 8 додавання не вiдбуватиметься.

Такт 9: 0000 0000 1010 0101 1011 0000 0000 - змiнна Х iз зсувом влiво

0000 0000 0010 0100 0011 1110 1000 - СЧД8 = CЧД6

0000 0000 1100 1001 1110 1110 1000 - СЧД9

В тактi 10 додавання не вiдбуватиметься.

Такт 11:0000 0010 1001 0110 1100 0000 0000 -змiнна Х iз зсувом влiво

0000 0000 1100 1001 1110 1110 1000 - СЧД10 = СЧД9

0000 0001 0110 0000 1010 1110 1000 - СЧД11

В тактi 12 додавання не вiдбуватиметься.

Такт 13:0000 1010 0101 1011 0000 0000 0000 -змiнна Х iз зсувом влiво

0000 0001 0110 0000 1010 1110 1000 - СЧД12 = СЧД11

0000 1011 1011 1011 1010 1110 1000 - СЧД13

такт 14:0001 0100 1011 0110 0000 0000 0000 - змiнна Х iз зсувом влiво

0000 1011 1011 1011 1010 1110 1000 - СЧД13

0010 0000 0111 0001 1010 1110 1000 - СЧД14 - кiнцевий ре-

зультат.

Таким чином, Х * У = 2071AE8 hex.

6.4. Алгоритми дiлення двiйкових змiнних

Процедура ділення двійкових чисел реалізується циклічними діями, подібними до операції множення, за виключенням заміни додавання відніманням. Вiдмiтимо iнші характерні особливості операції ділення:

- розрядність частки дорівнює різниці між довжинами діленого та дільника,

- додатково до частки формується не дробова частина, а залишок,

- ділене, як правило, має подвійну довжину порівняно із дільником; якщо розрядності діленого та дільника однакові, то довжина діленого подвоюється за правилами розширення знаку,

- результатом ділення є переповнення, коли дільник дорівнює нулю;

- у випадку подвійної довжини діленого по відношенню до дільника переповнення виникає також, коли старша половина діленого є не меншою за дільник.

Наприклад, для беззнакового дiлення числа 1010 0011 на 1000 0011 дiлене повинно бути представлене як 0000 0000 1010 0011, а дiлення числа 1110 1110 1010 0011 на число 1100 0011 приведе до переповнення:

1110 1110 > 1100 0011.

Розглянемо детальнiше останню особливiсть операцiї дiлення. Виникнення переповнення в даному випадку означає не нескiнченно великий результат, а викликане утворенням результату, розряднiсть якого перевищує розряднiсть частки, тобто виходить за межi розрядноi сiтки результату.

Приклад ділення беззнакових чисел:

0000000011110000 ¦00000111

¦---------------- 11110000 = 240 (дес.),

- 00000111 ¦00100010 - частка 00000111 = 7 (дес.),

------------------- 00100010 = 34 (дес.),

00001000 240: 7 = 34 (2 - залишок)

-00000111

-------------

10 - залишок

Операцiя дiлення може бути представлена n-тактовою (n – кiлькiсть бiт дiльника) послiдовною процедурою утворення частки згiдно наступного алгоритму:

- перед початком процедури дiлене має подвоєну довжину порiвняно iз дiльником; дiльник змiщений максимально влiво (на n розрядiв),

- в кожному i-тому тактi дiльник одноразово зсувається вправо,

- якщо дiлене, а в подальшому, залишок вiд дiленого, менше дiльника, то до частки заноситься нульовий бiт, якщо дiлене, а в подальшому, залишок вiд дiленого, бiльше дiльника, то здiйснюється вiднiмання дiльника вiд частки, а до частки заноситься одиничний бiт.

1. Алгоритм ділення зсувом дільника вправо

Початковий стан: 0000000011110000 - ділене

0000011100000000 - дільник

1) 0000000011110000 - ділене

-0000001110000000 - дільник

віднімання не відбувається, до частки - 0,

2) 0000000011110000 - ділене

-0000000111000000

віднімання не відбувається, до частки - 0,

3) 0000000011110000 - ділене

-0000000011100000

0000000000010000 - залишок

до частки - 1,

4) 0000000000010000 - залишок

-0000000001110000

віднімання не відбувається, до частки - 0,

5) 0000000000010000 - залишок

-0000000000111000

віднімання не відбувається, до частки - 0,

6) 0000000000010000 - залишок

-0000000000011100

віднімання не відбувається, до частки - 0,

7) 0000000000010000 - залишок

-0000000000001110

0000000000000010 - залишок,

до частки - 1,

8) 0000000000000010 - залишок кiнцевий

-0000000000000111

віднімання не відбувається, до частки - 0.

Частка - 00100010, залишок - 00000010.

По аналогii зсуву вправо дiльника вiдносно дiленого, надалi - залишку вiд дiленого, частку можна визначити також згідно алгоритму ділення зсувом вліво діленого, надалі - залишку, при фiксованiй позицii дiльника:

- перед початком процедури дiлене також має подвоєну довжину порiвняно iз дiльником; дiльник змiщений максимально влiво (на n розрядiв),

- в кожному i-тому тактi дiлене, надалi - залишок вiд дiленого, одноразово зсувається влiво,

На мал.11 наведені блок-схеми алгоритмів ділення зсувом діленого A вліво (а) та дільника B вправо (б).

2. Алгоритм ділення зсувом вліво діленого, надалі- залишку.

Початковий стан: 0000000011110000 - ділене

0000011100000000 - дільник

1) 0000000111100000 - ділене

-0000011100000000 - дільник

віднімання не відбувається, до частки - 0,

2) 0000001111000000 - ділене

-0000011100000000 - дільник

віднімання не відбувається, до частки - 0,

а) б)

Мал.11. Блок-схема алгоритму ділення зсувом діленого A влiво (а) та зсувом дільника B вправо (б)

3) 0000011110000000 - ділене

-0000011100000000

0000000010000000 – залишок, до частки - 1,

4) 0000000100000000 - залишок

-0000011100000000

віднімання не відбувається, до частки - 0,

5) 0000001000000000 - залишок

-0000011100000000

віднімання не відбувається, до частки - 0,

6) 0000010000000000 - залишок

-0000011100000000

віднімання не відбувається, до частки - 0,

7) 0000100000000000 - залишок

-0000011100000000

0000000100000000 - залишок

до частки - 1,

8) 0000001000000000 - залишок кінцевий,

-0000011100000000

віднімання не відбувається, до частки - 0.

Частка - 00100010, залишок - 00000010.

Алгоритм ділення зсувом вліво діленого, надалі - залишку, дозволяє зберігати дільник в байтовому регістрі та провадити необхідні арифметичні операції з 8-розрядними операндами, що обумовило переважну реалізацію програм ділення на основі цього алгоритму.

Для ділення знакових двійкових чисел необхідно додатково виконати операції визначення знаку частки, модулів діленого та дільника, переведення частки в додатковий код.

Приклад. Потактно виконати дiлення беззнакових змiнних Х та У. Використати алгоритм дiлення зсувом вліво діленого Х, надалі - залишку. Шiстнадцятковi значення змiнних: X = 6E43, У = C4.

Початковий стан: 0110 1110 0100 0011 - ділене Х

1100 0100 - дільник У

такт 1: 1101 1100 1000 0110 - ділене зсунуте влiво

-1100 0100 - дільник

0001 1000 1000 0110 - залишок вiд дiленого, до частки - 1,

такт 2: 0011 0001 0000 1100 - залишок, зсунутий влiво

- 1100 0100 - дільник

вiднiмання не вiдбувається, до частки - 0.

Вiднiмання не вiдбувається також в тактi 3, в якому до частки занесеться нульовий бiт.

Такт 4: 1100 0100 0011 0000 - залишок, зсунутий влiво

- 1100 0100 - дільник

0000 0000 0011 0000 - залишок, до частки - 1.

В наступних чотирьох тактах вiднiмання не вiдбуватиметься, до частки занесуться чотири нульовi бiти. Останнiй залишок зсунеться чотири рази влiво, що буде його кiнцевою формою:

частка - 1001 0000; залишок - 0000 0011.

Перевiримо результат:

X дec = 28227; У дec = 196; X / У = 28227 / 196 = 144.02;

частка дес = 144; залишок дес = 3;

частка * У + залишок = 144 * 196 + 3 = 28224 + 3 = 28227.

6.5.Завдання до гл.6

1. Потактно виконати множення беззнакових змiнних Х та У.