Числа №3. Сложение

Продолжаем тему чисел, на этот раз – что-то более серьезное. Поговорим, как компьютеры складывают числа. На эту тему написаны хорошие статьи и книги, поэтому в формате заметки изложить тему невозможно. Напишу только то, что считаю наиболее важным.

Мы, люди, учимся считать в десятичной системе счисления. Если нужно сложить два числа, мы делаем это в столбик. Мы складываем разряды, при этом может случиться переполнение, например 5 + 7 = 12. В текущем разряде останется 2, а старший переедет к следующему, и нужно учесть его при сложении. Покажем это на примере:

   1 1
  23.55
  12.97
  -----
  36.52

Мы складываем по две десятичные цифры за раз: 2 и 3, 4 и 9 и так далее. Компьютер делает то же самое, но в двоичном виде. Он не может сложить 2 и 3 за один машинный такт – это невозможно. Его система счисления доведена до предела: в ней только нули и единицы. Такой подход следует из природы полупроводников и транзисторов: они принимают два сигнала и выдают один. Были машины на троичной логике, но они не получили распространения.

Чтобы сложить два бита, для начала проектируют полусумматор. Это логический элемент, который состоит из других элементов проще. Полусумматор принимает два бита (входы) и возвращает бит результата. Если подать нули, результат будет ноль, если 0 и 1 или наоборот, то 1.

Почему “полу”? Потому что если подать 1 и 1, мы должны получить 0 (результат) и 1 (бит переноса). У полусумматора нет переноса, поэтому бит 1 пропадет. Чтобы этого не случилось, из двух полусумматоров делают полный. Он принимает не два, а три входа: два бита (входы) и перенос, который, возможно, образовался при сложении прошлого разряда.

Множество сумматоров объединяют в каскад, и можно складывать многобитные числа: 4-, 8-, 16- и 32-битные. Пусть вас не смущают четырехбитные числа: такие архитектуры были в старых калькуляторах. Обратите внимание, что последний флаг переноса никуда не делся: складывая числа, мы должны быть готовы к тому, что последний разряд переполнился, и с этим нужно что-то делать.

Проблему последнего переноса решают так: этот бит подключается к специальному регистру флагов. У процессора есть регистр, где каждый бит означает особое состояние. Один из них определяет, был ли перенос в последнем разряде (carry flag). Есть особая команда семейства jump, которая переходит на нужный адрес, если флаг не ноль. В высокоуровневых языках по этому адресу находится код, который возбуждает исключение.

До сих пор я использовал слова “перенос” и “переполнение” вместе, но на самом деле это разные вещи. Перенос (carry) используется для беззнаковых чисел, а для знаковых мы говорим о переполнении (overflow). В регистре флагов это два разных бита и две разные команды jump.

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

Картинки взяты из замечательной книги “Код: тайный язык информатики”. Горячо рекомендую ее к прочтению.