Выполнение арифметических операций в компьютерных системах над двоичными числами с фиксированной точкой

4.1 Операция сложения и вычитания, двоичных беззнаковых чисел в компьютерных системах

Компьютерная система выполняет сложение и вычитание операндов по правилам сложения и вычитания двоичных беззнаковых чисел рис.4.1:

Правила сложения:	Правила вычитания:
1. 0 + 0 = 0	1. 0 - 0 = 0
2. 0 + 1 = 1	2. 1 - 1 = 0
3. 1 + 0 = 1	3. 1 - 0 = 1
4. 1 + 1 = 10	4. 10 - 1 = 1

Рисунок 4.1 - Правила сложения и вычитания, двоичных беззнаковых чисел

Проблем не возникает до тех пор, пока значение результата не превышает разрядной сетки операнда.

Например: необходимо перевести в двоичную систему счисления, а затем сложить два числа: 7₍₁₀₎ и 5₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ). Длина разрядной сетки операндов равна четырем битам.

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

Например: необходимо перевести в двоичную систему счисления, а затем найти разность двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам вычитания двоичных беззнаковых чисел ). Длина разрядной сетки операндов равна четырем битам рис.4.3.

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

Например: необходимо перевести в двоичную систему счисления, а затем найти сумму двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ). Длина разрядной сетки операндов равна четырем битам рис.4.4.

Десятичное число	Двоичное число
7(10)	0111(2)
5(10)	0101(2)
12(10)	1100(2)

Рисунок 4.2 - Пример вычисления суммы двух чисел: 7₍₁₀₎ и 5₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ), при четырехразрядной сетке операндов

Десятичное число	Двоичное число
9(10)	1001(2)
7(10)	0111(2)
2(10)	0010(2)

Рисунок 4.3 - Пример вычисления разности двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам вычитания двоичных беззнаковых чисел ), при четырехразрядной сетке операндов

Десятичное число	Двоичное число
9(10)	1001(2)
7(10)	0111(2)
16(10)		0000(2)

Рисунок 4.4 - Пример вычисления суммы двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ), при четырехразрядной сетке операндов

В примере, представленном на рис.4.4 видно, что (1) вышла за пределы разрядной сетки операнда.

При обработке полученной суммы она не учитывается и следовательно сумма получилась равной (0), а не (16), что является не верным результатом.

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

Например: необходимо перевести в двоичную систему счисления, а затем найти сумму двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ). Длина разрядной сетки операндов равна восьми битам рис.4.5:

Десятичное число	Двоичное число
9(10)	00001001(2)
7(10)	00000111(2)
16(10)	00010000(2)

Рисунок 4.5 - Пример вычисления суммы двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ), при восьмиразрядной сетке операндов

В компьютерной системе этот исход сложения прогнозируется и предусмотрены специальные средства для фиксирования подобных ситуаций и их обработки.

Так, для фиксирования ситуации выхода за разрядную сетку результата, как в данном примере, предназначен флаг переноса (FC). Он располагается в бит - (0) регистра флагов eflags. Именно установкой этого флага фиксируется факт переноса (1) из старшего разряда операнда за пределы разрядной сетки.

Естественно, что программист должен предусматривать возможность такого исхода операции сложения и средства для корректировки. Это предполагает включение участков кода после операции сложения, в которых анализируется флаг (FC). Анализ этого флага можно провести различными способами. Самый простой и доступный использовать команду условного перехода. Эта команда в качестве операнда имеет имя метки в текущем сегменте кода. Переход на эту метку осуществляется в случае если в результате работы предыдущей команды флаг (FC) установился в (1).

4.2 Операция сложения и вычитания двоичных знаковых чисел в компьютерных системах

При сложении и вычитании знаковых двоичных чисел операция вычитания заменяется операцией сложения в дополнительном коде.

Докажем, что результат выполнения операций сложения и вычитания над числами, представленными в ДК, являются ПК, ОК или ДК соответственно.

Для этого рассмотрим отдельно формирование числовой и знаковой частей суммы.

Тогда операцию сложения проанализируем над «псевдомодулями» слагаемых - дополнительными кодами, у которых отброшен знаковый разряд.

В этом случае граничное число (C) станет равным весу знакового разряда, который становится отсутствующим.

Представим операцию сложения в общем виде:

. (4.1)

где Z - сумма;

