Отправлено goshka 22 июня 2003 г. 19:29 В ответ на: нет файла. Ведь недавно читал где-то и потерял , так хорошо усе было написано :) отправлено whale 22 июня 2003 г. 18:29

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

Например: 
разделим число 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
   остаток                     00001
                                       -  0
                                          11
                                         -  0
                                           110
                                           -  0
                                           1100
                                        -  1100
                                           0000
Двоичное, как и десятичное деление, начинается с анализа делимого (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ХХХХ. Далее сдвигается первый остаток на один разряд влево и из него вычитывается делитель:
    0. 00011000
 + 1. 01000000
    1. 01011000  второй остаток
Остаток отрицательный, поэтому в следующий разряд частного записывается 0, С = 10ХХХ. Кроме того необходимо биты делителя вернуть обратно первому остатку, т.е. сложить делитель (в прямом коде) и второй остаток:
    1. 01011000
 + 0. 11000000
    0. 00011000   сдвинутый первый остаток.
Далее еще раз сдвигается сдвинутый первый остаток на один разряд влево и вычитается из него делитель:
    0. 00110000
 + 1. 01000000
    1. 01110000  третий остаток
Третий остаток отрицательный, значит следующий (третий) разряд частного равен 0, С = 100ХХ. Поэтому возвращаем делитель третьему остатку,
    1. 01110000
 + 0. 11000000
    0. 00110000   дважды сдвинутый первый остаток
Сдвигаем дважды сдвинутый первый остаток на один разряд влево и вычитаем делитель:
0. 01100000
1. 01000000
1. 10100000  четвертый остаток
Четвертый остаток опять отрицательный, поэтому С = 1000Х. Прибавляем делитель к четвертому остатку, результат сдвигаем на один разряд влево, а затем вновь вычитаем делитель:
    0. 1100000  первый остаток после четвертого сдвига
 + 1. 0100000
    0. 0000000  пятый остаток
Остаток положительный, значит С = 10001 = 17(10) - это и есть ответ.
Такой метод деления называется делением с восстановлением остатка.
Деление чисел, представленных в форме с фиксированной запятой можно также осуществить на двоичных сумматорах обратного и дополнительного кода.
Перед выполнением самой процедуры деления чисел в формате с фиксированной запятой определяется и запоминается знак частного. Далее оба операнда представляются в прямом коде, а делитель еще и в дополнительном для того, чтобы вычитание делителя заменить сложением, и выполняется сама процедура деления по описанному выше методу с обязательным контролем переполнения разрядной сетки. Если знак частного отрицательный, то ответ, при необходимости, представляется в дополнительном коде.
Например: разделим 35 на 5. 3510 = 0.1000112, 510 = 1012, 5д = 1.011д 
(в регистре С, как и в предыдущем примере, формируется частное):
    0.100011
 + 1.011000
    1.111011    С = 0 восстанавливаем остаток до делимого.
 + 0.101000
    0.100011     сдвигаем влево остаток.
    1.00011
 + 1.01100
    0.01111      С = 01, сдвигаем влево остаток.
    0.1111
 + 1.0110
    0.0101      С = 011, сдвигаем остаток.
    0.101
 + 1.011
    0.000       С = 0111 = 710 
Вычитание делимого продолжают столько раз, сколько разрядов отведено для частного.
Метод деления без восстановления остатка. Как уже отмечалось, основой выполнения деления является операция вычитания с целью получения остатка, знак которого определяет цифру частного. Алгоритм выполнения деления имеет следующий вид:
X - Y = a0,
где a0 - это остаток. Если а0  0, то С = 1, если а0 < 0, то С = 0. Для определения следующей цифры частного необходимо выполнить следующие действия: при а0  0 надо 2а0 - Y = a1, а при а0 < 0 надо 2а0 + Y = a1. Как видно в данном случае знак остатка определяет не только очередную цифру частного, но и характер следующей процедуры: прибавления делителя к сдвинутому остатку, если этот остаток меньше 0, и вычитание делителя из сдвинутого остатка, если остаток больше или равен 0. Этот метод деления получил название деления без восстановления остатка. 
Рассмотрим пример:
разделим 3510 на 510, т.е. 0.1000112 на 1012
        0.100011
    +  1. 011000   дополнительный код 5 (т.е. вычитание 5)
        1.111011   a0<0,  С = 0
2a0   1.110110
    +  0.101000    5 в прямом коде
        0.011110     a1>0,  С = 01
2a1   0.111100
    +  1.011000     5 в дополнительном коде (т.е. вычитание 5)
        0.010100    a2>0,  С = 011
2a2   0.101000
    +  1.011000
        0.000000    a3 = 0,  С = 0111 = 710 

• Спасибо ! Вся петрушка была в остатке, я немного спутал формат его на выходе и поэтому не сходилось :) — whale   (22.06.2003 19:41, пустое)