Двоичная математика для начинающих

В обычной жизни мы привыкли к десятичной системе — у нас есть десять цифр от 0 до 9. Если мы складываем 5 и 6, то получаем 11: места для одной цифры в ответе уже не хватает, и мы переносим единицу в следующий разряд (в десятки).

Компьютер делает абсолютно то же самое, только у него всего две цифры: 0 и 1. Сложение в двоичной системе выглядит очень просто: 0 + 0 = 0, 1 + 0 = 1. А вот 1 + 1 равно 2, но цифры «2» у компьютера нет! Поэтому происходит переполнение разряда: двойка записывается как 10 — в текущий разряд пишется 0, а единица переносится в следующий, прямо как мы переносим десятки при сложении в столбик.

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

Разряды и их веса

У каждой позиции в двоичном числе есть свой вес — степень двойки. Для 8-битного числа веса выглядят так:

Число — это сумма весов тех разрядов, где стоит единица. Например, 113 — это 64 + 32 + 16 + 1, и в двоичной записи оно выглядит как 01110001. А 29 — это 16 + 8 + 4 + 1, то есть 00011101.

Как считать в двоичной

Сложение начинается с младшего, самого правого разряда. Единственное правило, которое нужно запомнить: 1 + 1 = 0 и единица «в уме», в следующий разряд. Вспомни: двоичная «10» — это десятичная двойка, поэтому и получается «0 пишем, 1 в уме».

Разберём на простом примере — сложим 3 и 5. Три — это 0011, пять — 0101:

  0011
+ 0101
------
  1000

Считаем поразрядно справа налево: 1 + 1 = 0 и 1 в уме; 1 + 0 + 1 (из ума) = 0 и 1 в уме; 0 + 1 + 1 (из ума) = 0 и 1 в уме; 0 + 0 + 1 (из ума) = 1. Получаем 1000 — это 8.

Так же работает каскад сумматоров в процессоре: каждый бит складывается отдельно, а перенос передаётся соседу слева. А из каких вентилей собирается этот «столбик», рассказывает статья «Анатомия сумматора».

Большой пример: 113 + 29

Теперь посмотрим на пару посерьёзнее: 113 (01110001) и 29 (00011101). Складываем в столбик. Для каждого разряда распишем все колонки: значения битов, перенос на входе и результат:

Собираем сумму по разрядам сверху вниз: 10001110. Переводим обратно в десятичную: 128 + 8 + 4 + 2 = 142. Сошлось!

Обрати внимание на цепочку переноса: он бежит от младшего разряда к старшему, как волна, — из нулевого разряда в первый, потом из четвёртого в пятый, из пятого в шестой и из шестого в седьмой. Именно так считает настоящий каскад сумматоров.

Переполнение

Максимальное 8-битное число — 255, когда все разряды заполнены единицами. А что будет, если результат не помещается? Например, 200 + 100 = 300, а это больше 255. Старший перенос уходит «за край», за пределы восьмого разряда, — и восьми бит уже не хватает. Это и есть переполнение.

В процессорах переполнение отслеживается отдельно: на самом старшем сумматоре перенос «за край» сообщает о том, что результат слишком велик для шины. В игре на уровне 1.8 именно так проверяется правильность 8-битного сумматора ADDER8.

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

1. Складывать слева направо. Сложение всегда начинается с младшего, правого разряда — как в школьном столбике.

2. Забывать перенос. 1 + 1 = 0, но единица обязательно уходит в следующий разряд; без неё сумма будет занижена.

3. Путать веса разрядов. У старшего разряда 8-битного числа вес 128, а не 256. 256 — это вес девятого разряда, которого у восьми бит просто нет.

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

Резюме

1. В двоичной системе всего две цифры — 0 и 1, а переполнение разряда превращается в перенос в следующий.

2. Вес разряда — это степень двойки: для 8 бит это 128, 64, 32, 16, 8, 4, 2, 1.

3. Число равно сумме весов единичных разрядов: 113 = 01110001, 29 = 00011101.

4. Сложение идёт справа налево, и 1 + 1 даёт 0 плюс перенос 1: 3 + 5 = 0011 + 0101 = 1000 = 8.

5. Перенос бежит по разрядам, как волна: 113 + 29 = 142 = 10001110.

6. Переполнение — когда результат не помещается в 8 бит, то есть равен 256 или больше.

На уровне 1.6–1.8 тебе предстоит пройти путь от полусумматора (1.6) через полный сумматор (1.7) до 8-битного сумматора ADDER8 (1.8) — и впервые в игре собрать схему, которая сама выполняет сложение в столбик по правилам этой статьи.