X - первое слагаемое;

Y - второе слагаемое.

В зависимости от знаков слагаемых возможны следующие варианты:

1. , тогда:

.

Например: рассмотрим два случая а) и б).

Случай а): необходимо вычислить сумму двух чисел записанных в десятичной системе счисления (5+2=7), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита. Формат суммы представлен на рис. 4.6, а вычисление суммы и значения флагов на рис.4.7.

0,
D3	D2	D1	D0

Рисунок 4.6 - Формат суммы

Случай а)
Десятичное число	Двоичное число	Значения флагов
5(10)	0,101(2)	FC=0
2(10)	0,010(2)	FS=0
7(10)	0,111(2)	FZ=0
		FO=0

Рисунок 4.7 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=0, потому, что нет перехода (1) из разряда D2 в знаковый разряд D3 и нет перехода из знакового разряда D3 за пределы разрядной сетки.

- FS=0, потому, что значение знакового бита D3=0.

- FZ=0, потому, что сумма не равняется (0).

- FO=0, потому, что результат правильный и переполнение разрядной сетки нет.

Случай б):необходимо сложить два числа записанных в десятичной системе счисления (7+7=14), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита.

Формат суммы представлен на рис. 4.8, а вычисление суммы и значения флагов на рис.4.9.

1,
D3	D2	D1	D0

Рисунок 4.8 - Формат суммы

Случай б)
Десятичное число	Двоичное число	Значения флагов
7(10)	0,111(2)	FC=1
7(10)	0,111(2)	FS=1
14(10)	1,110(2)	FZ=0
		FO=1

Рисунок 4.9 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=1, потому, что есть перехода (1) из разряда D2 в знаковый разряд D3 и нет перехода из знакового разряда D3 за пределы разрядной сетки.

- FS=1, потому, что значение знакового бита D3=1, а это не правильно так как оба слагаемых положительные числа, значит и сумма должна быть положительной, а в данном случае сумма получается отрицательной так как знаковый бит равен (1).

- FZ=0, потому, что сумма не равняется (0).

- FO=1, потому, что результат не правильный и переполнение разрядной сетки есть.

2. и , тогда:

.

Например: необходимо сложить два числа записанных в десятичной системе счисления (5+(-2)=3), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита.

Формат суммы представлен на рис. 4.10, а вычисление суммы и значения флагов на рис.4.11.

	0,
	D3	D2	D1	D0

Рисунок 4.10 - Формат суммы

Десятичное число	Двоичное число	Значения флагов
5(10)	0,101(2)	FC=0
(-2)(10)	1,110(2)	FS=0
(3)(10)	10,011(2)	FZ=0
		FO=0

Рисунок 4.11 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=0, потому, что есть перехода (1) из разряда D2 в знаковый разряд D3 и есть перехода из знакового разряда D3 за пределы разрядной сетки.

- FS=0, потому, что значение знакового бита D3=0.

- FZ=0, потому, что сумма не равняется (0).

- FO=0, потому, что результат правильный и переполнение разрядной сетки нет. Единица, которая вышла за пределы разрядной сетки не учитывается.

3. и , тогда: , по сути, представляет собой дополнительный код отрицательной разности:

. так как

.

Например: необходимо сложить два числа записанных в десятичной системе счисления (2+(-5)=(-3)), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита.

Формат суммы представлен на рис. 4.12, , а вычисление суммы и значения флагов на рис.4.13.

	0,
	D3	D2	D1	D0

Рисунок 4.12 - Формат суммы

Десятичное число	Двоичное число	Значения флагов
2(10)	0,010(2)	FC=0
(-5)(10)	1,011(2)	FS=1
(-3)(10)	1,101(2)	FZ=0
		FO=0

Рисунок 4.13 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=0, потому, что нет перехода (1) из разряда D2 в знаковый разряд D3 и нет перехода из знакового разряда D3 за пределы разрядной сетки.

- FS=1, потому, что значение знакового бита D3=1.

- FZ=0, потому, что сумма не равняется (0).

- FO=0, потому, что результат правильный и переполнение разрядной сетки нет. Число 1,101 и есть (-3). Для того, чтобы перейти к прямому коду необходимо все биты проинвертировать, а затем к младшему биту прибавить (1), рис.4.14:

