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

©

 

Вместо этого можно сразу записать в счётчик значение R и после каждого повторения вычитать из него единицу, пока не получится ноль^1.

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

Например, сложим числа 5₁₀ (0000 0101₂) и -9₁₀(1111 0111₂), используя 8-разрядную двоичную арифметику. Применим сложение столбиком, не задумываясь о знаках чисел:

 

Для расшифровки получившегося отрицательного числа применим к нему схему получения дополнительного кода: 1111 1100 -» 0000 0100₂ = 4₁₀. Таким образом, результат равен -4₁₀, что совпадает с правилами

«обычной» арифметики.

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

Сложим десятичные числа 96 и 33. Их сумма 129 выходит за 8-битную сетку. Для того чтобы обнаружить переполнение, добавим к обоим слагаемым ещё один старший бит, совпадающий со знаковым (рис. 4.9).

 

Знаковый разряд S результата равен 1, т. е. сумма получилась отрицательной, хотя оба слагаемых положительны! Процессор определяет переполнение, сравнивая биты S и S': если они раз-

---

 

¹Второй вариант более эффективен, потому что процессор автоматически сравнивает результат очередного действия с нулём.

---

 

личны, то произошло переполнение и результат неверный (см. рис. 4.9).

То же самое получается, если сложить два достаточно больших по модулю отрицательных числа, например -96 и -33. Добавим к кодам обоих чисел один старший разряд, равный знаковому разряду (рис. 4.10).

 

Получается, что в результате бит S=0, хотя ответ должен

быть отрицательным. Биты S' и S не совпадают, это говорит о том, что произошло переполнение. Несложно проверить (сделайте это самостоятельно), что, если переполнения нет, значения битов S и S' всегда одинаковы независимо от знаков слагаемых.

Сложение многоразрядных двоичных чисел в компьютере выполняет специальное устройство — сумматор (см. главу 3). Как мы уже говорили, вычитание сводится к сложению с дополнительным кодом вычитаемого, поэтому отдельного «блока вычитания» в компьютере нет.

 

Умножение и деление выполнять труднее, чем сложение и вычитание. Вспомните, например, что в математике умножение часто заменяют многократным сложением, а деление — многократным вычитанием.

К двоичным числам можно применять обычную схему умножения «столбиком». Перемножим, например, числа 9₁₀ (0000 1001₂) и 5₁₀ (0000 0101₂):

 

Легко проверить, что это число равно 45₁₀.

В сравнении с десятичной системой, здесь есть серьёзное упрощение: первый сомножитель умножается на единицу (в этом случае результат равен ему самому) или на ноль (результат — 0). Поэтому компьютерное умножение целых чисел состоит из следующих элементарных действий:

1)  вычисление очередного произведения в зависимости от младшего бита второго сомножителя: оно равно нулю (если этот бит нулевой) или первому сомножителю (если бит равен единице);

2) сложение содержимого сумматора с очередным произведением;

3) сдвиг содержимого первого сомножителя влево на 1 разряд;

4) сдвиг второго сомножителя вправо на 1 разряд (при этом следующий бит попадёт в младший разряд).

Таким образом, удаётся построить схему умножения без использования таблицы умножения. Заметим, что умножение — это довольно трудоёмкая операция, и для её ускорения конструкторы используют различные «хитрые» приёмы. Поэтому в реальных компьютерах всё может выглядеть значительно сложнее, чем в учебном примере.

Умножение, как и сложение, выполняется одинаково для положительных и отрицательных чисел (в дополнительном коде). Если в нашем примере вместо числа 9 подставить -9, то получится:

Оставив только 8 младших битов, можно убедиться (применяя алгоритмы А1-АЗ), что результат — это дополнительный код числа -45.

Теория деления нацело намного сложнее, чем приёмы умножения, поэтому мы её обсуждать не будем.

 

В отличие от арифметических действий операция сравнения по-разному выполняется для чисел со знаком и без него. Еще раз внимательно посмотрим на таблицы кодов 8-битных чисел, при¬ведённые в § 27 (табл. 4.4). Если сравниваемые коды не превышают 7F₁₆, то оба числа положительны а сравнение однозначно. Если это не так, то сравнение чисел с учётом и без учёта знака дает разные результаты. Например, для беззнаковых чисел 81₁₆ (129₁₀) больше, чем 7F₁₆ (127₁₀). Для чисел со знаком, наоборот, отрицательное значение 81₁₆ (-127₁₀) будет меньше, чем 7F16 (12710). Поэтому современные процессоры имеют разные команды для сравнения чисел со знаком и без знака. Чтобы не путаться, при сравнении с учётом знака обычно используют термины «больше» /«меньше», а при сравнении без учёта знака — «выше » / «ниже».

 

 

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

Рассмотрим электронное устройство для управления гирляндой лампочек. Состояние каждой лампочки будет задаваться отдельным битом в некотором управляющем регистре: если бит равен нулю, лампочка выключена, если единице — включена. Для получения различных световых эффектов (типа «бегущих огней») требуется зажигать или гасить отдельные лампочки, менять их состояние на противоположное  и т. д. (рис. 4.11). Точно так же биты регистров используются для управления внешними устройствами.                                

 

Будем применять логические операции к каждому биту числа, как обычно, считая, что 1 соответствует значению «истина», а 0 — «ложь». Эти операции часто называют поразрядными или битовыми, поскольку действия совершаются над каждым разрядом в отдельности, независимо друг от друга¹.

Введём несколько терминов, которые используются в литературе по вычислительной технике. Сброс — это запись в бит нулевого значения, а установка — запись единицы. Таким образом, если бит в результате какой-то операции становится равным нулю, то говорят, что он сбрасывается. Аналогично, когда в него записана единица, говорят, что бит установлен.

Маска —это константа (постоянная), которая определяет область применения логической операции к битам многоразрядного числа. С помощью маски можно скрывать (защищать) или открывать для выполнения операции отдельные биты².

Основные логические операции в современных процессорах — это «НЕ» (not), «И» (and), «ИЛИ» (ог) и «исключающее ИЛИ» (xог).

 

Логическое «НЕ»  (инвертирование, инверсия, not) — это замена всех битов числа на обратные значения: 0 на 1, а 1 — на 0. Эта операция используется, например, для получения дополнительного кода отрицательных чисел (см. алгоритм А1 в § 27). «НЕ» — это унарная операция, т. е. она действует на все биты одного числа. Маска здесь не используется.

 

Логическое «И» (and). Обозначим через D содержимое некоторого бита данных, а через М — значение соответствующего ему бита маски. Операция «И» между ними задаётся таблицей, показанной на рис. 4.12.

Из таблицы видно, что при выполнении логического «И» нулевой бит в маске всегда сбрасывает (делает равным нулю) соответствующий бит результата, а еди-

---

² Для сравнения, сложения ( как и другие арифметические действи ) не является подразрядной операцией, поскольку возможен перенос из младшего разряда в старший.

² Использование маски аналогично выделению области рисунка в графическом редакторе - для выделенных пикселей маска равна 1, для остальных - нулю.

---

 

ничный бит позволяет сохранить значение D (как бы пропускает его, открывая «окошко»).

---

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

---

 

 

Например, операция Х and 1 сбросит у любого числа X все биты. С помощью этого приёма легко узнать, является  ли число четным :  остаток  от деления на 2 равен последнему биту ! 

 

Логическое «ИЛИ». Вспомнив таблицу истинности логической операции «ИЛИ» (or), можно обнаружить, что в ноль в маске сохраняет бит (D or 0 = D), а единица устанавливает соответствующий бит результата ( D or 1 = 1) (рис. 4.13). 

---

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

---

 

 

Например, операция X or 80₁₆ установит старший бит восьмиразрядного числа X, формально сделав тем самым

число отрицательным

Таким образом, используя операции «И» и «ИЛИ», можно сбрасывать и устанавливать любые биты числа, т. е. строишь любой нужный двоичный код. Где это может пригодиться? Рассмотрим примеры решения конкретных задач.

 

Пример 1. На клавиатуре набраны 3 цифры, образующие значение целого числа без знака. Определить, какое число было введено.

 

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

 

Будем пользоваться шестнадцатеричными кодами: как видно из таблицы, их связь с цифрами числа гораздо нагляднее. Чтобы получить числовое значение цифры из кода символа X, достаточно сбросить его старшие четыре бита, не изменяя значений четырёх младших битов. Для этого нужно использовать операцию X and 0F₁₆.

Пусть 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'. Тогда по таблице находим, что S₁ =31₁₆, S₂ =32₁₆ и S₃ =33₁₆. Значение 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 = 0020₁₆. С ее помощью можно добавить элемент к множеству с помощью операции «ИЛИ»: S = S or M. А узнать, есть ли во множестве интересующая нас цифра, можно, выделив соответствующий бит с помощью логического «И» (Р = S and M) и проверив результат на равенство нулю.

 

Исключающее ИЛИ. Как видно из таблицы истинности, операция «исключающее ИЛИ» (xor) не изменяет биты, когда маска нулевая, и меняет биты на противоположные при единичной маске (рис. 4.15).

 

Например, команда X = X xor FF₁₆ выполняет инверсию всех битов 8-разрядного целого числа. Напомним, что это один из этапов получения дополнительно¬го кода отрицательных чисел.

---

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

---

Пример 3. Пусть .X" — это результат выполнения некоторого вычислительного теста, а У — то, что ожидалось получить («правильное» значение). Нужно определить, в каких разрядах разли¬чаются эти числа (для инженера это очень полезная подсказка,

Предположим, что Х = 7, У = 3. В результате операции X xor У устанавливаются (в единицу) только те разряды, которые в

этих числах не совпали, а остальные сбрасываются¹. В данном случае находим, что числа различаются только одним битом:

 

Пример 4. Используя логическую операцию «исключающее ИЛИ», можно шифровать любые данные. Покажем это на примере простого текста '2*2=4'.

Выберем любую маску, например 23_1О = 0001 0111₂. Эта маска представляет собой ключ шифра — зная ключ, можно расшифровать сообщение. Возьмём первый символ — цифру '2', которая имеет код 50₁₀ = ООН 0010₂, и применим операцию «исключающее ИЛИ» с выбранной маской:

Полученное значение 0010 0101₂ = 37₁₀ — это код символа '%'. Для расшифровки применим к этому коду «исключающее ИЛИ» с той же маской:

---

Профессиональные программисты часто используют операцию хог для обнуления переменной: команда R := R хог R запишет в переменную R

---

 

В результате получили число 50 — код исходной цифры '2'.

---

Повторное применение операции «исключающее ИЛИ» стой же  маской восстанавливает исходное значение, т. е. эта логическая операция

обратима.

---

 

Если применить такую процедуру шифрования ко всем символам текста '2*2=4', то получится зашифрованный текст *%=%*#*.

Обратимость операции «исключающее ИЛИ» часто используется в компьютерной графике для временного наложения одного изображения на другое. Это может потребоваться, например, для выделения области с помощью инвертирования её цвета.

 

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

Идея операции сдвига довольно проста: все биты кода одновременно сдвигаются в соседние разряды¹ влево или вправо (рис. 4.16).

---

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

---

 

Отдельно надо поговорить о двух крайних битах, у которых «нет соседей». Для определённости обсудим сдвиг влево. Для самого младшего бита (на рис. 4.16 он крайний справа) данные взять неоткуда, поэтому в него просто заносится ноль. Самый старший (крайний слева) бит должен потеряться, так как его некуда сохранить. Чтобы данные не пропали, содержимое этого разряда копируется в специальную ячейку процессора — бит переноса¹ С (от англ. carry — перенос), с которым может работать процессор.

Рассмотренный тип сдвига обычно называется логическим сдвигом. Его можно использовать для быстрого умножения и деления. Рассмотрим, например, 8-разрядный двоичный код 0000 1100, который представляет число 12₁₀. Выполнив логический сдвиг влево, получим 0001 1000, т. е. число 24₁₀, которое вдвое больше! Это не случайность: вспомните, что происходит, если к десятичному числу справа приписать дополнительный ноль, например 34 -» 340.

При сдвиге вправо любое чётное число уменьшается ровно в 2 раза. В случае нечётного значения происходит деление нацело, при котором остаток отбрасывается. Например, из 0001 0001 = 17₁₀ при сдвиге вправо получается 0000 1000 = 8₁₀.

---

Логический сдвиг влево на 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):

---

¹При программировании на языках высокого уровня бит переноса недоступен.

---

получится 1111 0000. Легко проверить, что это дополнительный код числа -16, т. е. значение удвоилось! Но со сдвигом вправо ничего не получается: из 1111 1000 получаем 0111 1100 — это код положительного числа! Дело в том, что при сдвиге вправо отрицательных чисел, в отличие от положительных, старший разряд надо заполнять не нулём, а единицей! Чтобы исправить положение, вводится ещё одна разновидность сдвига — арифметический сдвиг. Его единственное отличие от логического состоит в том, что старший (знаковый) бит не меняется, т. е. знак числа остаётся прежним (рис. 4.17).

 

Если применить арифметический сдвиг к коду 1111 1000, получается 1111 1100 — дополнительный код числа -4, т. е. произошло деление на 2. В качестве упражнения проверьте, как ведёт себя отрицательное нечётное число при арифметическом сдвиге вправо.

Арифметический сдвиг

влево не требуется, поскольку он ничем не отличается от обычного логического сдвига.

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

 

 

Циклический сдвиг позволяет «просмотреть» все биты и вернуться к исходному значению. Если сделать последовательно 8 циклических сдвигов 8-битного числа, каждый его бит на каком-то шаге окажется на месте младшего разряда, где его можно выделить с помощью логической операции «И» с маской 1. Так можно «просматривать» не только младший, но и любой другой разряд (например, для выделения старшего разряда нужно использовать маску 80₁₆).

 

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. Как выполнить инверсию всех битов, не используя логическую операцию «НЕ»?

25. Почему логический сдвиг не годится для уменьшения в два раза отрицательных чисел?  Как работает арифметический сдвиг?

26. Почему не требуется арифметический сдвиг влево?

*27. Выведите правило вычисления результата арифметического сдвига отрицательного нечётного числа на один разряд вправо. Проверьте, применимо ли это правило к положительным нечетным числам. Как упрощается формула для чётных исходных значений?

28. Где могут применяться сдвиги?

 

б) «Шифрование с помощью операции "исключающее ИЛИ"»

в) «Применение сдвигов».