Правила двоичной арифметики сложение вычитание умножение. Двоичные числа и двоичная арифметика

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

Всё это время я говорил о том, что цифровые машины стали возможны благодаря простой идее о том, что любую информацию можно представить в виде последовательности из «0» и «1», т. е. закодировать её двоичным числом. При этом я умышленно умолчал о том, как «0» и «1» представляются внутри цифрового устройства. Для понимания основных идей информации было достаточно.

Но если задаться вопросом что такое на самом деле «0» и «1» в цифровом устройстве, то очевидный ответ будет звучать так:«электричество»! Да, «истина» и «ложь» в электронных устройствах кодируются с помощью напряжения (если ты забыл что это такое, то можешь просто воспринимать его как давление воды в трубе. Аналогия хоть и не точная, но зато понятная). На самом деле мы можем что угодно принять за «истину» или «ложь». Просто выбрать два разных значения и одно из них считать за «истину», а второе за «ложь».

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

Но вернёмся к электрическому представлению «0» и «1». Инженеры решили этот вопрос в лоб и просто приняли 0 вольт за «0», а за «1» напряжение большее ~2.5 вольт. Были придуманы простейшие схемы (логические элементы), сначала на электронных лампах и реле, а потом на транзисторах, которые умеют распознавать эти уровни напряжения и выполнять логические функции: И, НЕ, ИЛИ, И-НЕ и т. д. На основе этих схем были построены более сложные элементы: триггеры, счетчики, сумматоры, шифраторы и дешифраторы, мультиплексоры и демультиплексоры, регистры, - из которых в дальнейшем были созданы ещё более сложные устройства такие как АЛУ, ячейки памяти и многие другие необходимые блоки современных цифровых устройств.

Соглашение, когда 0В обозначает «0», а ~2.5В обозначает «1» принято называть положительной логикой. Если же принято наоборот (0В = «1», а 2.5В = «0»), то такое соглашение называют отрицательной логикой. Какой вариант использовать -- выбор разработчика. К тому же сейчас существует множество схем, которые работают и с другими напряжениями. В целом они делятся на два больших семейства: ТТЛ (TTL) и КМОП (CMOS). Существуют также более современные семейства LVTTL, LVCMOS. Не буду сейчас на них подробно останавливаться.

Системы счисления

Система счисления - это практически тоже самое, что алфавит для записи слов, только он служит для записи чисел. Двоичный алфавит состоит из цифр «0» и «1», а десятичный из 0, 1, 2, 3, 4, 5, 6, 7, 8 ,9. Восьмиричный из 0, 1, 2, 3, 4, 5, 6, 7. С помощью такого «численного алфавита» мы записываем все возможные числа. При этом все современные активно использующиеся системы счисления таковы, что для записи любого числа достаточно только тех цифр, что есть в выбранной системе счисления. При этом количество разных цифр в системе счисления называется её «основанием». Двоичная система имеет основание 2, десятичная -- 10, восьмиричная -- 8, шестандцатиричная -- 16, шестидесятиричная -- 60 и т.д.

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

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

D = d p-1 b p-1 + d p-2 b p-2 + ... + d 1 b 1 + d 0 b 0 .d -1 b -1 + d -2 b -2 + ... + d -n b -n

С помощью этой формулы можно записать как целое число, так и число дробное. p -- число знаков слева от точки, а n -- после запятой, а b -- это основание системы. Для примера запишем число 22.15:

22.15 = d 2-1 b 2-1 + d 2-2 b 2-2 .d -1 b -1 +d -2 b -2 = 2 1 10 1 + 2 0 10 0 .1 -1 10 -1 +5 -2 10 -2

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

Позиционные системы таковы, что если в результате сложения, полученное число превышает «основание», то мы добавляем новый разряд слева: 5+7 = 12, 11+99 = 110 и т.д. Эти правила сложения тебе известны со времен начальной школы. И они успешно применяются как десятичным, так и к двоичным числам.

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

Арифметика нулей и единиц

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

1 + 0 = 01 0 + 0 = 00 1 + 1 = 10 (+ 1 разряд переноса) = 10 1 * 1 = 01 1 - 1 = 00

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

Как видно сумма двух 8-разрядных чисел не всегда равна 8 разрядам. В этом примере мы получили 9! Ниже я показал, что произойдёт, если сложить два 8-разрядных числа в устройстве, которое умеет работать только с 8-разрядными числами, если забыть про перенос в старший разряд.

Мы потеряли самый старший разряд (9-й), который в результате сложения должен был быть равен «1»! Таким образом, реальное цифровое устройство всегда должно уметь учитывать перенос из младшего разряда в старший, иначе некоторые операции сложения всегда будут давать неверный результат.

Кстати, если представить, что число "11111111" -- это максимальное значение некоторого восьми разрядного счетчитка, то добавив к нему единицу мы получим переполнение счетчика и он обнулится.

роизвольное натуральное число можно единственным способом представить в виде суммы степеней двойки, например 23 = 16+4+2+1. Обозначая входящие в эту сумму степени двойки единицами, а не входящие в ее степени нулями, можно кратко обозначить эту сумму булевым набором (в другой терминологии - вектором) (10111) 2 . Индекс 2 напоминает о том, что число записано в двоичной системе. Единица, стоящая в младшем (самом левом) разряде, означает слагаемое 1, единица во втором слева разряде означает слагаемое 2, единица в третьем разряде означает 4, а нуль в четвертом разряде означает отсутствие слагаемого 8, единица в четвертом (старшем) разряде означает присутствие слагаемого 16 (в большинстве случаев разумно рассматривать только такие записи чисел в двоичной системе, в которых в старшем разряде стоит единица).

Главное достоинство двоичной системы (помимо естественности ее применения в электронной цифровой технике) - исключительная простота алгоритмов арифметических операций в ней. Таблица умножения в двоичной системе совсем не требует запоминания: любое число, умноженное на нуль дает нуль, а умноженное на единицу равно самому себе. Правило деления сводится к двум равенствам 0/1 = 0, 1/1 =1, благодаря чему деление столбиком в двоичной системе делается проще, чем в десятичной, и по существу сводится к многократному вычитанию. Таблица сложения в двоичной системе чуть сложнее таблицы умножения (в отличие от десятичной системы), так как 1+1 = (10) 2 и возникает перенос в следующий разряд.

Правило сложения двух битов в двоичной системе задается формулами x+y = 2v+u, v = x&y, u = xÅy. В силу симметрии для их проверки достаточно рассмотреть не четыре, а три случая: 0+0 = (00) 2 , 1+0=0+1= (01) 2 , 1+1 = (10) 2 . Схема, выполняющая это сложение, называется полусумматором (в англоязычной литературе: half adder) и обозначается обычно HA или FA2. Эта схема (в базисе {AND, XOR}) изображена на рисунке.

Схемы для арифметических операций над многоразрядными двоичными числами. Сложение двух n-разрядных двоичных чисел (x n ,….,x 1) 2 и (y n ,….,y 1) 2 как и в десятичной системе приводит к появлению переносов в следующий разряд, которые необходимо учитывать в вычислении. Эти переносы также равны нулю или единице (если перенос равен нулю, то в ручном вычислении он фактически не выполняется, но логическая схема обязана правильно работать и в этом случае, ведь она «не знает», какой перенос пришел из предыдущего разряда). Обозначим перенос из (i-1)-го разряда в следующий i-й разряд через w i (w 1 =0, потому что предыдущего разряда в этом случае просто нет). Тогда для вычисления z i (i-го бита результата) нужно сложить биты x i и y i и бит переноса w i . Это сложение выполняем по формулам

x i + y i +w i = 2v i +u i , v i =m(x i ,y i ,w i), u i =l(x i ,y i ,w i)

с помощью схемы FA3. Тогда z i =u i =l(x i ,y i ,w i), а следующий бит переноса w i +1 = v i =m(x i ,y i ,w i). При сложении n-разрядных чисел получается вообще говоря n+1-разрядное число. Его старший бит z n +1 = w n +1 равен последнему переносу.

Схема сложения трехразрядных чисел приведена на следующем рисунке. Аналогичным образом выглядит и схема сложения n-разрядных чисел.

Сложность указанного n-разрядного сумматора равна 5n-3. Н.П.Редькин доказал, что сумматоров для n-разрядных чисел меньшей сложности в базисе {AND,OR,XOR,NOT} не существует. Построенный сумматор является поэтому минимальной схемой. Но у этой схемы есть существенный недостаток - она имеет большую глубину. Глубиной схемы называется максимальное число ее элементов, образующих цепь, соединяющую какой-либо из входов схемы с одним из ее выходов. Например, глубина указанной выше схемы FA3 равна 3.

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

Теоретически вычислить задержку реальной схемы очень сложно. Цепей элементов схемы, соединяющих ее входы с выходами (эти цепи также называют путями), обычно довольно много и задержка схемы определяется задержкой по самому плохому в определенном смысле пути, который называется критическим. Например, на схеме FA3 критический путь, вероятно, соединяет входы X или Y с выходом m. Задержка по любому пути определяется не только суммой задержек всех элементов, лежащих на этом пути (в приведенном примере она равна 3, если считать задержку каждого элемента единичной). Следует учитывать также задержку соединяющих эти элементы проводов. Задержка элемента зависит от того, между каким его входом и каким его выходом она измеряется, а также от электрических характеристик самого элемента и элементов непосредственно с ним связанных в рассматриваемой схеме, она зависит от температуры схемы и даже от того, какие логические значения подаются в рассматриваемый момент на входы этого элемента и изменяется ли (и в какую сторону) значение на его выходе. Тем не менее, хотя и не очень точно, задержку пути можно оценить как сумму задержек его элементов. Если задержки всех элементов равны, то эта величина определяется глубиной схемы. Разумеется, понятие глубины схемы можно расширить, допустив, что элементы базиса могут иметь произвольные неотрицательные задержки.

Глубина указанной выше схемы n-разрядного сумматора на первый взгляд равна 3n-2. Но внимательный анализ возможных критических путей показывает, что она на самом деле равна 2n-1. Все равно это очень много и построенная таким образом реальная схема будет иметь большую задержку. На практике используются схемы, имеющие одновременно малую сложность, не превосходящую Cn (где С - небольшая константа) и малую глубину, приблизительно равную 2log 2 n. В.М. Храпченко в 1970 г. построил схему малой сложности и глубины, асимптотически равной log 2 n (т.е. равную (1+ e(n)) log 2 n, где e(n) стремится к нулю с ростом n). Он же недавно доказал, что глубина сумматора не может быть меньше log 2 n + log 2 n (log 2 (log 2 n))). Поэтому построенная им схема имеет асимптотически минимальную глубину. Однако схема Храпченко превосходит обычные схемы только при n порядка тысячи. Тем не менее существует некоторая модификация его схемы с глубиной приблизительно равной log j n, где j = (Ö5+1)/2, и эта схема имеет глубину меньшую, чем стандартные схемы, уже начиная с n = 8. В 2008 г. М.И.Гринчук построил схему глубины не большей log 2 n+log 2 (log 2 n)+6, которая уже при малых n имеет меньшую глубину, чем все известные схемы.

Задача построения оптимальных схем для умножения n-разрядных чисел оказалась еще труднее, чем задача о построении оптимальных сумматоров. Легко построить схему для умножения n-разрядных чисел в базисе {OR,AND,XOR,NOT} сложности приблизительно равной 6n 2 . Для этого можно использовать указанную выше схему для сумматора. Однако ее глубина будет велика. В начале 60-х годов несколько исследователей (в СССР Столяров и Офман, в США Авиценис и Уоллес) независимо построили схему для умножения сложности порядка n 2 и глубины порядка log 2 n. В смысле глубины эти схемы по порядку оптимальны, но до сих пор остается нерешенной задача построения схемы для умножения асимптотически минимальной глубины. В смысле сложности эти схемы оказались далеки от оптимальных. А. А. Карацуба построил в 1962 г. схему для умножения, имеющую сложность по порядку не большую n 1,6 , потом А. Л. Тоом построил схему сложности n 1+ e(n) , где e(n) стремится к нулю с ростом n. В определенном смысле этот результат окончательный, тем не менее он был уточнен на рубеже 70-х годов немецкими математиками А. Шенхаге и Ф. Штрассеном, которые получили для схем умножения верхнюю оценку сложности по порядку не превосходящую n log 2 n log 2 (log 2 n), а в 2008 г. эту оценку улучшил американский математик М. Фюрер, заменивший двойной логарифм крайне медленно растущей функцией. Есть предположение, что сложность схемы умножения по порядку не меньше n log 2 n, но и это не доказано.

Американский математик С.Кук доказал, что можно построить схему для деления 2n-разрядного числа на n-разрядное, у которой сложность по порядку не превосходит сложности умножения n-разрядных чисел. Известно также, что нижняя оценка сложности схемы для деления по порядку не меньше нижней оценки сложности умножения. Поэтому в смысле оценок сложности деление не представляет ничего нового в сравнении с умножением. Однако долгое время наилучшей оценкой глубины деления по порядку было (log 2 n) 2 .

Впоследствии были найдены схемы для деления с глубиной по порядку равной log 2 n, но их сложность оказалась велика. Американцы Рейф и Тейт построили схемы для деления глубины по порядку не превосходящей log 2 n log 2 (log 2 n) и одновременно сложности по порядку не превосходящей n log 2 n log 2 log 2 n, однако и эти схемы, как и схемы Шенхаге-Штрассена и Фюрера пока не нашли практических применений, так как в действительности начинают превосходить используемые на практике схемы лишь при огромных значениях n.

Рекомендуемая литература

1. О.Б. Лупанов « Асимптотические оценки сложности управляющих систем » изд. МГУ, 1984.
2. О.Б. Лупанов «Конспект лекций по математической логике »изд. МГУ, 2009.
3. Дж. Сэвидж «Сложность вычислений » М. изд. Факториал, 1998.
4. Д. Кнут « Искусство программирования на компьютере», т. 2, изд. Вильямс, 2000.
5. С.Б. Гашков «Системы счисления и их применения », М. изд. МЦНМО, 2004.
6. С.Б. Гашков, В.Н. Чубариков «Арифметика. Алгоритмы. Сложность вычислений », изд. Дрофа, 2005.

Арифметические операции над двоичными числами осуществляются с помощью алгоритма под названием «сложение в столбик». Правила выполнения арифметических действий над двоичными числами задаются таблицами двоичных сложения, вычитания и умножения (табл. 1.31).

Таблица 1.31. Арифметические операции над двоичными числами

Пр и мер 1.60. Произвести сложение чисел 55,25 и 19,5 в десятичной и в двоичной системах счисления.

Первое слагаемое 55 , 25 1 1 0 1 1 1,0 1

Второе слагаемое 19 , 50 1 0 0 1 1,1 0

Образующийся дополнительный бит называется битом переноса.

Пр и мер 1.61. Произвести сложение чисел 65 и 42 в двоичной системе счисления.

• 65 10 = 01000001 2 .
• 42 10 = 00101010 2 .

Выполним сложение этих чисел:

01000001 Первое слагаемое

00101010 Второе слагаемое 01101011 Результат

Можно убедиться, что (01101011) 2 = (107) 10:

0 2 7 + 1 2 6 + 1 2 5 + 0 2 4 + 1 -2 3 + 0-2 2 + 1 -2" + 1 -2° = = 64 + 32 + 8 + 2+ 1 = 107.

Пр и мер 1.62. Выполнить сложение двоичных чисел X и У. а) Х= 1101; У= 101.

Результат. 1101 + 101 = 10010. б)Х= 1101; У= 101; 7= 111.

х+у+г= 110 0 1

Примечание. Вычитание чисел в двоичной системе счисления выполняется так же, как и в десятичной. При необходимости занимается единица из следующего старшего разряда, причем занимаемая единица равна двум единицам данного разряда. Заем единицы производится каждый раз, когда цифра в разряде вычитаемого количественно больше цифры в том же разряде уменьшаемого. Для выполнения операции вычитания она заменяется сложением, а в качестве второго слагаемого берется инвертированное (противоположное) число. Например, пусть нужно выполнить вычитание: 65 - 42. Заменим его сложением: 65 + (-42).

