РОЗПОДІЛ ЧИСЕЛ

Алгоритми розподілу двійкових чисел

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

Алгоритм ділення з відновленням залишку. Значення розрядів приватноговизначаються в результаті аналізу залишків, отриманих після вирахування дільника В на першому кроці алгоритму з старших розрядів діленого ДСТ, а на наступних кроках - з старших розрядів поточного залишку.

При позитивному і кульове значеннях залишку розряд приватного c k = 1. У цьому випадку для отримання наступного залишку поточний залишок зсувається на один розряд вліво і з нього віднімається дільник В.

При негативному значенні залишку поточний розряд приватного c k = 0. Виникає тупикова ситуація. Для виходу з неї повертається попередній залишок шляхом додавання дільника В до негативного залишку. Відновлений залишок зсувається на один розряд вліво і з нього віднімається дільник В. Операції відновлення та зсуву дозволяють збільшити попередній залишок в два рази і продовжити операцію ділення.

Приклад 2.30. Проілюструємо алгоритм з відновленням залишку для випадку п = 3, коли ділене А = 100011 (35 | 0), дільник В = 111 (710). Для вирахування дільника В скористаємося операцією алгебраїчного додавання в додатковому коді. Негативне значення дільника в додатковому коді (~ В) = 1001. Для виконання операції ділення введемо додаткові знакові розряди, які виділимо жирним шрифтом. Послідовність дій при розподілі представлена нижче, на рис. 2.17.

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

Мал. 2.17. Алгоритм ділення двійкових чисел з відновленням залишку

Приклад 2.31. При розподілі використовуються операції додавання і зсуву.

В результаті поділу отримано приватне С = 0101, яке, по суті справи, являє собою сукупність переносів, що виникають в результаті операцій додавання.

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

Приклад 2.32. Алгоритм без відновлення залишку для тих же значень подільника і діленого аналогічний наведеним прикладом 2.29 (рис. 2.18).

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

Мал. 2.18. Алгоритм ділення двійкових чисел без відновлення залишку

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

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