Деление двоичных чисел алгоритм

Деление двоичных чисел алгоритм

Алгоритмы деления двоичных чисел

Рассмотрим алгоритмы операции деления целых положительных двоичных чисел на , где А – 2п-разрядное делимое; В – и-разрядный делитель; . Полагаем, что частное является целым от-разрядным числом , при этом

Алгоритм деления с восстановлением остатка. Значения разрядов частногоопределяются в результате анализа остатков, полученных после вычитания делителя В на первом шаге алгоритма из старших разрядов делимого Дст, а на последующих шагах – из старших разрядов текущего остатка.

При положительном и пулевом значениях остатка разряд частного ck = 1. В этом случае для получения следующего остатка текущий остаток сдвигается на один разряд влево и из него вычитается делитель В.

При отрицательном значении остатка текущий разряд частного ck = 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. Алгоритм деления двоичных чисел без восстановления остатка

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

Деление двоичных чисел во многом аналогично делению десятичных чисел.

В универсальных вычислительных машинах, как правило, реализуется "школьный" алгоритм деления чисел. "Школьный" алгоритм деления заключается в том, что делитель на каждом шаге вычитается из делимого столько раз (начиная со старших разрядов), сколько это возможно для получения наименьшего положительного остатка. Тогда в очередной разряд частного записывается цифра, равная числу делителей, содержащихся в делимом на данном шаге. Иначе говоря, при делении операцию вычитания повторяют до тех пор, пока уменьшаемое не станет меньше вычитаемого. Число этих повторений показывает, сколько раз вычитаемое укладывается в уменьшаемом.

Читайте также:  Как отслеживать человека по номеру телефона мегафон

разделим число 35 на 7 :

1) 35 — 7 = 28, 2) 28 — 7 = 21, 3) 21 — 7 = 14, 4) 14 — 7 = 7, 5) 7 — 7 = 0.

Ответ равен 5, т.к. процедура вычитания была повторена 5 раз.

Рассмотрим еще один пример:

разделим 204(10) на 12(10), т.е. 11001100(2):1100(2):

делимое 11001100 | 1100 — делитель

делитель 1100 | 10001

Двоичное, как и десятичное деление, начинается с анализа делимого (11001100) и делителя (1100). Сразу же обнаруживается, что делитель укладывается в 1100, а поэтому записывается 1 в старший разряд поля частного. Умножается делитель на 1 и вычитается из 1100, разность равна 0. Объединяется 0 остатка со значением следующего разряда делимого, равным 1. Поскольку делитель (1100) 0 раз укладывается в 1, записываем 0 в следующий по старшинству разряд поля частного, а число 1 объединяется со следующим разрядом делимого и т.д. до тех пор, пока делимое не оказывается исчерпанным.

Конечно компьютер не может строить догадок относительно того, сколько раз делитель укладывается в том или ином числе, поэтому весь процесс деления сводится к операциям вычитания и сдвига. Продемонстрируем на том же примере, но сначала делитель (1100) представим в дополнительном коде, что позволит ограничиться сложением во всех случаях, когда нужно выполнять сложение или вычитание: 1100пр = 1. 0100д. Частное формируется в некотором регистре С, незаполненные разряды которого будем обозначать через Х.

Начинаем вычитать делитель из делимого. Если остаток получается положительным, то в разряд частного записывается 1, в противном случае — 0.

0. 11001100 делимое 204

+ 1. 01000000 делитель 12

0. 00001100 первый остаток

Первый (старший) бит частного равен 1, т.к. остаток получился положительным: С = 1ХХХХ. Далее сдвигается первый остаток на один разряд влево и из него вычитывается делитель:

1. 01011000 второй остаток

Остаток отрицательный, поэтому в следующий разряд частного записывается 0, С = 10ХХХ. Кроме того необходимо биты делителя вернуть обратно первому остатку, т.е. сложить делитель (в прямом коде) и второй остаток:

0. 00011000 сдвинутый первый остаток.

Далее еще раз сдвигается сдвинутый первый остаток на один разряд влево и вычитается из него делитель:

1. 01110000 третий остаток

Третий остаток отрицательный, значит следующий (третий) разряд частного равен 0, С = 100ХХ. Поэтому возвращаем делитель третьему остатку,

0. 00110000 дважды сдвинутый первый остаток

Сдвигаем дважды сдвинутый первый остаток на один разряд влево и вычитаем делитель:

1. 10100000 четвертый остаток

Четвертый остаток опять отрицательный, поэтому С = 1000Х. Прибавляем делитель к четвертому остатку, результат сдвигаем на один разряд влево, а затем вновь вычитаем делитель:

Читайте также:  Найти максимум целевой функции при ограничениях

0. 1100000 первый остаток после четвертого сдвига

0. 0000000 пятый остаток

Остаток положительный, значит С = 10001 = 17(10) — это и есть ответ.

Такой метод деления называется делением с восстановлением остатка.

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

Перед выполнением самой процедуры деления чисел в формате с фиксированной запятой определяется и запоминается знак частного. Далее оба операнда представляются в прямом коде, а делитель еще и в дополнительном для того, чтобы вычитание делителя заменить сложением, и выполняется сама процедура деления по описанному выше методу с обязательным контролем переполнения разрядной сетки. Если знак частного отрицательный, то ответ, при необходимости, представляется в дополнительном коде.

Например: разделим 35 на 5. 3510 = 0.1000112, 510 = 1012, 5д = 1.011д

(в регистре С, как и в предыдущем примере, формируется частное):

1.111011 С = 0 восстанавливаем остаток до делимого.

0.100011 сдвигаем влево остаток.

0.01111 С = 01, сдвигаем влево остаток.

0.0101 С = 011, сдвигаем остаток.

