Пример деления двоичных чисел методом без восстановления остатка

Ваша задача будет решена с вашими исходными данными OnLine и бесплатно

Задача:

Разделить число A = 213₁₀ на число B = 17₁₀ в двоичной системе счисления, методом без восстановления остатка.

Решение:

1) Переведем числа в двоичную систему счисления (работать будем только с модулями чисел, знак результата получим из анализа знаков исходных чисел):

213₁₀ = 11010101₂
17₁₀ = 10001₂

2) Впишем делимое A в 16-ти разрядный регистр, начиная с младших разрядов (нумерация разрядов начинается с нуля). В недостающие разряды записываем нули.

Разр.	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
A:	0	0	0	0	0	0	0	0	1	1	0	1	0	1	0	1

Обратите внимание! Так как для выполнения деления требуется производить операцию вычитания, это требует использования знаковой ариaметики. И поэтому в нашем случае 15-й разряд является знаковым (0 - соответствует положительному числу, 1 - отрицательному), а старшим разрядом числа является 14-й разряд.

3) Впишем делитель В в 16-ти разрядный регистр, начиная с младших разрядов. В недостающие разряды записываем нули.

Разр.	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
B:	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	1

Здесь также как и с числом A 15-й разряд является знаковым, а старшим разрядом числа является 14-й разряд. Эти знаковые разряды будут показывать нам знаки, образующихся в процессе деления, частичных остатков. Они не имеет никакого отношения к знакам исходных операндов и знаку результата, а играют чисто технологическую роль.

4) Предварительный сдвиг делителя. Сдвинем делитель B влево так, чтобы позиция старшей значащей единицы, в нем, совпала с позицией старшей значащей единицы в делимом A. Количество необходимых для этого сдвигов запомним в числе k В нашем случае старшая значащая единица в делимом A расположена в 7-м разряде, a в делителе B - в 4-м разряде. Следовательно нам необходимо сдвинуть число B влево на 3 разряда (k = 3).
Сдвинутый делитель выглядит следующим образом :

Разр.	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
B:	0	0	0	0	0	0	0	0	1	0	0	0	1	0	0	0

5) Так как в процессе деления множитель B придется не только прибавлять но и вычитать, то нам необходимо иметь число -B. Для этого представим B в дополнительном коде. Перевод в дополнительный код осуществим в два этапа:

5.1)Вначале получим обратный код. Для этого просто проинвертируем каждый разряд регистра (заменим "0" на "1", а "1" на "0").

Разр.	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
B_обр	1	1	1	1	1	1	1	1	0	1	1	1	0	1	1	1

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

Разр.	c	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
														1	1	1
B_обр		1	1	1	1	1	1	1	1	0	1	1	1	0	1	1	1
+		0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

B_доп		1	1	1	1	1	1	1	1	0	1	1	1	1	0	0	0

Таким образом -B = B_доп

6) Процесс деления будет следующий:

6.1) Вычитаем из делимого А делитель В (т.е. прибавляем -В).

6.2) Анализируем знак полученного частичного остатка (15-й разряд). В регистр результата записываем "0" если остаток отрицательный и единицу в противном случае. Помним, что отрицательному числу соответствует наличие единицы в 15-м разряде и наоборот.

6.3) Сдвигаем частичный остаток на один разряд влево. При этом крайний правый (младший) разряд заполняется нулем, а знаковый разряд (15-й) в процессе сдвига не участвует.

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

6.5) Анализируем знак полученного частичного остатка (15-й разряд). В регистр результата записываем "0" если остаток отрицательный и единицу в противном случае.

6.6) Действия описанные в пунктах 6.3-6.5 выполняем k раз (если k=0, то ни разу не выполняем).
Весь процесс деления выглядит следующим образом :

	Разр.	c	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
		1	1	1	1	1	1	1	1	1	1	1	1
Частное	А		0	0	0	0	0	0	0	0	1	1	0	1	0	1	0	1
	- B		1	1	1	1	1	1	1	1	0	1	1	1	1	0	0	0

1	=		0	0	0	0	0	0	0	0	0	1	0	0	1	1	0	1
		1	1	1	1	1	1	1	1	1	1	1	1	1
	<--		0	0	0	0	0	0	0	0	1	0	0	1	1	0	1	0
	- B		1	1	1	1	1	1	1	1	0	1	1	1	1	0	0	0

1	=		0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	0
											1	1
	<--		0	0	0	0	0	0	0	0	0	0	1	0	0	1	0	0
	- B		1	1	1	1	1	1	1	1	0	1	1	1	1	0	0	0

0	=		1	1	1	1	1	1	1	1	1	0	0	1	1	1	0	0
												1	1	1
	<--		1	1	1	1	1	1	1	1	0	0	1	1	1	0	0	0
	+ B		0	0	0	0	0	0	0	0	1	0	0	0	1	0	0	0

0	=		1	1	1	1	1	1	1	1	1	1	0	0	0	0	0	0

Здесь в колонке "Частное", сверху вниз, записаны разряды искомого частного, начиная со старших. Обратите внимание - значение разряда частного - это просто иверсия 15-го (знакового) разряда частичного остатка.
В следующем столбце - символика действий предпринимаемых в зависимости от знака частичного остатка. Смысл этих символов следующий:
    + В - делитель В прибавляется к регистру делимого A;
    - В - делитель В вычитается из регистра делимого A (технически здесь прибавляется В_доп );
    <-- - частичный остаток сдвигается на один разряд влево;
   " = " - показывается значение частичного остатка полученного после сложения.

7) Определяем остаток от деления. Для этого анализируем последний частичный остаток. В нашем случае он равен "1111111111000000".
7.1) Анализируем знак остатка (15-й разряд). В знаковом разряде содержится единица, значит требуется коррекция остатка. Для коррекции прибавим к нему делитель B.

Разр.	c	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
	1	1	1	1	1	1	1	1	1
		1	1	1	1	1	1	1	1	1	1	0	0	0	0	0	0
+ B		0	0	0	0	0	0	0	0	1	0	0	0	1	0	0	0

=		0	0	0	0	0	0	0	0	0	1	0	0	1	0	0	0

7.2) Так как в процессе деления частичные остатки были сдвинуты 3 раза влево, то для получения верного значения последний полученный остаток необходимо сдвинуть 3 раза вправо (вернуть на место). После сдвига имеем:

Разр.	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1

8) Определяем знак результата. Если знаки исходных операндов одинаковы, то результирующее частное положительно и наоборот. В нашем случае знаки совпадают, следовательно результирующее частное положительно.

Ответ: 11010101₂ : 10001₂ = 1100₂ и 1001₂ в остатке.

или в десятичной системе счисления: 213₁₀ : 17₁₀ = 12₁₀ и 9₁₀ в остатке.

...поделить MOИ чиcла в двоичной системе

...к списку решаемых задач