Как вентили складывают числа

Чтобы сложить два бита, хватает одного вентиля XOR и одного AND. Соедини цепочкой четыре полных сумматора, и можно будет складывать любые два числа от 0 до 15.

Попробуй сам, прежде чем читать дальше. Сложи 0101 и 0011 на бумаге в двоичной системе так же, как складываешь в десятичной, и записывай каждый перенос над следующим столбцом. Нужны всего три факта: 0 + 0 = 0, 0 + 1 = 1 и 1 + 1 = 10, то есть пишем 0 и переносим 1. Если пришёл перенос, то 1 + 1 + 1 = 11, значит, пишешь 1 и переносишь 1. Решение в следующем абзаце, так что сначала закрой его.

Вот решение. Крайний правый столбец: 1 + 1 = 10, пишем 0, переносим 1. Следующий: 0 + 1 плюс перенос снова дают 10, пишем 0, переносим 1. Следующий: 1 + 0 плюс перенос, 10, пишем 0, переносим 1. Крайний левый: 0 + 0 плюс перенос дают 1. Ответ 1000, то есть 8, и 5 + 3 = 8. Перенос был в трёх столбцах из четырёх. Калькулятор, игра и электронная таблица в итоге делают именно это. Внутри процессора каждый столбец обрабатывают несколько вентилей, и сцена начинается с этой же суммы. Потом попробуй в ней 9 + 8. Для этого нужен пятый бит.

Крайнему правому столбцу хватает двух вентилей

Посмотри на крайний правый столбец отдельно. Бит ответа в нём, сумма, равен 1, когда ровно один вход равен 1. Это правило XOR. Перенос равен 1, только когда оба входа равны 1. Это правило AND. Значит, вентили XOR и AND рядом, на которые подаются одни и те же два входа, складывают два бита. Эта маленькая схема называется полусумматором. «Полу» она потому, что не может принять перенос из столбца справа.

В остальных столбцах складываются три бита

В каждом другом столбце встречаются три бита: по одному из каждого числа и перенос справа. Полный сумматор принимает все три. Его сумма равна A XOR B XOR входной перенос: она равна 1, когда нечётное число битов из трёх равно 1. Его выходной перенос равен 1, когда хотя бы два из них равны 1. Из двух полусумматоров и вентиля OR получается один полный сумматор. Поставь в ряд четыре полных сумматора, соедини выходной перенос каждого с входным переносом сумматора слева, и получится 4-битный сумматор. Каждый перенос должен пробежать справа налево, прежде чем последний столбец установится, поэтому такая схема называется сумматором с последовательным переносом. Настоящие процессоры складывают 64-битные числа более хитрыми схемами, которые вычисляют переносы заранее, но правило в каждом столбце то же.

Что происходит, когда ответ слишком большой

Четыре бита вмещают числа от 0 до 15. Сложи 9 и 8, и настоящий ответ 17 в двоичной записи равен 10001, а это пять битов. Регистр, который хранит только четыре бита, запишет 0001, то есть 1, а лишний перенос слева служит сигналом тревоги. Это переполнение. 15 + 1 в четырёх битах даёт 0000. Когда это случается, процессор ставит флаг, чтобы программы могли это заметить. Для вычитания используется тот же сумматор. Чтобы вычислить A − B, процессор переворачивает каждый бит B и прибавляет 1, получая дополнительный код B, затем прибавляет его к A и отбрасывает лишний перенос. Для 5 − 3 в четырёх битах: 3 записывается как 0011, после переворота получается 1100, плюс 1 даёт 1101. Затем 0101 + 1101 = 10010, и если оставить четыре бита, получится 0010, то есть 2.

Умножение сводится к сдвигам и сложению

Умножение собирается из тех же деталей. В двоичной системе умножение на 2 сдвигает каждый бит на один разряд влево, так же как умножение на 10 в десятичной добавляет ноль: 0011 (3) превращается в 0110 (6). Для 5 × 3 заметь, что 3 = 2 + 1. Значит, 5 × 3 = 5 × 2 + 5 × 1 = 1010 + 0101 = 1111, то есть 15. Схема умножителя сдвигает и складывает именно так, беря по одному биты второго числа, равные 1.