Двоичная система

Двоичная (бинарная) система счисления – позиционная система счисления с основанием 2, использующая только две цифры: 0 и 1.

Основание системы – это количество различных цифр-символов в ней. У двоичной системы то же устройство, что и у десятичной, только «алфавит» цифр в ней в пять раз меньше – не 0–9 (десять цифр), а всего 0 и 1 (две цифры). Все правила позиционной записи при этом сохраняются без изменений.

Причина, по которой именно такая система лежит в основе устройства компьютера – физическая, а не математическая. С помощью электронных компонентов человек может надёжно различать всего два состояния: ток есть / тока нет, напряжение выше порога / ниже порога. Пытаться различать десять уровней напряжения (как для десятичных цифр) гораздо менее надёжно: любая помеха способна исказить сигнал и превратить, скажем, «7» в «6».

Один такой разряд – одно состояние «есть / нет» – называют битом:

Бит – один разряд двоичного числа; принимает одно из двух значений, 0 или 1.

Первый электронный компьютер общего назначения – ENIAC (1945, разработчики Джон Эккерт и Джон Мокли) – хранил числа в десятичном виде: под каждый разряд отводилось кольцо из десяти ламп-триггеров, и такая схема была громоздкой и не слишком надёжной.

Джон фон Нейман участвовал в проекте как консультант, а в том же 1945 году в отчёте «First Draft of a Report on the EDVAC» предложил для следующего компьютера, EDVAC, перейти на двоичное представление чисел – оно заметно упрощает схемы умножения и деления и надёжнее для электроники. Это решение и легло в основу всех современных компьютеров – включая тот, с которого вы сейчас читаете этот текст.

Общее правило позиционной записи: вес каждого разряда равен основанию системы в степени номера разряда (разряды считают справа налево, начиная с нуля). Подставим основание b = 2:

$N = a_0 \cdot 2^0 + a_1 \cdot 2^1 + a_2 \cdot 2^2 + \dots$

где $a_i$ – цифра $i$-го разряда (0 или 1).

То есть веса разрядов в двоичной системе – это степени двойки:

Эту строчку стоит выучить наизусть – она понадобится постоянно, а на экзамене под рукой не будет ни калькулятора, ни Python. Заодно запомните ориентир: $2^{10} = 1024$ – то самое число, из-за которого в килобайте 1024 байта, а не 1000.

Например, запись $101_2$ расшифровывается так: $1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 4 + 0 + 1 = 5$. (Полный разбор перевода в десятичную систему – в уроке 2.4, здесь важно только понять принцип.)

В десятичной системе, когда цифра в разряде доходит до максимума (9) и нужно прибавить ещё единицу, она обнуляется, а единица переносится в следующий разряд: 9 + 1 = 10. Механизм тот же самый в счётчике одометра автомобиля.

В двоичной системе работает ровно то же правило – но поскольку максимальная цифра здесь не 9, а всего 1, перенос происходит гораздо чаще: уже при 1 + 1.

Посчитаем от 0 до 8:

Обратите внимание на переход 1 → 10: единица «переполнила» разряд и перенеслась левее, а на её месте появился 0 – точно так же, как 9 → 10 в привычной десятичной системе. И ещё одна закономерность из таблицы: новый разряд появляется ровно на числах 2, 4, 8 – то есть на степенях двойки.

Ниже – восемь битов. Кликайте по любому, чтобы переключить его между 0 и 1, и смотрите, как меняется разложение по весам разрядов и итоговое десятичное число. Попробуйте собрать 5 – то самое число из разминки.

У виджета выше ровно восемь битов, и это не случайное число: 8 битов – это байт, основная единица памяти. Возникает естественный вопрос: а какое самое большое число в них поместится?

Каждый бит независимо принимает одно из двух значений. Один бит даёт 2 варианта (0 и 1), два бита – 4 (00, 01, 10, 11), три бита – 8. Каждый добавленный бит удваивает количество вариантов, поэтому в n битах помещается $2^n$ разных чисел: от 0 до $2^n - 1$.

Обратите внимание на «минус один»: чисел ровно $2^n$, но одно из них – ноль, поэтому наибольшее значение на единицу меньше. Это самая частая ошибка в задачах на диапазоны: в байте помещается 256 разных значений, но максимальное из них – 255, а не 256.