0.000 С = 0111 = 710

Вычитание делимого продолжают столько раз, сколько разрядов отведено для частного.

Метод деления без восстановления остатка. Как уже отмечалось, основой выполнения деления является операция вычитания с целью получения остатка, знак которого определяет цифру частного. Алгоритм выполнения деления имеет следующий вид:

где a0 — это остаток. Если а0 0, то С = 1, если а0 0, С = 01

+ 1.011000 5 в дополнительном коде (т.е. вычитание 5)

0.010100 a2>0, С = 011

0.000000 a3 = 0, С = 0111 = 710

4.3.2. Деление двоичных чисел, представленных в форме с плавающей запятой.

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

A1 : A2 = m12 : m22 = (m1 : m2)2 .

Знак ответа определяется обычным образом. Если ответ получился ненормализованный, то выполняется процедура нормализации и округления ответа.

Т.к. мантиссы операндов нормализованы, то возможны случаи, когда

Напомним, что при реализации алгоритмов математических операций в формате с плавающей запятой каждый раз, когда осуществляется та или иная процедура, затрагивающая характеристики операндов или результата, производится контроль над переполнением и исчезновением порядка, т.е. контролируется условие

A = 10 = 0,1010, pA = 4, B = 2 = 0,1, pB = 2. p = pA — pB = 2. mA = 0.1010,

mB = 0.1 , (mB)l = 1.1000. |mA| > |mB|. При первом вычитании mB из mA 1 записываем в целую часть частного:

а0 0.0010 С = 1,XX, далее, будем делить методом деления без восстановления остатка.

Дата добавления: 2016-07-18 ; просмотров: 6198 ;

Деление в принципе является неточной операцией, поэтому при её выполнении прежде всего устанавливается количество разрядов частного, которые подлежат определению. Деление в двоичной системе счисления может выполняться точно так же, как и в десятичной, однако формирования частного двоичных операндов реализуется гораздо проще, чем в десятичной системе, т.к.:

Читайте также:  Приложение fujifilm для цифровой камеры

• Упрощается процедура подбора очередной цифры вследствие того, что в двоичной системе очередной цифрой может быть одна из двух — либо 0, либо 1;

• Упрощается процедура умножения найденной цифры частного на делитель.

ПримерНайти частное от деления двоичных чисел 0.1001 на 0.1101.

РешениеПо умолчанию считается, что разрядность результата и операндов одинаковая, поэтому окончательный результат должен иметь в данном случае 4 разряда. Учитывая необходимость округления, найдем дополнительный пятый разряд, на основании которого выполним округление.

12. Сложение двоично-десятичных чисел

Рассмотрим на конкретном примере реализацию этой операции. Пример Найти сумму двух десятичных чисел с использованием двоично-десятичной системы счисления: A = D + C, где D = 3927; C = 4856. Решение Составляем двоично-десятичную запись для чисел D и C: D =3927 = 0011 1001 0010 0111: C = 4856 =0100 1000 0101 0110. Найти значение А можно, реализовав следующую последовательность операций из двоичного сложения и операции коррекции:

Для получения двоично-десятичной суммы A на основании результата сложения операндов по правилам двоичной арифметики необходимо добавить шестерку (0110) в те тетрады, из которых был перенос. В данном примере это вторая тетрада (отмечена *). Необходимость такой коррекции обусловливается тем, что перенос, сформированный по правилам двоичного суммирования, унес из тетрады шестнадцать, а для десятичного сложения перенос должен был унести десять, т.е. перенос, сформированный по правилам двоичной арифметики, унес лишнюю шестерку. Кроме этого шестерка добавляется в те тетрады, в которых получено значение, большее девяти. Такая коррекция обуславливается тем, что по правилам десятичной арифметики в25 таких тетрадах должен быть выработан перенос и, чтобы его выработать по правилам двоичной арифметики, в тетраду нужно добавить шестерку. Для рассмотренного примера такой тетрадой является и четвертая тетрада (отмечена **)

13. Двоично-десятичная арифметика. Вычитание двоично-десятичных чисел.

В ЭВМ часто предусматривается обработка чисел не только в двоичной системе счисления, но в двоично-десятичной. При этом, как правило, стремятся реализовать двоично-десятичную арифметику по правилам двоичной с введением ограниченного количества коррекций.

Для получения двоично-десятичной разности «A» на основании результата вычитания операндов по правилам двоичной арифметики необходимо вычесть шестерку (0110) из тетрад, в которые пришел заем. Это обусловливается тем, что заем, сформированный по правилам двоичного вычитания, приносит в тетраду шестнадцать, а для десятичного сложения заем должен был принести в тетраду десять, т.е. заём, сформированный по правилам двоичной арифметики, принес лишнюю шестерку. Для рассмотренного примера тетрадами, в которые пришел заем и в которых необходимо выполнить коррекцию (вычесть шестерку), являются вторая и четвертая тетрады (отмечены *).

Ссылка на основную публикацию
Делаем постер в фотошопе
Многие из нас хотели бы видеть у себя на стене плакат с любимыми персонажами сериалов, репродукциями картин или просто красивыми...
Генератор вложенных списков python
подскажите как можно записать это с помощью генератора списков 1 ответ 1 Все ваши предыдущие вопросы, включая данный, связаны с...
Генератор красивого шрифта для вк
Создать красивый текст надпись разными шрифтами и символами для соцсетей Инстаграм, фейсбук, вконтакте, твиттер Доступно 29 разных онлайн шрифтов для...
Деление двоичных чисел алгоритм
Алгоритмы деления двоичных чисел Рассмотрим алгоритмы операции деления целых положительных двоичных чисел на , где А – 2п-разрядное делимое; В...
Adblock detector