ПОРОГ
ОБЩАЯ ОСНОВА И БАЗОВАЯ ЛОГИКА: ОТ ОДНОГО ПРОВОДА ДО РАБОТАЮЩЕЙ ПРОГРАММЫ

Любое измерение напряжения — это сравнение, а не абсолютное число. Фраза «на проводе пять вольт» имеет смысл только тогда, когда всё остальное в схеме согласно с тем, что считать нулём, — с общей точкой отсчёта, землёй. Напряжение любого провода, высокое или низкое, — это на самом деле просто «насколько выше земли».

Цифровая логика использует эту общую землю, чтобы провести черту. Всё, что близко к земле, читается как LOW — цифра 0. Всё, что близко к напряжению питания, читается как HIGH — цифра 1. Промежуток между ними намеренно оставлен неопределённым, чтобы небольшая электрическая помеха никогда не превратила уверенный 0 в случайную 1.

Один провод в схеме из главы 1 несёт ровно один бит — одно «да» или «нет», HIGH или LOW. Сам по себе он не очень выразителен. Но выстройте в ряд несколько проводов — и каждая возможная комбинация их состояний становится отдельным узором; а всё, что представляет компьютер — числа, буквы, цвета, звук, — это просто имя, данное одному из этих узоров.

Добавьте ещё один провод — и число возможных узоров удваивается, потому что каждый узор, который могли составить прежние провода, теперь встречается дважды: один раз с новым проводом LOW, один раз — HIGH. Именно это удвоение объясняет, почему двоичная система вообще важна не только математикам: это ровно то, что даёт реальное количество проводов.

Логический элемент — это схема с одной задачей: посмотреть на входные напряжения и выдать HIGH или LOW по фиксированному правилу. Таких правил, которые стоит знать, немного, и всего трёх из них — И, ИЛИ и НЕ — достаточно, чтобы построить любое другое, включая каждое ветвление, которое когда-либо делает программа.

И выдаёт HIGH, только если оба входа HIGH. ИЛИ выдаёт HIGH, если хотя бы один вход HIGH. НЕ просто переворачивает то, что получает. Выберите элемент ниже, переключите входы — и посмотрите на его решение.

XOR («исключающее ИЛИ») выдаёт HIGH, когда входы не совпадают — ровно один из них HIGH, но не оба. Это не четвёртый фундаментальный элемент: соедините ИЛИ, И и два НЕ — и получите ровно ту же таблицу истинности. XOR заслуживает собственного обозначения лишь потому, что это именно та схема, которая складывает два бита, — см. главу 8.

Законы де Моргана — другое полезное сокращение: отрицание И равносильно ИЛИ от отрицаний, а отрицание ИЛИ равносильно И от отрицаний. Именно поэтому «не (идёт дождь и холодно)» означает ровно то же самое, что «не идёт дождь, или не холодно», — что на русском, что в кремнии.

Любой обычный языковой союз соответствует одному из элементов главы 3: «и» / «также» / «оба» — это И; «или» / «либо» — это ИЛИ; «не» — это НЕ. Скажите «если идёт дождь или наступила ночь, включи фары» — и вы уже написали элемент ИЛИ, просто ещё не нарисовали его.

Конструкция if/then/else пропускает выход элемента через развилку: путь THEN — когда условие HIGH, путь ELSE — когда LOW. Электрически ничего нового не происходит: это тот же элемент из главы 3, только теперь он решает, какая из двух инструкций реально выполнится.

Условие if/else из главы 5 выбирает лишь между двумя путями. Большинству реальных решений нужно больше двух вариантов, поэтому код выстраивает условия в лестницу: IF, затем серия ELSE IF, а в конце — ELSE как вариант по умолчанию. Компьютер проверяет каждую ступень сверху вниз и останавливается на первой, которая оказалась HIGH, — все ступени ниже полностью пропускаются, даже если они тоже были бы истинны.

Классический пример — шкала оценок: балл 85 технически также «не меньше 70» и «не меньше 60», но оценку присваивает только первая сработавшая ступень — «не меньше 80». Порядок важен: переставьте ступени лестницы местами — и балл 95 может случайно получить оценку F. Подвиньте ползунок балла ниже и посмотрите, какая ступень сработает.

Десятичный разряд — это степени десяти: цифра «3» в «300» означает 3×10². Двоичный разряд работает так же, только со степенями двойки — каждый бит вдвое «весомее» соседнего справа: бит HIGH добавляет к сумме степень двойки своей позиции, а бит LOW не добавляет ничего.

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

Сложение двух отдельных битов требует двух ответов: собственно суммы и того, произошло ли переполнение в следующий разряд, — переноса. Один только XOR вычисляет сумму (HIGH ровно тогда, когда биты не совпадают, — это и есть сложение без переноса), а один только И вычисляет перенос (переполнение даёт только 1+1). Эта пара называется полусумматором.

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

Остаток от деления — оператор % — это то, что остаётся после деления: 10 % 3 равно 1, потому что 3 умещается в 10 три раза, а 1 остаётся. «n делится на 3» — это просто короткая запись «n % 3 равно 0».

FizzBuzz — знаменитая разминка для собеседований по программированию — это просто лестница из главы 6, прогоняемая для каждого числа: вывести «FizzBuzz», если число делится и на 3, и на 5, «Fizz» — если только на 3, «Buzz» — если только на 5, иначе — само число; и эта двойная проверка обязана стоять на верхней ступени лестницы, иначе до неё просто не дойдёт очередь. Подвиньте N и посмотрите, как пересчитывается вся последовательность.

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

Этот приём также даёт отрицательным числам место среди обычных битов: при 4 битах 0111 — это +7, а 1000 — это −8, и всё промежуточное аккуратно встаёт на свои места, а старший бит бесплатно становится флагом знака: 0 — для неотрицательных, 1 — для отрицательных.

Наивный поиск по отсортированному списку проверяет каждую запись, пока не найдёт совпадение, — в худшем случае N сравнений для списка из N элементов. Бинарный поиск действует умнее: проверяет средний элемент одним IF и, в зависимости от того, оказался он больше или меньше искомого, отбрасывает половину оставшегося списка, даже не заглядывая в неё.

Каждое сравнение уменьшает вдвое то, что осталось, — это формула удвоения из главы 2, только в обратную сторону, так что худший случай — это просто сколько раз можно поделить N пополам, прежде чем дойти до 1: log₂ N, округлённый вверх. Подвиньте размер списка ниже и посмотрите, как разрыв между «проверить всё» и «проверить с умом» становится огромным.

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

А ветвление из главы 5 в «железе» превращается в мультиплексор: элемент, который смотрит на условие и переключает, какой из двух проводов реально дойдёт до следующего регистра. Каждая инструкция if, когда-либо выполненная любой программой, в конце концов компилируется именно в это — тикающее на чьём-то тактовом генераторе.

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

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