1,101(2)	(-3)
0,010(2)	инверсия
1(2)	+1
0,011(2)	(+3)

Рисунок 4.14 - Пример перехода от дополнительного кода числа к прямому коду

4. , тогда:

.

Например: рассмотрим два случая а) и б).

Случай а): необходимо сложить два числа записанных в десятичной системе счисления ((-5)+(-2)=(-7)), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита. Формат суммы представлен на рис. 4.15, а вычисление суммы и значения флагов на рис.4.16.

	1,
	D3	D2	D1	D0

Рисунок 4.15 - Формат суммы

Случай а)
Десятичное число	Двоичное число	Значения флагов
(-5)(10)	1,011(2)	FC=0
(-2)(10)	1,110(2)	FS=1
(-7)(10)	11,001(2)	FZ=0
		FO=0

Рисунок 4.16 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=0, потому, что есть переход (1) из разряда D2 в знаковый разряд D3 и есть перехода из знакового разряда D3 за пределы разрядной сетки.

- FS=1, потому, что значение знакового бита D3=1.

- FZ=0, потому, что сумма не равняется (0).

- FO=0, потому, что результат правильный и переполнение разрядной сетки нет. Единица, которая вышла за пределы разрядной сетки не учитывается.

Число 1,001 и есть (-7). Для того, чтобы перейти к прямому коду необходимо все биты проинвертировать, а затем к младшему биту прибавить (1), рис.4.17.

Случай б):необходимо сложить два числа записанных в десятичной системе счисления ((-7)+(-7)=(-14)), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита.

Формат суммы представлен на рис. 4.18, а вычисление суммы и значения флагов на рис.4.19.

1,001(2)	(-7)
0,110(2)	инверсия
1(2)	+1
0,111(2)	(+7)

Рисунок 4.17 - Пример перехода от дополнительного кода числа к прямому коду

	0,
	D3	D2	D1	D0

Рисунок 4.18 - Формат суммы

	Случай б)
Десятичное число	Двоичное число	Значения флагов
(-7)(10)	1,001(2)	FC=1
(-7)(10)	1,001(2)	FS=0
(-14)(10)	10,010(2)	FZ=0
		FO=1

Рисунок 4.19 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=1, потому, что нет перехода (1) из разряда D2 в знаковый разряд D3 и есть переход из знакового разряда D3 за пределы разрядной сетки.

- FS=0, потому, что значение знакового бита D3=0, а это не правильно так как оба слагаемых отрицательные числа, значит и сумма должна быть отрицательные, а в данном случае сумма получается положительной так как знаковый бит равен (0).

- FZ=0, потому, что сумма не равняется (0).

- FO=1, потому, что результат не правильный и переполнение разрядной сетки есть. Единица, которая вышла за пределы разрядной сетки не учитывается.

Из вышесказанного на примере (4^х- разрядной) сетки можно сделать следующие выводы:

- переполнение разрядной сетки возможно, когда оба операнда имеют одинаковые знаки;

- есть переход (1) из разряда D2 в знаковый разряд D3 и нет перехода из знакового разряда D3 за пределы разрядной сетки.

- нет перехода (1) из разряда D2 в знаковый разряд D3 и есть переход из знакового разряда D3 за пределы разрядной сетки.

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

4.3 Операции сдвига в компьютерных системах

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

Существует несколько вариантов сдвига:

1. Логический сдвиг. Сдвиг, который выполняется над всеми разрядами операнда, включая знаковый.

2. Арифметический сдвиг. Не влияет на положение знака операнда.

Арифметический сдвиг двоичного операнда влево или вправо на (i) разрядов эквивалентно соответственно умножению и делению исходного операнда на (2ⁱ).

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

Сдвиг влево имеет смысл, пока не теряются значащие цифры операнда.

3. Модифицированный сдвиг. Арифметический сдвиг операндов, представленных обратным или дополнительным кодом:

- обратный код - при правом и левом сдвигах в освобождающиеся разряды регистра записываются цифры знакового разряда;

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

4. Циклический сдвиг. Операнд перемещается в регистре как в замкнутом контуре, поступая с выхода последнего разряда на вход первого.

Схемы выполнения операций сдвига приведены на рис. 4.20.

Рисунок 4.7 - Схемы выполнения операций сдвига

4.4 Умножение двоичных беззнаковых чисел в компьютерных системах