И так, мы уже знаем, что такое двоичная система исчисления. Двоичная система - это такая же полноценная система исчисления, как и хорошо всем нам знакомая десятичная. В двоичной системе, как и в любой другой системе исчисления возможны все арифметические операции, к которым мы привыкли в десятичной системе. То есть сложение, вычитание, умножение, деление. Рассмотрим, каждую из арифметических операций на конкретных примерах.

Сложение

Допустим нам нужно найти сумму двух двоичных чисел: 10011001110 + 11000101110. Как это сделать. Правила сложения двоичных чисел такие же, как и для десятичных. С той только разницей, что каждый разряд суммы может принимать только два значения - ноль или единица. Точно так же, как и в десятичной системе, для сложения чисел их удобно записать в столбик:

Сложение чисел нужно производить поразрядно, начиная с младшего разряда. При этом применяется следующее правило: Ноль плюс ноль получится, естественно ноль. Один плюс ноль и ноль плюс один дадут в результате один. При сложении двух единиц мы получим ноль в текущем разряде и единицу переноса в старший разряд. При сложении трех единиц (с учетом единицы переноса с предыдущего разряда) получим единицу в текущем разряде и единицу переноса. Эти правила объеденены в так называемой таблице сложения:

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

Умножение

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

Точно так же, как и при умножении двоичных чисел, мы умножаем первое число на каждый разряд второго и записываем полученные результаты под первой чертой, одно под другим со здвигом. Затем полученные промежуточные результаты мы складываем с учетом сдвига. Однако в случае с двоичными числами имеется одно существенное отличие. Так как любой разряд двоичного числа либо ноль, либо единица, то промежуточное умножение сильно облегчается. В самом деле, любое число, умноженное на единицу, равно самому себе. Любое число, умноженное на ноль, равно нулю! Поэтому тут и вычислять то ничего не нужно. Именно по этому умножение двух двоичных чисел сводится к операциям сдвига и сложения. Это очень важно для построения вычислительных машин. Теперь ясно, что нам не нужны какие нибудь там "умножители". Для реализации операций сложения и умножения нам нужны только сумматоры и сдвиговые регистры. С их устройством вы можете познакомиться на нашем сайте.

Вычитание

Для того, что бы упростить операцию вычитания, был придуман так называемый “дополнительный код”. Можно сказать, что при помощи этого кода записываются отрицательные числа. Для того, что бы записать двоичное число в дополнительном коде, необходимо проинвертировать все его разряды а затем прибавить единицу. Инвертировать разряд двоичного числа - это, значит, заменить его содержимое на противоположное. (Ноль на единицу, а единицу на ноль). Ниже в таблице приведены примеры перевода различных чисел в дополнительный код. В каждой строке таблицы вы видите одно и то же число записаное сначала в десятичной системе исчисления, затем в двоичной системе в прямом коде, затем инвертированный прямой код, а затем в дополнительном коде.

Правила перевода числа из десятичного представления в двоичное читайте в разделе «Системы исчисления».

Правило вычитаия двух двоичных чисел гласит:
для того, что бы вычесть одно число из второго, необходимо:

• Перевести вычитаемое в дополнительный код.
• Сложить эти два числа (уменьшаемое и вычитаемое в дополнительном коде).
• При сложении перенос из самого старшего разряда не учитывать.
• Полученный результат и есть разность.

Поясним это на примере. Допустим, нам нужно найти разность между числами 13 и 5, в двоичной системе исчисления. Переведем сначала искомые числа в двоичную систему:

Число 13 берем в прямом двоичном коде (00001101).

Число 5 переводим в дополнительный двоичный код 5 (11111011).

Теперь производим сложение:

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

Для проверки переведем полученный результат в десятичный вид. 1000 в двоичной системе это 8 в десятичной. Советую внимательно проверить приведенный пример в соответствии с таблицей сложения (см выше).

Умножение и деление на 2

Аналогично происходит делениена 2. Только наоборот. Для того, что бы разделить двоичне числа на 2 (двоичное 10) нужно просто отбросить ноль в младшем разряде числа и все остальные разряды сдвинуть на один разряд вправо. Если в младшем разряде искомого числа не ноль, а единица, то это значит, что число не делится на два нацело. В этом случае возможно деление с остатком.

Примечание: Вы можете сами потренироваться в умножении на два с другими числами. О переводе из десятичного представления числа в двоичное смотри здесь.

