Введение в двоичную арифметику

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

Таблица 1.1. Таблица сложения одноразрядных двоичных чисел

Из табл. 1.1 видно, что результат сложения двух одноразрядных чисел является двухразрядным (двузначным) числом, а результат сложения двух N-разрядных — N+1 -разрядным. Образующийся дополнительный бит называется битом переноса (carry bit).
При сложении двоичных чисел в столбик мы выписываем их друг под другом (пример 1.1). Два младших разряда мы складываем в соответствии с табл. 1.1. При сложении последующих двух разрядов мы должны учитывать не только эти разряды, но и бит переноса из младшего разряда, т. е. производить сложение в соответствии с табл. 1.2. Из этой таблицы видно, что для трех одноразрядных слагаемых все равно получается только два бита суммы, так что для работы со всеми последующими разрядами мы можем обойтись только одним битом переноса (рис. 1.1).

Таблица 1.2. Таблица сложения с учетом переноса

Пример 1.1. Сложение двух 8-разрядных чисел (83 + 56 = 139)

Рис. 1.1. 8-разрядный двоичный сумматор

Дополнительный, 9-й разряд, образующийся при сложении 8-разрядных чисел, переносится в специальный бит слова состояния процессора, который также называется битом переноса, и обычно обозначается буквой С (от англ, саrrу — перенос). Этот бит можно использовать как условие в командах условного перехода, а также для реализации 16-разрядной операции сложения или одноименной операции большей разрядности на 8-разрядном АЛУ.
При операциях над беззнаковыми (неотрицательными) числами бит переноса можно интерпретировать как признак переполнения: т. е. того, что результат нельзя представить числом с разрядностью АЛУ. Игнорирование этого бита может приводить к неприятным последствиям: например, складывали мы 164 + 95, а получили в результате 3.
Иногда этот эффект, называемый "оборачиванием счетчиков", имеет и полезное применение. Например, используя "часовой" кварцевый генератор с частотой 32 768 Гц и 15-разрядный двоичный счетчик, мы можем отмерять секунды по появлению бита переноса в 16-м разряде и избавляемся от необходимости сбрасывать сам счетчик.
Двоичное вычитание может выполняться аналогичным образом, только необходимо использовать не таблицы сложения, а таблицы вычитания для двух и трех слагаемых. Не утомляя себя и читателя выписыванием этих таблиц, скажем сразу, что операция двоичного вычитания эквивалентна операции двоичного сложения уменьшаемого с двоичным дополнением вычитаемого. Двоичное дополнение строится таким образом: все биты числа инвертируются (нули заменяются на единицы, и наоборот), а затем к результату добавляется единица. Доказательство этого утверждения мы оставляем любопытному читателю, а сами просто рассмотрим пример 1.2.

Пример 1.2. Вычитание чисел (83 — 56 = 27)

Построение двоичного дополнения 56 :

Сложение с двоичным дополнением (83 + 56) mod 256 = 27:

	1		0
+	0	1	0	1	0	0	1	1
	1	1	0	0	1	0	0	0
1	0	0	0	0	1	0	1	1

Из примера видно, что эквивалентность между операциями неполная: сложение с дополнением сопровождается переносом в 9-й разряд, которого нет при прямом вычитании. Этот факт приводит к тому, что мы уже не можем считать перенос в 9-й разряд критерием того, что результат сложения не может быть представлен 8-ю битами. Точный критерий переполнения для целочисленных операций сложения и вычитания теперь звучит так: переполнение произошло, если перенос в 9-й бит (для 8-разрядного АЛУ) не равен переносу в 10-й бит.
Но в остальном двоичное дополнение сильно упрощает жизнь проектировщикам процессоров: вместо двух устройств, сумматора и дифференциатора (по-русски, сложителя и вычитателя), нам достаточно иметь только сумматор. Кроме того, можно представлять отрицательные числа в двоично-дополнительном коде (табл. 1.3). При таком представлении признак переполнения называют также признаком потери знака.
Видно, что четыре бита позволяют нам представить либо ноль и натуральные числа от 1 до 15, либо целые числа от - 8 до 7. Во втором случае, старший бит может интерпретироваться как знаковый — если он равен 1, число отрицательное, если 0 — положительное. Для манипулирования числами в обоих представлениях можно использовать одни и те же команды сложения и вычитания, различие возникает только, когда мы начинаем интерпретировать результаты сравнения таких чисел или сами эти числа (например, переводить их в десятичный формат).
Для команд умножения и деления трюк с двоичным дополнением не проходит, поэтому процессоры, использующие такое представление данных, вынуждены иметь по две пары команд умножения и деления, знаковые и беззнаковые. Любознательному читателю предлагается самостоятельно Разработать алгоритмы умножения и деления двоичных чисел в двоично-Дополнительном представлении. За основу для этих алгоритмов опять-таки рекомендуется взять школьные методы умножения и деления многозначных чисел "в столбик".

Таблица 1.3. Двоичное представление знаковых и беззнаковых чисел

Подавляющее большинство современных процессоров использует двоично-дополнительное представление для целых чисел. В те времена, когда компьютеры были большими, встречались системы, применявшие для этой цели дополнительный, знаковый бит: число —1 представлялось так же, как +1, но с установленным знаковым битом. Такие процессоры должны были иметь отдельные команды для беззнаковых и знаковых арифметических операций и более сложное АЛУ. Кроме того, при таком представлении возникает специфическая проблема "отрицательного нуля".
Иногда наравне с двоичным используется и специфическое, так называемое двоично-десятичное представление чисел (рис. 1.2). Это представление особенно удобно для приложений, которые постоянно вынуждены использовать десятичный ввод и вывод (микрокалькуляторы, часы, телефоны с автоопределителем номера и т. д.) и имеют небольшой объем программной памяти, в который нецелесообразно помещать универсальную процедуру преобразования чисел из двоичного представления в десятичное и обратно.
В таком представлении десятичная цифра обозначается тетрадой, четырьмя битами. Цифры от 0 до 9 представляются 0, 1111 недопустимы.своими двоичными эквивалентами, а комбинации битов 1010, 1011, 1100, 1101, 111

Рис. 1.2. Двоично-десятичное представление чисел

Вместо арифметических операций над такими числами большинство современных микропроцессоров предлагают использовать для их сложения и вычитания обычные бинарные операции, а потом исправлять возникающие при этом недопустимые значения при помощи специальной команды двоично-десятичной коррекции. Алгоритм работы этой команды читателю предлагается разработать самостоятельно. Для него потребуется информация о том, происходил ли при сложении двоичный перенос из младшей тетрады. Процессоры, предоставляющие такую команду, имеют и бит межтетрадного переноса.
Если операция производится над числами, имеющими 16 или более двоичных разрядов (4 и более двоично-десятичных), для коррекции нам недостаточно одного межтетрадного переноса — надо иметь по биту переноса на каждую из пар последовательных тетрад. Так далеко ни один из существующих процессоров не заходит. Например, 32-разрядные процессоры х86 имеют команды двоично-десятичной коррекции только для операций над числами с 8-ю двоичными (двумя двоично-десятичными) разрядами.