Пусть сомножителями X и Y являются s-битные целые числа без знака:

где – (Х) – множимое, (Y) – множитель, (Z) – произведение. Тогда:

Z = X ∙ Y. (4.2)

где: ;

.

Представим множитель Y в развернутой форме:

. (4.3)

Тогда:

(4.4)

Произведение множимого на один бит множителя называется частичным произведением. Полное произведение числа представляет собой сумму (s) частичных произведений (ЧП). При умножении вручную существует два способа:

- способ № 1, начиная с младшей цифры множителя и сдвиг частичных произведений влево;

- способ № 2, начиная со старшей цифры множителя и сдвиг частичных произведений вправо. Например. Необходимо перемножить два беззнаковых числа (7∙3=21). Для удобства возьмем длину разрядной сетки равную четырем битам. Правило умножения вручную заключается в следующем:

- шаг 1. Анализируется младший (правый) бит множителя, если младшая цифра множителя равна (1), то в сумму частичных произведений записываются все биты множимого, если младшая цифра множителя равна (0), то в сумму частичных произведений записываются все (0);

- шаг 2. Анализируется следующий после младшего бит множителя, если цифра множителя равна (1), то в сумму частичных произведений записываются все биты множимого сдвинутые на один разряд влево, если цифра множителя равна (0), то в сумму частичных произведений записываются все (0), сдвинутые на один разряд влево;

- шаг 3. Шаги (1) и (2) повторяются до тех пор, пока не будут проанализированы все цифры множителя;

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

Итак: необходимо перемножить два беззнаковых числа (7∙3=21)

где: (7) – множимое;

(3) – множитель;

(21) – произведение.

Необходимо вычислить сумму частичных произведений – (ЧП), а следовательно и произведение.

Способ №1

Десятичное число	Двоичное число	Комментарии
7(10)	0111(2)	множимое
3(10)	0011(2)	множитель
		номера цифр множителя
		1ое – ЧП
		2ое – ЧП
		3ое – ЧП
	4ое – ЧП
21(10) 0010101(2)	сумма ЧП - произведение

Способ №2

Десятичное число	Двоичное число	Комментарии
7(10)	0111(2)	множимое
3(10)	0011(2)	множитель
		номера цифр множителя
		1ое – ЧП
		2ое – ЧП
		3ое – ЧП
	4ое – ЧП
21(10) 0010101(2)	сумма ЧП - произведение

В отличие от ручного умножения, операционное устройство компьютера не может просуммировать сразу (s) частичных произведений, как это делает человек. Обычный сумматор, как правило, рассчитан на одновременное сложение только двух операндов. Если нужно получить сумму нескольких слагаемых, то происходит накопление суммы: сначала в сумматор записывается первое слагаемое, к нему прибавляется второе, затем к полученной сумме прибавляется третье слагаемое и так до получения полной суммы.

Длина произведения s-битных сомножителей равна 2s бит:

(4.5)

Поскольку умножение на ( ) эквивалентно сдвигу влево, то вычисление произведения (Z) сводится к формированию частичных произведений ( ), их сдвигу и суммированию с учетом весов, определяемых величинами ( ).

(4.6)

Умножение реализуется циклическим процессом, на каждом шаге которого:

- анализируется очередной бит множителя;

- в зависимости от его значения происходит (y_i=1) или нет (y_i=0) прибавление множимого к предыдущей сумме частичных произведений;

- производится изменение взаимного положения множимого (X) и суммы частичных произведений с учетом веса (2ⁱ).

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

В соответствии со способом формирования суммы частичных произведений – (ЧП), возможны четыре варианта умножения. Они различаются тем, с каких разрядов множителя (Y) (младших или старших) начинается умножение, и что сдвигается (множимое или сумма ЧП).

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

Рисунок 4.8 — Схемы выполнения операции умножения двоичных беззнаковых чисел

Соответственно, при умножении старшими разрядами вперед должен анализироваться старший разряд множителя.

Схема 1

. (4.7)

. (4.8)

Время выполнения операции умножения:

(4.9)

где (t_с) — время, затрачиваемое на выполнение операции сдвига на один разряд;

(t₊) — время, затрачиваемое на выполнение операции сложения.

Схема 2

. (4.10)

(4.11)

. (4.12)

Схема 3

. (4.13)

. (4.14)

. (4.15)

Схема 4

. (4.16)

. (4.17)

. (4.18)

Рассмотрим на примере два базовых алгоритма умножения в компьютерных системах двоичных беззнаковых чисел:

Алгоритм №1. Алгоритм умножения младшими разрядами вперед, со сдвигом суммы ЧП вправо.

1. Исходное значение суммы (ЧП) принимается равным (0), счетчику тактов – (Сч.Т) присваивается значение, равное числу разрядов множителя.

2. Анализируется младшая разрядная цифра множителя. Если она равна (1), то к сумме (ЧП) прибавляется множимое, совмещенное по старшим разрядам; если (0) — прибавление не производится.

3. Производится сдвиг множителя и суммы ЧП вправо на (1) разряд. Содержимое (Сч.Т) уменьшается на (1).

4. Анализируется содержимое (Сч.Т). Если оно не равно (0), то переход к (п.2), иначе — (п.5).

5. Умножение закончено, младшая часть произведения находится на месте множителя, а старшая — на месте суммы (ЧП). Например: необходимо перемножить два беззнаковых числа (7∙3=21). Для удобства возьмем длину разрядной сетки равную четырем битам, а именно: Х = 7 – множимое, Y = 3 – множитель, Z = 21 – произведение. Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением, т.е длина разрядной сетки произведения в два раза больше множимого и множителя. Алгоритм умножения приведен в табл. 4.1.

Таблица 4.1 - Алгоритм умножения со сдвигом вправо двоичных беззнаковых чисел

Регистр (В) множимое X	Регистр (С) множитель Y	Регистр (А) произведение Z	Счетчик тактов (Сч.Т)	Комментарии
				множимое
				1Я СЧП
							1ЫЙсдвиг СЧП
				множимое
				2Я СЧП
							2 ОЙсдвиг СЧП
							3 ИЙсдвиг СЧП
							4ЫЙсдвиг СЧП
		СТОП

Алгоритм №2. Алгоритм умножения старшими разрядами вперед, со сдвигом суммы ЧП влево.

1. Исходное значение суммы (ЧП) принимается равным (0), (Сч.Т) присваивается значение, равное числу разрядов множителя.

2. Производится сдвиг суммы (ЧП) влево на (1) разряд.

3.Анализируется старшая разрядная цифра множителя. Если она равна (1), то к сумме (ЧП) прибавляется множимое, совмещенное по младшим разрядам; если (0) — прибавление не производится.

4.Производится сдвиг множителя влево на (1) разряд. Содержимое (Сч.Т) уменьшается на (1).

5.Анализируется содержимое (Сч.Т). Если оно не равно (0), то переход к (п.2), иначе — (п.6).

6.Умножение закончено, произведения находится на месте суммы (ЧП), которая имеет удвоенную разрядность. Например: необходимо перемножить два беззнаковых числа (7∙3=21). Для удобства возьмем длину разрядной сетки равную четырем битам, а именно: Х = 7 – множимое, Y = 3 – множитель, Z = 21 – произведение. Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением, т.е длина разрядной сетки произведения в два раза больше множимого и множителя. Алгоритм умножения приведен в табл. 4.2.

Таблица 4.2 - Алгоритм умножения со сдвигом влево двоичных беззнаковых чисел

Регистр (В) множимое X	Регистр (С) множитель Y	Регистр (А) произведение Z	Счетчик тактов (Сч.Т)	Комментарии
				1ЫЙсдвиг СЧП
							2 ОЙсдвиг СЧП
				3 ИЙсдвиг СЧП
							4ЫЙсдвиг СЧП
				5ЫЙсдвиг СЧП
				множимое
				1Я СЧП
							6ОЙ сдвиг СЧП
				множимое
				2Я СЧП
		СТОП

4.5 Деление двоичных беззнаковых чисел в компьютерных системах

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

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

В отличие от умножения этот процесс имеет итеративный характер, так как результат деления в большинстве случаев не может быть точно представлен числом конечной длины.

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

Обозначим 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). Исходное значение частичного остатка (R₀) полагается равным (s) старшим разрядам делимого.

2. Выполняется пробное вычитание делителя (Y) из исходного значения частичного остатка – (ЧО). Положительная разность указывает на то, что частное превысит (s-разрядную сетку), и будет выполнено прерывание. Если же результат вычитания отрицательный, то деление можно выполнять.