Деление на произвольное число

Вспомним как мы делим одно число на другое в десятичной системе исчисления. Я имеется в виду деление столбиком или углом. Точно так же происходит деление в двоичной системе. Вот пример деления двух двоичных чисел:

Сначала мы записываем делимое. В данном случае это число 1000001 (в десятичном виде 65). Затем, справа от него, рисуем угол. В верхней части угла записываем делитель. В нашем случае – это 101 (десятичное 5). Затем мы начинаем находить частное по разрядно. В десятичной системе исчисления в данном случае мы подбираем, на какое число от 1 до 9 нужно умножить делитель, для того, что бы результат был бы все же меньше, чем три первые разряда делимого. Если такого числа не находится, то берут первые четыре разряда делимого. В двоичной системе исчисления любой разряд может принимать только два значения – ноль или единица. Поэтому выбор у нас гораздо меньший. Делитель можно умножать только на 1 либо на ноль. При этом в первом случае он останется неизменным, а во втором он будет равен нулю. Нам придется лишь проверять не больше ли делитель, чем число, составляющее первые три разряда делимого. Как видим первые три разряда составляют число 100, что меньше, чем 101. Поэтому берем первые четыре разряда делимого. Число, составляющее первые четыре разряда делимого (1000) естественно больше делителя. Поэтому мы записываем делитель под первыми четырьмя разрядами делимого и вычитаем эти два числа. Получаем разность 11. В первый разряд частного записываем 1.

Находим следующий разряд частного. Для этого сносим следующий разряд делимого (так же, как это делается при делении в десятичной системе). Проверяем – можно ли теперь вычесть из него 101. Число 110 больше, чем 101. Поэтому мы записываем единицу в следующий разряд частного и производим вычитание этих двух чисел. Разность равна 1.

Далее ищем третий разряд частного. Сносим еще один ноль с очередного разряда делимого. Но из числа 10 невозможно вычесть 101. 10 меньше, чем 101. Поэтому записываем в очередной разряд частного ноль и сносим последний разряд делимого. Теперь вычитание возможно. Более того, результат вычитания равен нулю. Это означает во первых, что последний разряд частного равен единице, а во вторых то, что число 1000001 поделилось на 101 без остатка. Результат деления равен 1101 (десятичное 13).

Заключение

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

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

Правила двоичной арифметики

Сложение и вычитание двоичных чисел основаны на правилах этих действий в пределах одного разряда и правилах учета межразрядных переносов и займов.

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

Таблица 3.1

Правила арифметических операций

Перенос, возникающий в i -м разряде, передается в следующий (i +1)-разряд с увеличенным вдвое весом и уменьшенным вдвое значением.

Заем из (i +1)-го разряда передается в i-й разряд с уменьшенным вдвое весом и увеличенным вдвое значением.

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

При вычитании двоичных чисел (см. табл. 3.1) в данном разряде при необходимости занимается единица из соседнего (старшего) разряда. Эта занимаемая единица равна двум единицам данного разряда. Заем производится каждый раз, когда цифра в разряде вычитаемого больше цифры в том же разряде уменьшаемого. Например, при вычитании:

единица из разряда с весом 2 4 была занята в разряд с весом 2 3 ; эта единица стала там двойкой, и в разряде с весом 2 3 выполнилось вычитание 10-1 = 1; на месте разряда с весом 2 4 в уменьшаемом фактически остался нуль.

Распространение займа сразу на несколько более старших разрядов можно проследить на примере вычитания чисел 101110,001 (2) и 101,011 (2) . Записав числа друг под другом:

нетрудно заметить, что в разряде с весом 2 -2 в результате вычитания должен произойти заем из разряда с весом 2 1 . Перепишем пример с учетом фактического расположения цифр после заема и выполним вычитание. Вместо зачеркнутых цифр необходимо использовать в качестве уменьшаемого надписанные цифры. Окончательный результат (разность) составляет 101000,110 (2) .

Пример . Уменьшаемое 1000000 (2) , вычитаемое 1 (2) , разность составляет

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

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

В основном арифметические операции выполняются на одном общем устройстве, называемом арифметико-логическим устройством (АЛУ).

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