Как выполняется деление двоичных чисел
Системы счисления. Арифметические действия в двоичной системе счисления
Цель: научить учащихся выполнять арифметические действиями в двоичной системе счисления.
Задачи:
образовательные:
— повторение и закрепление знаний учащихся о системах счисления;
— формировать у школьников умение выполнять правильно арифметические действия в двоичной системе счисления;
развивающие:
— развивать логическое мышление учащихся;
— развивать познавательный интерес учеников.
Содержание нового материала: правила сложения, умножения, вычитания и деления в двоичной системе счисления.
Ход урока.
Изучение нового материала.
Правила сложения:
0+0=0
0+1=1
1+0=1
1+1=10
Обратить внимание учащихся на то, что при сложении двух единиц в двоичной системе счисления в записи получается 0, а единица переносится в следующий разряд. При сложении трех единиц получается в записи 1, и единица переносится в следующий разряд. (1+1+1=11).
Пример 1.
101+10=111
Пример 2.
10011+11=1110
Учащиеся самостоятельно решают следующие примеры:
1001+11=1100
110+110=1100
Правила умножения:
0*0=0
0*1=0
1*0=0
1*1=1
Пример 1.
101*11=1111
Пример 2.
1011*101=110111
Учащиеся самостоятельно решают следующие примеры:
1001*101=101101
1001*11=11011
Правила вычитания:
0-0=0
1-0=1
1-1=0
0-1=-1
Обратить внимание учащихся на то, что «минус» в последнем правиле обозначает – «занять разряд (1)».
Пример 1.
10110-111=1111
Объяснение:
Вычитание выполняется так же, как в математике. Если цифра в уменьшаемом меньше цифры вычитаемого, то для данного вычитания необходимо занять разряд (1), т.к. 10-1=1. Если слева от такого вычитания стоит 0, то мы не можем занять разряд. В этом случае разряд занимаем в уменьшаемом у близстоящей слева от данного вычитания единицы. При этом все нули, у которых мы не могли занять разряд, необходимо поменять на единицу, т.к. 0-1=-1. Желательно все изменения в цифрах записывать сверху данного вычитания. Дальнейшее вычитание выполнять с получившимися сверху цифрами.
Пример 2.
100000-11=11101
Учащиеся самостоятельно решают следующие примеры:
100010-100=
101011-10111=
Правило деления:
Деление выполняется по правилам математики, не забывая, что мы выполняем действия в двоичной системе счисления.
Пример 1.
101101:1001=101
К вопросу о делении
Нам подвернулась возможность провести небольшое, но крайне интересное тактическое учение
В процессе исследований нового МК от известной фирмы на основе архитектуры Cortex-М4 (я об этом обязательно еще напишу) возник вопрос, насколько быстро может работать операция целочисленного деления в аппаратной реализации. Натурный эксперимент дал несколько неожиданный результат: деление 32-разрядного числа на 32-разрядное выполняется за 3 такта частоты процессора — ну ни фига ж себе, как быстро. Выяснилось, что это имеет место только с определенными операндами, но дальнейшие исследования показали, что никогда время выполнения деления не превосходит 7 тактов. Полученные результаты вызвали легкую оторопь («и это не некая фигура речи, которая неизвестно что означает, а вполне конкретный глагол» — Дивов, как всегда, бесподобен).
Ну нельзя же просто так взять и быстро поделить такие длинные числа, странно как то, но факты — упрямая вещь. Представил себе картину, что вызывает меня завтра к себе Президент РФ и ставит передо мной задачу сделать МК не хуже, чем у ARM (согласен, что картина бредовая, но чего на свете не бывает), а я растеряно на него гляжу и понимаю, что не смогу сделать такое деление таких чисел за такое время, и не оправдаю ожиданий, на меня возлагаемых (ну на самом то деле я всегда смогу втихую купить лицензию у ARM, и сделать вид, будто бы придумал все сам, многие так и делают, но от меня то ВВП ждет совсем другого, да и потом — его то я обмануть смогу, а вот себя вряд ли).
И стало мне грустно, что в ARM сидят ребята намного умнее меня, и пошел я с тоской во взоре подглядеть в Инете, как они это делают. На сайте ARM никакой информации по времени исполнения не нашел, в одном из материалов по STM32 было указано, что деление занимает от 2 до 7 тактов, что соответствует наблюдениям, но информации о том, как это делается, нет.
В общем, Инет всемогущий особо не помог, есть трюки с делением на константу, сам о них писал в одном из постов, но у нас иная ситуация, есть алгоритм Ньютона и ускоренная его версия, но это явно не по делу, есть алгоритм на основе преобразования Фурье, но это для очень больших чисел и вряд ли выполнится за 7 тактов даже на архитектуре ARM. Пришлось придумывать самому и решение было найдено, причем настолько простое и очевидное, что становится несколько неловко от того, что это не было сделано мгновенно после формулировки задачи.
Прежде, чем смотреть мое решение, предлагаю Вам найти свое самостоятельно, а потом сравните с моим, и, если они отличаются то жду Вас в комментариях.
Итак, как нам быстро (не более, чем за 7 тактов) поделить два 32-разрядных числа с получением 32-разрядного результата.
Для начала вспомним, как вообще осуществляется деление в двоичной арифметике в
классической форме. Алгоритм достаточно прост и понятен — вычитаем делитель из делимого. Если результат неотрицателен (делим без-знаковые числа), то очередной разряд результата делаем равным единице и результат рассматриваем, как следующее делимое, в противном случае очередной бит результата равен 0. Перед следующим тактом уменьшаем делитель в два раза (либо сдвигаем его вправо, либо сдвигаем влево делимое) и уменьшаем вес бита в 2 раза (аналогичными сдвигами). Таким образом, мы получаем за один такт один бит результата и вся операция продлится 32 такта. В этом процессе есть еще начальный сдвиг, но на оценку ситуации в целом он не влияет. Будем ускорять, но как?
Обратим внимание, что полученный алгоритм сильно напоминает работу АЦП с последовательным приближением и вспоминаем, что есть и другой метод преобразования, намного более быстрый — параллельное преобразование. А что, если…
Будем вычитать из делителя не только делимое, но и делимое*2 и делимое*3 (одновременно, на трех сумматорах), тогда мы получим три бита (знаки результатов) информации, которые принимают 4 различных значения, значит из них можно извлечь сразу 2 бита результата. Далее экстраполируем подобный подход для 3,4,5 бит результата.
Чтобы получить 5 бит информации за один такт, нам потребуется 31 сумматор, на каждом из которых будет выполняться операция Делимое-Делитель*н(1-31), знаки результата пропускаем через шифратор и получаем сразу 5 бит результата. Затем сдвигаем делимое на 5 разрядов влево и повторяем до готовности. Тогда нам потребуется 32/5=6.4=>7 тактов для полного завершения операции.
Так что задача поделить за 7 тактов решена, остается вопрос – как можно ли сократить данное время, ведь в исследуемом МК оно бывает меньше 7. Напрашивающееся решение — на этапе подготовки алгоритма определить номер старшего значащего разряда делимого (Ч) и делителя (З) и сразу станет ясно, сколько старших битов частного равны нулю, так что мы можем пропустить первую либо несколько фаз алгоритма. Например, если Ч
Практическая работа №5. Операция деления чисел в ЭВМ
Практическая работа №5
Операция деления чисел в ЭВМ
Целью работы является изучение деления чисел как с фиксированной, так и с плавающей точкой в ЭВМ.
2. Теоретическая часть
2.1. Умножение и деление чисел в двоичной системе счисления.
Наиболее просто умножение выполняется в прямом коде, независимо от того, являются ли операнды целыми или дробными числами. В ЭВМ с фиксированной точкой умножение реализуется в два этапа.
Первый этап заключается в определении знака произведения с помощью сложения знаковых цифр сомножителей по модулю два, где 0 – соответствует плюсу, а 1 – минусу.
Сложение по модулю два
По-другому, это эквивалентно
На втором этапе производится перемножение модулей сомножителей, затем в случае необходимости округления полученного модуля произведения, после чего к модулю результата приписывается его знак, определенный на первом этапе.
Умножение производится по обычным правилам арифметики, согласно двоичной таблицы умножения.
Традиционная схема умножения похожа на известную из школьного курса процедуру записи «в столбик». Вычисление произведения двух n-разрядных двоичных чисел без знака сводится к формированию частичных произведений (ЧП) по одному на каждую цифру множителя, с последующим суммированием полученных ЧП. Перед суммированием каждое частичное произведение должно быть сдвинуто на один разряд относительно предыдущего.
Деление чисел в двоичной системе производится аналогично делению десятичных чисел. Рассмотрим деление двух целых чисел, так как делимое и делитель всегда могут быть приведены к такому виду путем перенесения запятой в делимом и делителе на одинаковое число разрядов и дописывания необходимых нулей. Деление начинается с того, что от делимого слева отделяется минимальная группа разрядов, которая, рассматриваемая как число, превышает или равна делителю. Дальнейшие действия выполняются по обычным правилам, прием последняя целая цифра частного получается тогда, когда все цифры делимого исчерпаны.
2.2. Умножение двоичных чисел в ЭВМ. Машинный метод.
Умножение двоичных чисел сводится к операциям сдвига на один двоичный разряд влево и повторения первого сомножителя в тех разрядах, где второй сомножитель содержит 1, и сдвига без повторения в разрядах с 0. Сдвиг всегда чередуется со сложением, поскольку для выполнения операций имеется всего два регистра (два места для записи чисел). Другими словами, реализации отдельной операции умножения в процессоре не требуется.
Как и в операции сложения, при умножении чисел с ограниченной разрядной сеткой может возникнуть переполнение.
Перемножение двух n-разрядных двоичных чисел P=A*B приводит к получению результата, содержащего 2n битов. Таким образом, алгоритм умножения предполагает последовательное выполнение двух операций – сложения и сдвига. Суммирование ЧП обычно производится не на завершающем этапе, а по мере их получения. Это позволяет избежать необходимости хранения всех ЧП, то есть сокращает аппаратурные издержки. Устройство умножения предполагает наличие регистров множимого, множителя и суммы частичных произведений, а также сумматора ЧП и, возможно, схем сдвига (если операция сдвига не реализована иным способом).
Существуют следующие алгоритмы умножения:
Рассмотрим пример умножения двоичных чисел в ЭВМ.
Выполнить умножение чисел A = 101112 и B = 1012 в двоичной системе счисления.
Умножение выполняется в несколько этапов:
1. Впишем множимое A, допустим в 8-ми разрядный регистр, начиная с младших разрядов (нумерация разрядов начинается с нуля). В недостающие разряды записываем нули.
2. Впишем множитель В в 8-ми разрядный регистр, начиная с младших разрядов. В недостающие разряды записываем нули.
3. Подготовим (обнулим) регистр результата C удвоенной разрядности (16 бит). Произведение содержит в два раза больше разрядов чем исходные сомножители.
4. Дальше выполняется следующий цикл:
4.1. Анализируем очередной разряд множителя В (начинаем с младших), если он «1», то прибавляем множимое A к старшим разрядам регистра С, результат снова в С. Если очередной разряд множителя «0», пропускаем данный шаг.
4.2. Сдвигаем содержимое регистра С на один разряд вправо. При этом крайний левый (старший) разряд заполняется нулем. Но если перед этим была операция сложения, во время которой возник перенос из старшего разряда, то тогда крайний левый разряд заполняется единицей.
4.3. Действия, описанные в п. п. 5.1 и 5.2,повторяютсядо тех пор не будут проанализированы все разряды множителя.
В итоге процесс умножения выглядит следующим образом:
5. Определяется знак результата. Если знаки исходных сомножителей одинаковы, то результирующее произведение положительно и наоборот. В данном случае знаки совпадают, следовательно результирующее произведение положительно.
В итоге получается ответ: 
2.3. Деление двоичных чисел в ЭВМ. Машинный метод.
Рассмотрим процесс деления двоичных чисел в ЭВМ на примере деления числаА=100101112 на B=1012, который включает следующие этапы:
1. Впишем делимое A в 16-ти разрядный регистр, начиная с младших разрядов (нумерация разрядов начинается с нуля). В недостающие разряды записываем нули.
2. Впишем делитель В в 16-ти разрядный регистр, начиная с младших разрядов. В недостающие разряды записываем нули.
Здесь также как и с числом A 15-й разряд является знаковым, а старшим разрядом числа является 14-й разряд. Эти знаковые разряды будут показывать нам знаки, образующихся в процессе деления, частичных остатков. Они не имеет никакого отношения к знакам исходных операндов и знаку результата, а играют чисто технологическую роль.
4. Так как в процессе деления множитель B придется не только прибавлять но и вычитать, то нам необходимо иметь число -B. Для этого представим B в дополнительном коде.
5. Процесс деления будет следующий:
5.1. Вычитаем из делимого А делитель В (т. е. прибавляем -В).
5.2. Анализируем знак полученного частичного остатка (15-й разряд). В регистр результата записываем «0» если остаток отрицательный и единицу в противном случае. Помним, что отрицательному числу соответствует наличие единицы в 15-м разряде и наоборот.
5.3. Сдвигаем частичный остаток на один разряд влево. При этом крайний правый (младший) разряд заполняется нулем, а знаковый разряд (15-й) в процессе сдвига не участвует.
5.4. Прибавляем к частичному остатку делитель В если остаток отрицательный либо вычитаем делитель в противном случае.
5.5. Анализируем знак полученного частичного остатка (15-й разряд). В регистр результата записываем «0» если остаток отрицательный и единицу противном случае.
5.6. Действия, описанные в пунктах 5.3-5.5, выполняем k раз (если k=0, то ни разу не выполняем). Но, если после очередной операции сложения/вычитания частичный остаток, по модулю, будет меньше чем исходный (несдвинутый) делитель, то операция деления прекращается, а частное дополняется нулями так, чтобы число разрядов частного равнялось k+1.
В итоге процесс деления для вышеуказанного примера будет выглядеть следующим образом:
Арифметические операции в двоичной системе
Арифметические действия в двоичной системе производится по тем же правилам что и в десятичной системе счисления. Однако так как в двоичной системе счисления используются только две цифры 0 и 1, то арифметические действия выполняются проще, чем десятичной системе.
Сложение двоичных чисел.
Сложение выполняется поразрядно столбиком, начиная с младшего разряда и используя таблицы двоичного сложения:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10.
При сложении необходимо помнить, что 1+1 дают нуль в данном разряде и единицу переноса в старший.
Пример 3.5. Сложить два числа:
Вычитание двоичных чисел.
Вычитание выполняется поразрядно столбиком, начиная с младшего разряда и используя таблицы двоичного вычитания:
0 – 0 = 0
1 – 0 = 1
1 – 1 = 0
10 – 1 = 1.
Пример 3.6. Найти разность двух чисел:
Т.е. при вычитании двоичных чисел в случае необходимости занимается 1 из старшего разряда, которая равна двум единицам младшего разряда.
Умножение двоичных чисел.
Как видно из приведенных примеров, операция умножения может быть представлена как операции сдвига и суммирования.
Деление двоичных чисел.
Деление в двоичной системе производится вычитанием делителя со сдвигом вправо, если остаток больше нуля.
Пример 3.8. Найти частное двух чисел если:
1. Делимое больше делителя:
2. Делимое меньше делителя:
Как видно из приведенных примеров, операция деления может быть представлена как операции сравнения, сдвига и суммирования.
Вернуться в оглавление:Алгоритмические языки
Двоичный калькулятор онлайн
Данный калькулятор может производить следующие действия над двоичными числами:
Сложение двоичных чисел
Сложение двух двоичных чисел производится столбиком поразрядно. Начиная с младшего разряда (справа на лево), как и при сложении столбиком десятичных чисел. Но так как цифр всего две (0 и 1), их сложение происходит по следующим правилам:
Пример
Для примера сложим 1011 и 101:
| + | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | ||
| 1 | 0 | 0 | 0 | 0 |
Вычитание двоичных чисел
Вычитание двоичных чисел производится аналогично сложению – столбиком, но по следующим правилам:
Пример
Для примера вычтем из числа 1011 число 101:
| − | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | ||
| 1 | 1 | 0 |
Умножение двоичных чисел
Умножение двоичных чисел производится в столбик аналогично умножению в десятичной системе, но по следующим правилам:
Пример
Для примера перемножим числа 1011 и 101:
| × | 1 | 0 | 1 | 1 | |
| 1 | 0 | 1 | |||
| + | 1 | 0 | 1 | 1 | |
| 0 | 0 | 0 | 0 | ||
| 1 | 0 | 1 | 1 | ||
| 1 | 1 | 0 | 1 | 1 | 1 |
Деление двоичных чисел
Внешне деление двоичных чисел похоже на деление десятичных чисел, но тут есть свои нюансы: такое деление производится вычитанием делителя со сдвигом вправо, если остаток больше нуля. Чтобы понять этот процесс рассмотрим пример: