Вычитание, сравнение и АЛУ

АЛУ, арифметико-логическое устройство, — это часть процессора, которая выполняет вычисления: складывает, вычитает и сравнивает числа, применяет к ним логические операции. Отдельной схемы для вычитания в нём нет. Вычитает и сравнивает тот же сумматор, к которому добавили несколько вентилей.

Вычитание без вычитателя

В игре меню выбора героя замкнуто в кольцо: шестнадцать портретов стоят по кругу. Нужный портрет на шесть мест левее. Можно шесть раз нажать «влево». А можно десять раз нажать «вправо»: круг замкнётся, и Вы окажетесь там же. Шаг назад на 6 и шаг вперёд на 10 дают одно и то же, потому что 6 + 10 = 16.

Четыре бита — такой же круг из шестнадцати значений: после 1111 снова идёт 0000. Значит, вместо того чтобы вычитать B, можно прибавить число, которое дополняет B до 16. В уроке Целые числа в памяти оно называлось дополнительным кодом числа −B. Получают его так: инвертируют все биты B и прибавляют единицу. Отсюда главное правило урока:

A − B = A + (инверсия B) + 1

Почему правило работает? Сложите любое четырёхразрядное число с его инверсией. В каждом разряде встретятся ноль и единица, и получится 1111, то есть 15. Значит, инверсия B равна 15 − B:

A + (15 − B) + 1 = A − B + 16

Лишние 16 — это единица в пятом разряде. В четыре бита она не помещается и отбрасывается. Остаётся A − B.

Пример: 13 − 6

A             1101    13
B             0110     6
инверсия B    1001     9

    1101
  + 1001
  +    1
  ------
  1 0111

Проверим в десятичной записи: 13 + 9 + 1 = 23 = 16 + 7. Пятая цифра уходит на выход переноса из старшего разряда, а на четырёх выходах суммы остаётся 0111 — это 7. Верно: 13 − 6 = 7.

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

Сумматор с переключателем режима

Чтобы одна схема умела и складывать, и вычитать, она должна по команде делать две вещи: инвертировать B и прибавлять единицу.

Инвертировать по команде умеет исключающее ИЛИ. Подадим на один его вход бит B, а на другой — управляющий сигнал M:

Пока M = 0, бит проходит без изменений. Когда M = 1, на выходе его инверсия. Так работает переключатель «Инверсия цветов» в настройках телефона: выключен — картинка обычная, включён — каждый цвет заменён противоположным.

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

• M = 0: биты B не меняются, входной перенос равен 0. Схема считает A + B.
• M = 1: биты B инвертированы, входной перенос равен 1. Схема считает A + (инверсия B) + 1, то есть A − B.

Вычитание обошлось в четыре дополнительных вентиля — по одному на разряд.

Сравнение — это вычитание

Покупая предмет в игре, Вы заставляете программу проверить, хватает ли монет. Набирая код домофона — проверить, совпал ли он с правильным. Для процессора оба вопроса решаются вычитанием: он считает A − B и смотрит не на само число, а на его признаки.

Такие признаки называют флагами. Флаг — это один бит, который сообщает что-то о результате. Нам хватит двух:

• флаг нуля Z (от английского zero) равен 1, когда все биты результата — нули. Его получают, собрав все биты результата на вентили ИЛИ и поставив в конце НЕ;
• флаг знака N (от negative) — это старший бит результата. В дополнительном коде единица в старшем разряде означает отрицательное число.

Сравним три пары чисел на четырёх битах:

В последней строке 1110 — это −2 в дополнительном коде.

АЛУ: все операции в одном блоке

Сложение, вычитание, логические операции над парами битов собирают в один блок — арифметико-логическое устройство. У него есть:

• два входа для чисел A и B;
• вход кода операции — несколько битов, которые говорят, что нужно сделать;
• выход результата;
• выходы флагов.

Возьмём учебное АЛУ на четыре операции. Коду операции хватит двух битов. Коды мы назначили сами: у каждого настоящего процессора они свои.

Самое любопытное — как АЛУ выбирает операцию. Оно ничего не выбирает заранее: все схемы внутри работают одновременно, и каждая выдаёт свой ответ. На выход проходит только один — тот, на который указывает код операции. Схему, которая пропускает на выход один вход из нескольких, называют мультиплексором.

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

На рисунке сложение и вычитание показаны отдельными блоками, чтобы было нагляднее. На деле их выполняет один сумматор-вычитатель. Заметьте: коды 00 и 01 различаются только правым битом, и его можно подать прямо на вход M.

Умножение: сдвиги и сложения

Допишите к десятичному числу ноль справа — оно вырастет в 10 раз. В двоичной системе такой же ноль увеличивает число в 2 раза: 110 — это 6, 1100 — 12, 11000 — 24. Операцию, при которой все биты переезжают на разряд левее, называют сдвигом влево.

Умножим 6 на 5. Множитель 5 — это 101₂, то есть 4 + 1. Значит, 6 · 5 = 6 · 4 + 6 · 1:

6 · 1     00110     6
6 · 4     11000    24    сдвиг влево на два разряда
          -----
сумма     11110    30

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

Частые ошибки

• Забывают прибавить единицу. Одна инверсия даёт ответ на единицу меньше: 13 + 9 = 22, на четырёх битах это 0110, то есть 6 вместо 7.
• Считают перенос при вычитании ошибкой. Единица на выходе переноса здесь означает, что уменьшаемое не меньше вычитаемого.
• Думают, что АЛУ сначала выбирает операцию, а потом считает. Считается всё сразу, выбирается готовый результат.
• Дописывают ноль не с той стороны. Ноль слева число не меняет, ноль справа — удваивает.

Коротко

• Вычитание заменяют сложением: A − B = A + (инверсия B) + 1.
• Вентили исключающего ИЛИ инвертируют B по управляющему сигналу; тот же сигнал подают на входной перенос.
• Сравнить два числа — значит вычесть их и посмотреть на флаги: Z сообщает, что результат равен нулю, N — что он отрицательный.
• АЛУ — блок с двумя входами для чисел, кодом операции, выходом результата и флагами.
• Все операции АЛУ считает одновременно, а нужный результат выбирает мультиплексор.
• Сдвиг влево умножает число на 2; умножение складывается из сдвигов и сложений.

АЛУ считает, но ничего не помнит: уберите числа со входов — исчезнет и результат. Как схема запоминает один бит — в уроке Триггер.