Сложение и вычитание
Сложение и вычитание требуются не только для расчётов по формулам, но и для организации вычислений. Например, для того чтобы повторить какое-то действие R раз, используют переменную-счётчик, к которой после каждого выполнения этого действия прибавляют единицу, а затем результат сравнивают с R.
©
Вместо этого можно сразу записать в счётчик значение R и после каждого повторения вычитать из него единицу, пока не получится ноль1.
Благодаря тому что отрицательные числа кодируются в дополнительном коде, при сложении можно не обращать внимания на знаки слагаемых, т. е. со знаковым разрядом обращаются точно так же, как и со всеми остальными.
Например, сложим числа 510 (0000 01012) и -910(1111 01112), используя 8-разрядную двоичную арифметику. Применим сложение столбиком, не задумываясь о знаках чисел:
Для расшифровки получившегося отрицательного числа применим к нему схему получения дополнительного кода: 1111 1100 -» 0000 01002 = 410. Таким образом, результат равен -410, что совпадает с правилами
«обычной» арифметики.
При сложении двух чисел с одинаковыми знаками может случиться переполнение — сумма будет содержать слишком большое количество разрядов. Покажем, как это выглядит для положительных и отрицательных чисел.
Сложим десятичные числа 96 и 33. Их сумма 129 выходит за 8-битную сетку. Для того чтобы обнаружить переполнение, добавим к обоим слагаемым ещё один старший бит, совпадающий со знаковым (рис. 4.9).
Знаковый разряд S результата равен 1, т. е. сумма получилась отрицательной, хотя оба слагаемых положительны! Процессор определяет переполнение, сравнивая биты S и S': если они раз-
1Второй вариант более эффективен, потому что процессор автоматически сравнивает результат очередного действия с нулём.
личны, то произошло переполнение и результат неверный (см. рис. 4.9).
То же самое получается, если сложить два достаточно больших по модулю отрицательных числа, например -96 и -33. Добавим к кодам обоих чисел один старший разряд, равный знаковому разряду (рис. 4.10).
Получается, что в результате бит S=0, хотя ответ должен
быть отрицательным. Биты S' и S не совпадают, это говорит о том, что произошло переполнение. Несложно проверить (сделайте это самостоятельно), что, если переполнения нет, значения битов S и S' всегда одинаковы независимо от знаков слагаемых.
Сложение многоразрядных двоичных чисел в компьютере выполняет специальное устройство — сумматор (см. главу 3). Как мы уже говорили, вычитание сводится к сложению с дополнительным кодом вычитаемого, поэтому отдельного «блока вычитания» в компьютере нет.
Умножение и деление
Умножение и деление выполнять труднее, чем сложение и вычитание. Вспомните, например, что в математике умножение часто заменяют многократным сложением, а деление — многократным вычитанием.
К двоичным числам можно применять обычную схему умножения «столбиком». Перемножим, например, числа 910 (0000 10012) и 510 (0000 01012):
Легко проверить, что это число равно 4510.
В сравнении с десятичной системой, здесь есть серьёзное упрощение: первый сомножитель умножается на единицу (в этом случае результат равен ему самому) или на ноль (результат — 0). Поэтому компьютерное умножение целых чисел состоит из следующих элементарных действий:
1) вычисление очередного произведения в зависимости от младшего бита второго сомножителя: оно равно нулю (если этот бит нулевой) или первому сомножителю (если бит равен единице);
2) сложение содержимого сумматора с очередным произведением;
3) сдвиг содержимого первого сомножителя влево на 1 разряд;
4) сдвиг второго сомножителя вправо на 1 разряд (при этом следующий бит попадёт в младший разряд).
Таким образом, удаётся построить схему умножения без использования таблицы умножения. Заметим, что умножение — это довольно трудоёмкая операция, и для её ускорения конструкторы используют различные «хитрые» приёмы. Поэтому в реальных компьютерах всё может выглядеть значительно сложнее, чем в учебном примере.
Умножение, как и сложение, выполняется одинаково для положительных и отрицательных чисел (в дополнительном коде). Если в нашем примере вместо числа 9 подставить -9, то получится:
Оставив только 8 младших битов, можно убедиться (применяя алгоритмы А1-АЗ), что результат — это дополнительный код числа -45.
Теория деления нацело намного сложнее, чем приёмы умножения, поэтому мы её обсуждать не будем.
Сравнение
В отличие от арифметических действий операция сравнения по-разному выполняется для чисел со знаком и без него. Еще раз внимательно посмотрим на таблицы кодов 8-битных чисел, при¬ведённые в § 27 (табл. 4.4). Если сравниваемые коды не превышают 7F16, то оба числа положительны а сравнение однозначно. Если это не так, то сравнение чисел с учётом и без учёта знака дает разные результаты. Например, для беззнаковых чисел 8116 (12910) больше, чем 7F16 (12710). Для чисел со знаком, наоборот, отрицательное значение 8116 (-12710) будет меньше, чем 7F16 (12710). Поэтому современные процессоры имеют разные команды для сравнения чисел со знаком и без знака. Чтобы не путаться, при сравнении с учётом знака обычно используют термины «больше» /«меньше», а при сравнении без учёта знака — «выше » / «ниже».
Поразрядные логические операции
В главе 3, изучая основы математической логики, мы увидели, что обработка истинности и ложности высказываний может быть представлена как набор операций с двоичными кодами. Оказывается, что логические операции, введённые первоначально для обработки логических данных, можно формально применить к битам двоичного числа, и такой подход широко используется в современных компьютерах.
Рассмотрим электронное устройство для управления гирляндой лампочек. Состояние каждой лампочки будет задаваться отдельным битом в некотором управляющем регистре: если бит равен нулю, лампочка выключена, если единице — включена. Для получения различных световых эффектов (типа «бегущих огней») требуется зажигать или гасить отдельные лампочки, менять их состояние на противоположное и т. д. (рис. 4.11). Точно так же биты регистров используются для управления внешними устройствами. 
Будем применять логические операции к каждому биту числа, как обычно, считая, что 1 соответствует значению «истина», а 0 — «ложь». Эти операции часто называют поразрядными или битовыми, поскольку действия совершаются над каждым разрядом в отдельности, независимо друг от друга1.
Введём несколько терминов, которые используются в литературе по вычислительной технике. Сброс — это запись в бит нулевого значения, а установка — запись единицы. Таким образом, если бит в результате какой-то операции становится равным нулю, то говорят, что он сбрасывается. Аналогично, когда в него записана единица, говорят, что бит установлен.
Маска —это константа (постоянная), которая определяет область применения логической операции к битам многоразрядного числа. С помощью маски можно скрывать (защищать) или открывать для выполнения операции отдельные биты2.
Основные логические операции в современных процессорах — это «НЕ» (not), «И» (and), «ИЛИ» (ог) и «исключающее ИЛИ» (xог).
Логическое «НЕ» (инвертирование, инверсия, not) — это замена всех битов числа на обратные значения: 0 на 1, а 1 — на 0. Эта операция используется, например, для получения дополнительного кода отрицательных чисел (см. алгоритм А1 в § 27). «НЕ» — это унарная операция, т. е. она действует на все биты одного числа. Маска здесь не используется.
Логическое «И» (and). Обозначим через D содержимое некоторого бита данных, а через М — значение соответствующего ему бита маски. Операция «И» между ними задаётся таблицей, показанной на рис. 4.12.
Из таблицы видно, что при выполнении логического «И» нулевой бит в маске всегда сбрасывает (делает равным нулю) соответствующий бит результата, а еди-
2 Для сравнения, сложения ( как и другие арифметические действи ) не является подразрядной операцией, поскольку возможен перенос из младшего разряда в старший.
2 Использование маски аналогично выделению области рисунка в графическом редакторе - для выделенных пикселей маска равна 1, для остальных - нулю.
ничный бит позволяет сохранить значение D (как бы пропускает его, открывая «окошко»).
С помощью логической операции «И» можно сбросить отдельные i биты числа (те, для которых маска нулевая), не меняя значения остальных битов (для которых в маске стоят единицы).
Например, операция Х and 1 сбросит у любого числа X все биты. С помощью этого приёма легко узнать, является ли число четным : остаток от деления на 2 равен последнему биту !
Логическое «ИЛИ». Вспомнив таблицу истинности логической операции «ИЛИ» (or), можно обнаружить, что в ноль в маске сохраняет бит (D or 0 = D), а единица устанавливает соответствующий бит результата ( D or 1 = 1) (рис. 4.13). 
С помощью логической операции «ИЛИ» можно установить отдельные биты числа (те, для которых маска единичная), не меняя значения остальных битов (для которых в маске стоят нули)
Например, операция X or 8016 установит старший бит восьмиразрядного числа X, формально сделав тем самым
число отрицательным
Таким образом, используя операции «И» и «ИЛИ», можно сбрасывать и устанавливать любые биты числа, т. е. строишь любой нужный двоичный код. Где это может пригодиться? Рассмотрим примеры решения конкретных задач.
Пример 1. На клавиатуре набраны 3 цифры, образующие значение целого числа без знака. Определить, какое число было введено.
При нажатии клавиши на клавиатуре в компьютер поступает код нажатой клавиши. Выпишем десятичные и шестнадцатеричные коды всех символов , обозначающих цифры:
Будем пользоваться шестнадцатеричными кодами: как видно из таблицы, их связь с цифрами числа гораздо нагляднее. Чтобы получить числовое значение цифры из кода символа X, достаточно сбросить его старшие четыре бита, не изменяя значений четырёх младших битов. Для этого нужно использовать операцию X and 0F16.
Пусть Sj — код первого введённого символа, S2 — второго, S3 — третьего, а N обозначает искомое число. Тогда алгоритм перевода кодов символов в число выглядит так:
l.N=0.
2.W = S-i and 0F16 (выделяем первую цифру).
3.N -10 - N + W (добавляем её к числу).
4.W = S2 and 0F16 (выделяем вторую цифру).
5.N = 10 -N + W (добавляем её к числу).
6.W = S3 and 0F16 (выделяем третью цифру).
7.N =10N + W (добавляем её к числу).
Пусть, например, набраны символы '1', '2' и '3'. Тогда по таблице находим, что S1 =3116, S2 =3216 и S3 =3316. Значение W на втором шаге вычисляется так:
Так как W = 1, на третьем шаге получаем N = 1. Следующая пара шагов — четвёртый и пятый — дают результаты W = 2 и N = 12 соответственно. Наконец, результат завершающих шагов: W = 3 и N = 123.
Такая процедура используется в каждом компьютере: именно так коды цифровых символов, набранные на клавиатуре, преобразуются в числа, с которыми компьютер выполняет арифметические действия. Заметим, что фактически здесь использована схема Горнера для представления целого числа (см. § 10).
Пример 2. Создадим структуру данных S, которая отражает, есть или нет в некотором числе каждая из цифр от 0 до 9. В математике такая структура называется множеством. Для хранения S будем использовать 16-разрядное целое число (рис. 4.14).
Договоримся, что младший бит числа имеет номер 0 и хранит информацию о том, есть во множестве цифра 0 (если этот бит равен 0, такой цифры нет, если равен 1, то есть). Аналогично пер¬вый бит (второй по счёту справа) показывает, есть ли во множестве цифра 1, и т. д. Старшие биты 10-15 при этом не используют¬ся. Например, во множестве, изображенном на рис. 4.14, есть только цифры 0, 3, 6 и 9.
Для записи элементов во множество и проверки их наличия удобно использовать логические операции. Рассмотрим для при¬мера бит 5. Маска, которая потребуется для обращения к нему, — это единица в пятом разряде и нули во всех остальных, т. е. M = 002016. С ее помощью можно добавить элемент к множеству с помощью операции «ИЛИ»: S = S or M. А узнать, есть ли во множестве интересующая нас цифра, можно, выделив соответствующий бит с помощью логического «И» (Р = S and M) и проверив результат на равенство нулю.
Исключающее ИЛИ. Как видно из таблицы истинности, операция «исключающее ИЛИ» (xor) не изменяет биты, когда маска нулевая, и меняет биты на противоположные при единичной маске (рис. 4.15).
Например, команда X = X xor FF16 выполняет инверсию всех битов 8-разрядного целого числа. Напомним, что это один из этапов получения дополнительно¬го кода отрицательных чисел.
С помощью логической операции «исключающее ИЛИ" можно выполнить инверсию отдельных битов числа (тех, для которых маска единичная), не меняя значения остальных битов (для которых в маске стоят нули).
Пример 3. Пусть .X" — это результат выполнения некоторого вычислительного теста, а У — то, что ожидалось получить («правильное» значение). Нужно определить, в каких разрядах разли¬чаются эти числа (для инженера это очень полезная подсказка,
Предположим, что Х = 7, У = 3. В результате операции X xor У устанавливаются (в единицу) только те разряды, которые в
этих числах не совпали, а остальные сбрасываются1. В данном случае находим, что числа различаются только одним битом:
Пример 4. Используя логическую операцию «исключающее ИЛИ», можно шифровать любые данные. Покажем это на примере простого текста '2*2=4'.
Выберем любую маску, например 231О = 0001 01112. Эта маска представляет собой ключ шифра — зная ключ, можно расшифровать сообщение. Возьмём первый символ — цифру '2', которая имеет код 5010 = ООН 00102, и применим операцию «исключающее ИЛИ» с выбранной маской:
Полученное значение 0010 01012 = 3710 — это код символа '%'. Для расшифровки применим к этому коду «исключающее ИЛИ» с той же маской:
Профессиональные программисты часто используют операцию хог для обнуления переменной: команда R := R хог R запишет в переменную R
В результате получили число 50 — код исходной цифры '2'.
Повторное применение операции «исключающее ИЛИ» стой же маской восстанавливает исходное значение, т. е. эта логическая операция
обратима.
Если применить такую процедуру шифрования ко всем символам текста '2*2=4', то получится зашифрованный текст *%=%*#*.
Обратимость операции «исключающее ИЛИ» часто используется в компьютерной графике для временного наложения одного изображения на другое. Это может потребоваться, например, для выделения области с помощью инвертирования её цвета.
Сдвиги
Об операции сдвига вспоминают гораздо реже, чем она того заслуживает. Перечитайте ещё раз алгоритм умножения, описанный выше, и вы убедитесь, что он весь построен на сдвигах. Сдвиги незаменимы тогда, когда требуется проделать ту или иную обработку каждого бита, входящего в число. Наконец, сдвиги двоичного числа позволяют быстро умножить или разделить число на степени двойки: 2, 4, 8 и т. д. Поэтому программисты очень ценят и широко применяют всевозможные разновидности сдвигов.
Идея операции сдвига довольно проста: все биты кода одновременно сдвигаются в соседние разряды1 влево или вправо (рис. 4.16).
1 Аппаратно сдвиг реализуется необычайно просто и изящно: регистр, содержащий число, сбрасывается в ноль, при этом из тех разрядов, где исчезла единица, электрический импульс проходит в соседние и устанавливает их в единицу. При этом важно, что все разряды обрабатываются одновременно.
Отдельно надо поговорить о двух крайних битах, у которых «нет соседей». Для определённости обсудим сдвиг влево. Для самого младшего бита (на рис. 4.16 он крайний справа) данные взять неоткуда, поэтому в него просто заносится ноль. Самый старший (крайний слева) бит должен потеряться, так как его некуда сохранить. Чтобы данные не пропали, содержимое этого разряда копируется в специальную ячейку процессора — бит переноса1 С (от англ. carry — перенос), с которым может работать процессор.
Рассмотренный тип сдвига обычно называется логическим сдвигом. Его можно использовать для быстрого умножения и деления. Рассмотрим, например, 8-разрядный двоичный код 0000 1100, который представляет число 1210. Выполнив логический сдвиг влево, получим 0001 1000, т. е. число 2410, которое вдвое больше! Это не случайность: вспомните, что происходит, если к десятичному числу справа приписать дополнительный ноль, например 34 -» 340.
При сдвиге вправо любое чётное число уменьшается ровно в 2 раза. В случае нечётного значения происходит деление нацело, при котором остаток отбрасывается. Например, из 0001 0001 = 1710 при сдвиге вправо получается 0000 1000 = 810.
Логический сдвиг влево на 1 разряд увеличивает целое положительное число вдвое, а сдвиг вправо делит на 2 нацело.
Пример. Для умножения числа, находящегося в ячейке Z, на 10 можно использовать такой алгоритм:
1.Сдвиг влево Z (в ячейке Z получаем 220, где ZQ — исходное число).
2. X = Z (сохраним 2Z0).
3. Сдвиг на 2 бита влево X (вычислили 8Z0).
4. X = X + Z (X =8Z0 +2Z0 =10Z0).
Для некоторых компьютеров такая последовательность выполняется быстрее, чем стандартная операция умножения.
Посмотрим, что получится при сдвиге отрицательных чисел в дополнительном коде. Сдвинем влево код 1111 1000 (8-разрядное представление числа -8):
1При программировании на языках высокого уровня бит переноса недоступен.
получится 1111 0000. Легко проверить, что это дополнительный код числа -16, т. е. значение удвоилось! Но со сдвигом вправо ничего не получается: из 1111 1000 получаем 0111 1100 — это код положительного числа! Дело в том, что при сдвиге вправо отрицательных чисел, в отличие от положительных, старший разряд надо заполнять не нулём, а единицей! Чтобы исправить положение, вводится ещё одна разновидность сдвига — арифметический сдвиг. Его единственное отличие от логического состоит в том, что старший (знаковый) бит не меняется, т. е. знак числа остаётся прежним (рис. 4.17).
Если применить арифметический сдвиг к коду 1111 1000, получается 1111 1100 — дополнительный код числа -4, т. е. произошло деление на 2. В качестве упражнения проверьте, как ведёт себя отрицательное нечётное число при арифметическом сдвиге вправо.
Арифметический сдвиг
влево не требуется, поскольку он ничем не отличается от обычного логического сдвига.
То, что в результате логических сдвигов содержимое крайних разрядов теряется, не всегда удобно. Поэтому в компьютере предусмотрен циклический сдвиг, при котором бит из одного крайнего разряда переносится в другой («по циклу», рис. 4.18).
Циклический сдвиг позволяет «просмотреть» все биты и вернуться к исходному значению. Если сделать последовательно 8 циклических сдвигов 8-битного числа, каждый его бит на каком-то шаге окажется на месте младшего разряда, где его можно выделить с помощью логической операции «И» с маской 1. Так можно «просматривать» не только младший, но и любой другой разряд (например, для выделения старшего разряда нужно использовать маску 8016).
Вопросы и задания
1. Покажите на примере, как складываются два положительных целых числа , записанные в 8- разрядные ячейки. Что изменится, если числа будут отрицательными?
2. Что такое дополнительный код? Сформулируйте правила получения дополнительного кода числа.
3. При каких комбинациях знаков слагаемых в результате сложения
может возникнуть переполнение?
4. Какое устройство выполняет в компьютере сложение? Вспомните,что вы знаете об этом устройстве.
5. Почему не нужно разрабатывать специальное устройство для вычитания целых чисел?
6. Перемножьте столбиком два положительных целых числа в двоичной системе счисления. Изменится ли алгоритм выполнения операции, если у одного из сомножителей поменять знак?
7.Почему коды чисел со знаком и без знака нужно сравнивать по-разному?
8. Что такое поразрядные операции? Приведите примеры.
9. Почему арифметические операции нельзя отнести к поразрядным?
10.Что такое маска?
11. Как, используя маску, сбросить определённый бит (записать в него 0)?
12. Напишите значение маски для того, чтобы сбросить в 16-разрядном
числе 2 младших бита, не изменяя все остальные. Какую логическую операцию нужно для этого использовать?
13. Как, используя маску, установить определённый бит?
14. Напишите значение маски для того, чтобы установить в 16-разрядном числе 2 старших бита, не изменяя все остальные. Какую логическую операцию нужно для этого использовать?
15. Как, используя логические операции, определить, делится ли число на 4? На 8?
16. В каких практических задачах можно применять установку или сброс битов двоичного кода?
17. Каковы возможности операции «исключающее ИЛИ»?
*18. Попробуйте придумать алгоритм шифрования кода с рации «исключающее ИЛИ». Постарайтесь предложить алгоритм изменения маски, а не просто использовать константу.
19. Прочитайте ещё раз материал, связанный с переполнением при сложении. Какой логической операцией можно определить совпадают или нет биты S' и S?
20. Какую роль играет операция «НЕ» при получении отрицательных чисел?
21. Как выполнить инверсию всех битов, не используя логическую операцию «НЕ»?
22. Что такое сдвиг? Какие вы знаете виды сдвига?
23. Как обрабатываются самый старший и самый младший биты при различных типах сдвига?
24. Покажите на примерах, что сдвиг влево двоичного кода удваивает число, а сдвиг вправо - уменьшает вдвое.
25. Почему логический сдвиг не годится для уменьшения в два раза отрицательных чисел? Как работает арифметический сдвиг?
26. Почему не требуется арифметический сдвиг влево?
*27. Выведите правило вычисления результата арифметического сдвига отрицательного нечётного числа на один разряд вправо. Проверьте, применимо ли это правило к положительным нечетным числам. Как упрощается формула для чётных исходных значений?
28. Где могут применяться сдвиги?
Подготовьте сообщение
а) «Битовые логические операции»
б) «Шифрование с помощью операции "исключающее ИЛИ"»
в) «Применение сдвигов».