Деление двоичных беззнаковых чисел в компьютерных системах - Компьютерная арифметика
Деление мантисс чисел в форме с фиксированной запятой выполняется над абсолютными величинами операндов, представленными, чаще всего, прямым кодом.
Подобно умножению, деление в компьютерных системах реализуется как многошаговый процесс выполнения операций суммирования, сдвига и других элементарных операций.
В отличие от умножения этот процесс имеет итеративный характер, так как результат деления в большинстве случаев не может быть точно представлен числом конечной длины.
Как правило, формальным признаком окончания операции деления принимается количество сдвигов: при достижении числа сдвигов, равного количеству разрядов в частном, операция деления завершается.
Обозначим X - делимое, Y - делитель, а Z - частное. Тогда:
. (4.20)
Пусть (X), (Y) и (Z) являются беззнаковыми числами.
Операция деления характеризуется также дополнительным результатом (R) - остатком.
В практической реализации выделяют два типа операции деления:
- - первый тип это когда делимое, делитель и частное имеют одну и ту же длину (s); - второй тип это когда делимое имеет длину (2s) - удвоенную по сравнению с делителем и частным. Рассмотрим случай 1.
, . (4.21)
, . (4.22)
, . (4.23)
, . (4.24)
. (4.25)
Для того, чтобы деление было корректным, т. е. чтобы частное не превысило разрядную сетку, необходимо обеспечить выполнение условия:
. (4.26)
Или
. (4.27)
В противном случае будет иметь место переполнение разрядной сетки.
Переполнение исключено, если делимое и делитель имеют одинаковую длину. Как особый случай переполнения рассматривают попытку деления на нуль.
По существу, деление сводится к последовательности вычитаний делителя вначале из делимого, а затем из остатков.
Цифра ( ) частного определяется следующим образом: если текущий остаток () больше или равен делителю, цифра частного равна (1), если меньше, то цифра частного равна (0).
При этом операция сравнения реализуется посредством операции вычитания.
Так как частное можно определить только со старших разрядов, существует два варианта деления представленных на рис. 4.9:
- - с неподвижным делимым (частичным остатком) и сдвигаемым вправо делителем; - с неподвижным делителем и сдвигаемым влево делимым (частичным остатком).
В зависимости от способа обработки отрицательного частичного остатка, различают два алгоритма деления:
- - алгоритм №1, с восстановлением остатка; - алгоритм №2 без восстановления остатка.
Деление с восстановлением остатка заключается в следующем, если на очередном шаге получен положительный остаток, то в очередную цифру частного записывается (1), а остаток становится "предыдущим" для следующего шага.
Данный шаг на этом заканчивается.
Рисунок 4.9 - Схемы деления двоичных беззнаковых чисел
Если текущий остаток отрицателен, то в очередную цифру частного записывается (0), а к остатку прибавляется делитель для восстановления предыдущего, сдвинутого влево остатка, который становится "предыдущим" для следующего шага.
Таким образом, отрицательный остаток аннулируется, поскольку он выполнил свою функцию сигнализатора о соотношении модулей остатка и делителя и больше не нужен.
Алгоритм №1. Деление целых двоичных беззнаковых чисел методом с восстановлением остатка.
- 1. Исходное значение частного (Z) полагается равным (0). (Сч. Т) присваивается значение (s). Исходное значение частичного остатка (R0) полагается равным (s) старшим разрядам делимого. 2. Выполняется пробное вычитание делителя (Y) из исходного значения частичного остатка - (ЧО). Положительная разность указывает на то, что частное превысит (s-разрядную сетку), и будет выполнено прерывание. Если же результат вычитания отрицательный, то деление можно выполнять. 3. Восстанавливается исходное значение (ЧО) прибавлением делителя к полученному отрицательному остатку. 4. (ЧО) удваивается путем сдвига на один разряд влево. 5. Из (ЧО) вычитается делитель и анализируется знак результата вычитания: если остаток положительный, то очередная цифра частного равна (1), иначе - (0). 6. Частное сдвигается влево с занесением очередной полученной цифры частного в освободившийся младший разряд. (Сч. Т) уменьшается на (1). 7. Если полученный остаток отрицателен, то восстанавливается предыдущий положительный остаток прибавлением делителя к отрицательному остатку. 8. (Пп. 4-7) последовательно выполняются до получения всех цифр частного, пока (Сч. Т) не станет равным (0). 9. Если последний остаток от деления отрицателен, то восстанавливается предыдущий положительный остаток, который будет окончательным остатком от деления.
Недостатки:
- - нерегулярность выполнения операций, что усложняет устройство управления (для получения одной цифры частного необходимо выполнять либо одно вычитание и сдвиг, либо одно вычитание, одно сложение и сдвиг); - относительно малая скорость деления, т. к. в среднем половина шагов будет содержать операцию восстановления остатка.
T=(s+l)(l,5t++tC)-tC.
Например: необходимо разделить два беззнаковых числа (21:7=3).
Для удобства возьмем длину разрядной сетки равную четырем битам, а именно:
Х = 21 - делимое;
Y = 7 - делитель;
Z = 3 - частное.
Если (Z) и (Y) равняется четырем битам, то как было отмечено выше (X) должно быть восьмиразрядным значением, т. е длина разрядной сетки делимого в два раза больше делителя и частного.
Алгоритм деления приведен в табл. 4.3.
Таблица 4.3 - Алгоритм деление целых двоичных беззнаковых чисел методом с восстановлением остатка.
Регистр (В) Делимое X |
Регистр (С) Делитель Y |
Регистр (А) Частное Z |
Счетчик тактов Сч. Т) | |||||||||||||
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
4 |
1 |
0 |
0 |
1 | |||||||||||||
1 |
0 |
1 |
0 |
<0 | ||||||||||||
0 |
1 |
1 |
1 | |||||||||||||
1 |
0 |
0 |
0 |
1 | ||||||||||||
0 |
0 |
1 |
0 |
1 |
0 |
1 | ||||||||||
1 |
0 |
0 |
1 | |||||||||||||
1 |
0 |
1 |
1 |
<0 |
3 | |||||||||||
0 |
1 |
1 |
1 | |||||||||||||
1 |
0 |
0 |
1 |
0 | ||||||||||||
0 |
1 |
0 |
1 |
0 |
1 | |||||||||||
1 |
0 |
0 |
1 | |||||||||||||
1 |
1 |
1 |
0 |
<0 |
2 | |||||||||||
0 |
1 |
1 |
1 | |||||||||||||
1 |
0 |
1 |
0 |
1 | ||||||||||||
1 |
0 |
1 |
0 |
1 | ||||||||||||
1 |
0 |
0 |
1 | |||||||||||||
1 |
0 |
0 |
1 |
1 |
>0 |
1 | ||||||||||
0 |
1 |
1 |
1 | |||||||||||||
1 |
0 |
0 |
1 | |||||||||||||
1 |
0 |
0 |
0 |
0 |
>0 |
0 | ||||||||||
СТОП |
Деления без восстановления остатка заключается в следующем, исходной предпосылкой для использования данного метода является желание избавиться от процедуры восстановления остатка.
Благодаря этому, длительность деления можно существенно уменьшить по сравнению с вышеприведенной оценкой (за счет исключения "лишней" операции восстановления остатка), используя алгоритм деления без восстановления остатка.
Проанализируем шаг деления, при котором текущий остаток оказался отрицательным. Обозначим:
- - () - предыдущий остаток; - () - текущий; - () - последующий.
Пусть:
. (4.28)
При этом, в соответствии с правилом деления, должны выполняться три действия:
- восстановление предыдущего (сдвинутого влево) остатка:
. (4.29)
- сдвиг восстановленного остатка влево на один разряд:
. (4.30)
- вычитание модуля делителя из полученной кодовой комбинации:
. (4.31)
Таким образом, требуется перейти от текущего остатка:
. (4.32)
К последующему виду (4.31), избавившись от операции восстановления.
Если первым действием является сдвиг отрицательного остатка () влево, то:
. (4.33)
Правая часть (4.32) отличается от требуемого вида величиной |Y|.
Поэтому вторым действием будет корректировка (4.33):
. (4.34)
Сформулируем общее правило.
Чтобы определить цифру частного в некотором разряде, необходимо сдвинуть логически () влево на один разряд, а затем прибавить к нему код делителя, которому приписывается знак, противоположный знаку предыдущего остатка; если полученный () положительный, то в частном проставляется (1), если же отрицательный, - то (0).
Алгоритм №2. Деления целых двоичных чисел методом без восстановления остатка
- 1-2. Аналогично п. п. 1, 2 предыдущего. 3. Аналогично п. 4. 4. Из частичного остатка вычитается делитель, если остаток положительный, или к частичному остатку прибавляется делитель, если остаток отрицательный. 5. Частное сдвигается; в младший разряд заносится очередная цифра частного (1 -- при положительном остатке, 0 -- при отрицательном); 6. П. п. 3-5 последовательно выполняются для получения всех цифр частного, пока (Сч. Т) не станет равен (0). 7. Аналогично последнему пункту предыдущего алгоритма.
Реализация данного алгоритма не требует никаких дополнительных аппаратурных затрат. .
Например: необходимо разделить два беззнаковых числа (21:7=3).
Для удобства возьмем длину разрядной сетки равную четырем битам, а именно:
Х = 21 - делимое;
Y = 7 - делитель;
Z = 3 - частное.
Если (Z) и (Y) равняется четырем битам, то как было отмечено выше (X) должно быть восьмиразрядным значением, т. е длина разрядной сетки делимого в два раза больше делителя и частного.
Алгоритм деления приведен в табл. 4.4.
Таблица 4.4 - Алгоритм деление целых двоичных беззнаковых чисел методом без восстановлением остатка.
Регистр (В) Делимое X |
Регистр (С) Делитель Y |
Регистр (А) Частное Z |
Счетчик тактов (Сч. Т) | |||||||||||||
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
4 |
1 |
0 |
0 |
1 | |||||||||||||
1 |
0 |
1 |
0 |
<0 | ||||||||||||
0 |
1 |
0 |
0 |
1 |
0 |
1 | ||||||||||
0 |
1 |
1 |
1 | |||||||||||||
1 |
0 |
1 |
1 |
<0 |
3 | |||||||||||
0 |
1 |
1 |
1 |
0 |
1 | |||||||||||
0 |
1 |
1 |
1 | |||||||||||||
1 |
1 |
1 |
0 |
<0 |
2 | |||||||||||
1 |
1 |
0 |
0 |
1 | ||||||||||||
0 |
1 |
1 |
1 | |||||||||||||
1 |
0 |
0 |
1 |
1 |
>0 |
1 | ||||||||||
0 |
1 |
1 |
1 | |||||||||||||
1 |
0 |
0 |
1 | |||||||||||||
1 |
0 |
0 |
0 |
0 |
>0 |
0 | ||||||||||
СТОП |
Например: необходимо разделить два беззнаковых числа (21:7=3).
Для удобства возьмем длину разрядной сетки равную четырем битам, а именно:
Х = 20 - делимое;
Y = 7 - делитель;
Z = 2 - частное;
R = 6 - остаток.
Если (Z) и (Y) равняется четырем битам, то как было отмечено выше (X) должно быть восьмиразрядным значением, т. е длина разрядной сетки делимого в два раза больше делителя и частного.
Как было отмечено выше последний частичный остаток должен быть больше нуля.
Если последний частичный остаток меньше нуля, его необходимо восстанавливать путем прибавления к нему делителя.
Алгоритм деления приведен в табл. 4.5.
Таблица 4.5 - Алгоритм деление целых двоичных беззнаковых чисел методом без восстановлением остатка.
Регистр (В) Делимое X |
Регистр (С) Делитель Y |
Регистр (А) Частное Z |
Счетчик тактов (Сч. Т) | |||||||||||||
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
4 |
1 |
0 |
0 |
1 | |||||||||||||
1 |
0 |
1 |
0 |
<0 | ||||||||||||
0 |
1 |
0 |
0 |
1 |
0 |
0 | ||||||||||
0 |
1 |
1 |
1 | |||||||||||||
1 |
0 |
1 |
1 |
<0 |
3 | |||||||||||
0 |
1 |
1 |
1 |
0 |
0 | |||||||||||
0 |
1 |
1 |
1 | |||||||||||||
1 |
1 |
1 |
0 |
<0 |
2 | |||||||||||
1 |
1 |
0 |
0 |
0 | ||||||||||||
0 |
1 |
1 |
1 | |||||||||||||
1 |
0 |
0 |
1 |
1 |
>0 |
1 | ||||||||||
0 |
1 |
1 |
0 | |||||||||||||
1 |
0 |
0 |
1 | |||||||||||||
1 |
1 |
1 |
1 |
<0 |
0 | |||||||||||
СТОП | ||||||||||||||||
Счетчик тактов равняется нулю деление окончено, но последний частичный остаток получился равен меньше нуля, поэтому необходимо выполнить коррекцию, путем прибавления к последнему частичному остатку делитель. | ||||||||||||||||
0 |
1 |
1 |
1 |
- коррекция | ||||||||||||
1 |
0 |
1 |
1 |
0 |
>0 - истинный остаток. |
Похожие статьи
-
Умножение двоичных беззнаковых чисел в компьютерных системах - Компьютерная арифметика
Пусть сомножителями X и Y являются s-битные целые числа без знака: Где - (Х) - множимое, (Y) - множитель, (Z) - произведение. Тогда: Z = X - Y. (4.2)...
-
Он позволяет заменить операцию вычитания на операцию сложения, чем упрощает архитектуру компьютерной системы. Дополнительный код является дополнением...
-
Контроль переполнения в компьютерных системах - Компьютерная арифметика
Возможно только при сложении чисел с одинаковыми знаками, когда для представления результата недостаточно отведенного количество разрядов (требуется...
-
Представление числовых данных в компьютерных системах - Компьютерная арифметика
Компьютерный арифметика счисление двоичный Система вещественных чисел, используемая в ручных расчетах, предполагается бесконечной и непрерывной, т. е....
-
Операции сдвига в компьютерных системах - Компьютерная арифметика
Является одной из самых распространенных в компьютерной арифметике. В частности, она используется при выполнении умножения или деления двоичных чисел....
-
При сложении и вычитании знаковых двоичных чисел операция вычитания заменяется операцией сложения в дополнительном коде. Докажем, что результат...
-
Операция сложения и вычитания, двоичных беззнаковых чисел в компьютерных системах Компьютерная система выполняет сложение и вычитание операндов по...
-
Системы счисления - Компьютерная арифметика
Как было отмечено в первой главе Система счисления - совокупность приемов и правил для установления однозначного соответствия между любым числом и его...
-
Перевод чисел из одной позиционной системы счисления в другую - Компьютерная арифметика
Задача перевода чисел из одной позиционной системы счисления в другую является одной из главных в компьютерной арифметике. Ее можно сформулировать...
-
Классификация систем счисления - Компьютерная арифметика
В настоящее время различают Позиционные И Непозиционные системы счисления. Классификация систем счисления приведена на рис. 2.1. Рисунок 2.1 --...
-
Базовые понятия и определения компьютерной арифметики - Компьютерная арифметика
Компьютерная арифметика - совокупность принципов и форм представления числовой информации, методов и алгоритмов выполнения арифметических операций и...
-
ДД-код Константа16 ДД-код Константа16 1111 1111 FF 0000 0000 00 0011 0101 35 1111 0100 F4 0101 0111 57 1001 1010 9A 1000 1101 8D 0000 0111 07 1000 0000...
-
10 2 4 8 16 0 0 0 0 0 1 1 1 1 1 2 10 2 2 2 3 11 3 3 3 4 100 10 4 4 5 101 11 5 5 6 110 12 6 6 7 111 13 7 7 8 1000 20 10 8 9 1001 21 11 9 10 1010 22 12 A...
-
Арифметические флажки - Компьютерная арифметика
Флажки являются признаками, представляющими общую характеристику результата выполнения операции. Наиболее широко применяются следующие флажки: - Флажок...
-
Системы счисления. Представление данных в ЭВМ - Основы программирования
В современном мире для записи числовой информации используют позиционные системы счисления, в которых числа записываются с помощью ограниченного...
-
Собственные числа и собственные векторы матрицы Предположим, что среди бесконечного множества одномерных пространств R1 найдутся такие, которые будут...
-
Рассмотрим замкнутую сеть массового обслуживания с разнотипными заявками, которая является вероятностной моделью обслуживания заявок в УП "Проектный...
-
Блок OVRDSEL принимает до четырех входов (от первичных блоков) и выбирает один с наибольшим или наименьшим значением. Графически это выглядит следующим...
-
Программный интерфейс для базы данных я разрабатывал в объектно-ориентрованной среде Delphi, с помощью Embarcadero RAD Studio. Конструктор форм Delphi в...
-
Типы данных и команды SQL - Разработка информационной системы "Магазин компьютерных товаров"
Microsoft SQL Server поддерживает большинство типов данных SQL 2003. Также SQL Server поддерживает дополнительные типы данных, используемые для...
-
При обслуживании пассажиров в кассах предварительной продажи билетов в качестве показателей, характеризующих систему обслуживания, используют максимально...
-
Машинная арифметика с плавающей точкой - Представление и хранение информациии в ЭВМ
Число с плавающей точкой: X=±Mx-S±px Здесь: M - мантисса; S - порядок. 0.314 101 0.0314 102 Машинные числа. Машинными называются числа, допускающие...
-
Системы счисления - Основы информатики
1.1 Переведите число 154,23510 из десятичной системы счисления в двоичную, восьмеричную, шестнадцатеричную системы счисления Решение: При переводе из...
-
Арифметические операции в двоичной системе счисления Умножение в двоичной системе счисления = поразрядные сдвиги + суммирование Основные форматы хранения...
-
Объект ориентированный класс программирование Цель Работы - изучить методику создания одномерных динамических символьных массивов при помощи...
-
ВВЕДЕНИЕ, АНАЛИЗ ЗАДАЧИ - Теория вычислительных процессов
Ассемблер программа верификация Написать на языке ассемблер программу, реализующую вычитание двух целых упакованных 128- разрядных чисел. Описать...
-
В вычислительной технике понятие безопасности является весьма широким. Оно подразумевает и надежность работы компьютера, и сохранность ценных данных, и...
-
Операционная система - Программное обеспечение информационных компьютерных систем
Операционная система - это комплекс взаимосвязанных системных программ, назначение которого - организовать взаимодействие пользователя с компьютером и...
-
Программное обеспечение и его виды - Программное обеспечение информационных компьютерных систем
Windows программный компьютер операционный Программное обеспечение (software) - это набор команд, управляющих работой компьютера. Без программного...
-
Операционная система Windows - Программное обеспечение информационных компьютерных систем
Само название Windows, на русском языке означает "Окна" и имеет в нашем языке синонимы Виндовс, Вундоуз и другие производные полученные после перевода....
-
Расчет потребного числа отдельных устройств автовокзала Расчет числа билетных касс Число билетных касс должно обеспечивать полное и своевременное...
-
ЗАКЛЮЧЕНИЕ, СПИСОК ЛИТЕРАТУРЫ - Разработка информационной системы "Магазин компьютерных товаров"
В процессе работы я расширил свои знания касательно работы с SQL Server, а результатом работы стала правильно спроектированная, проверенная на логическую...
-
Показатели обслуживания пассажиров в справочном бюро автовокзала - число окон, обеспечивающих предоставление необходимого числа справок, длина очереди и...
-
Программное обеспечение сервера базы данных обрабатывает запросы, инициализированные программным обеспечением клиента, отправляя результат обратно в базу...
-
Реализация с помощью средств быстрой разработки DbForge Studio for SQL Server -- среда разработки для БД SQL Server, создания отчетов по данным, их...
-
Для поддержания компьютерной системы 1С:Библиотека в исправном состоянии необходимо осуществлять мероприятия в соответствии с типовой системой...
-
Аппаратный и программный аспекты диагностики КС Диагностика неисправностей КС имеет два аспекта: аппаратный и программный. Аппаратный аспект...
-
Система IP-адресации. - Использование компьютерных сетей
Для организации всемирной сети нужна хорошая система адресации, которая будет использоваться для направления информации всем адресатам. Союз Internet...
-
Глобальная компьютерная сеть Интернет - Использование компьютерных сетей
Цель данной темы - дать основные представления о глобальной компьютерной сети Интернет. Теоретический материал: Введение. Виды подключения к сети...
-
Доставочные агенты., Адресация в системе электронной почты - Использование компьютерных сетей
Программы, которые принимают почту от транспортного агента и доставляют ее соответствующим пользователям. Почта может доставляться конкретному лицу, в...
Деление двоичных беззнаковых чисел в компьютерных системах - Компьютерная арифметика