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

Системы счисления
Позиционные
Двоичная система счисления Троичная система счисления Восьмеричная система счисления Десятичная система счисления Двенадцатеричная система счисления Шестнадцатеричная система счисления Шестидесятеричная система счисления Нега-позиционная система счисления
Непозиционные
Унарная система счисления Римская система счисления
Смешанные
Фибоначчиева система счисления

Двои́чная систе́ма счисле́ния — это один из видов позиционных систем счисления. Основание данной системы равно двум, то есть используется только два символа для записи чисел — цифры 0 и 1. При этом, как и во всякой позиционной системе, значение (вес) цифры зависит от занимаемого ею места (позиции или разряда).

Благодаря тому, что символам 0 и 1 можно сопоставить два устойчивых состояния электронных вентилей «выключено/включено», двоичная система счисления используется практически во всей современной цифровой технике для представления чисел при реализации математических операций.

Стоит отметить, что английский термин binary digit — двоичная цифра, дал название единице измерения информации — бит.

История

Двоичная система счисления изучалась в Европе в XVI - XVII веках, однако системы, связанные с двоичными числами, появились ранее во многих культурах, включая древний Египет, Китай и Индию. Лейбниц был особенно вдохновлен китайским «И Цзин» (Двоичная система счисления в И Цзин используется для интерпретации четвертичной техники гадания).

В 1605 году Френсис Бэкон описал систему, в которой буквы алфавита могут быть сведены к последовательностям двоичных цифр, которые в свою очередь могут быть закодированы как едва заметные изменения шрифта в любых случайных текстах. Важным шагом в становлении общей теории двоичного кодирования является замечание о том, что указанный метод может быть использован применительно к любым объектам (Шифр Бэкона).

Современная двоичная система была полностью описана Лейбницем в XVII веке в работе Explication de l’Arithmétique Binaire. В системе счисления Лейбница были использованы цифры 0 и 1, как и в современной двоичной системе. Как человек, увлекающийся китайской культурой, Лейбниц знал о книге Перемен и заметил, что гексаграммы соответствуют двоичным числам от 0 до 111111.

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

В 1937 году Клод Шеннон представил к защите кандидатскую диссертацию «Символический анализ релейных и переключательных схем», в которой булева алгебра и двоичная арифметика были использованы применительно к релейно-контактным схемам. На диссертации Шеннона по существу основана вся современная цифровая техника.

В ноябре 1937 года Джордж Штибиц, впоследствии работавший в Bell Labs, создал на базе реле двоичный полусумматор «Model K Аdder», который выполнял двоичное сложение. В конце 1938 года Bell Labs развернула исследовательскую программу во главе со Штибицом. Созданный под его руководством калькулятор комплексных чисел, завершённый 8 января 1940 года, умел выполнять операции с комплексными числами.

Восcозданная модель компьютера Z1

Во время демонстрации на конференции American Mathematical Society в Дартмутском колледже 11 сентября 1940 года Штибиц продемонстрировал возможность посылки команд удалённому калькулятору комплексных чисел по телефонной линии с использованием телетайпа. Это была первая попытка использования удалённой вычислительной машины посредством телефонной линии. Среди участников конференции, бывших свидетелями демонстрации, были Джон фон Нейман, Джон Мокли и Норберт Винер.

В 1938 году немецкий инженер Конрад Цузе завершает разработку устройства под названием Z1. Это был механический вычислитель с электрическим приводом и с использованием электромеханических реле. Он был программируемым и использовал двоичную систему счисления.

Представление двоичных чисел

Чтобы обозначить, в какой системе счисления записано число, его снабжают указателем справа внизу. Например, запись числа 5 в десятичной форме обозначают как 5₁₀ и то же число в двоичной форме записи обозначают как 101₂. В двоичной системе счисления (как и в других системах счисления, кроме десятичной) знаки читаются по одному. Например, число 101₂ произносится «один ноль один».

Натуральные числа

В общем виде натуральное число, записываемое в двоичной системе счисления как $(a_{n-1}a_{n-2}\dots a_{1}a_{0})_{2}$, выглядит следующим образом:

$(a_{n-1}a_{n-2}\dots a_{1}a_{0})_{2}=\sum _{k=0}^{n-1}a_{k}2^{k},$

где:

$n$ — количество цифр (знаков) в числе,

$a_{k}$ — значения цифр из множества {0,1},

$k$ — порядковый номер позиции цифры (вес разряда).

Таким образом, по общему правилу представления числа в позиционной системе счисления, двоичное число в развёрнутом виде выглядит как сумма произведений числовых значений цифр из множества {0,1} на степень основания, то есть числа 2. Значение степени определяется порядковым номером позиции (разряда) справа налево, начиная с нулевой.

Например: 101₂ = (1·2² + 0·2¹ + 1·2⁰)₁₀

Отрицательные числа

Отрицательные двоичные числа обозначаются так же как и десятичные: знаком «—» перед числом. А именно, отрицательное целое число в двоичной системе счисления $(-a_{n-1}a_{n-2}\dots a_{1}a_{0})_{2}$ выглядит следующим образом:

$(-a_{n-1}a_{n-2}\dots a_{1}a_{0})_{2}=-\sum _{k=0}^{n-1}a_{k}2^{k}.$

В вычислительной технике широко используется запись отрицательных двоичных чисел в дополнительном коде (обратный код числа, дополненный единицей в младшем разряде).

Дробные числа

Дробное число, записываемое в двоичной системе счисления как $(a_{n-1}a_{n-2}\dots a_{1}a_{0},a_{-1}a_{-2}\dots a_{-(m-1)}a_{-m})_{2}$, имеет вид:

$(a_{n-1}a_{n-2}\dots a_{1}a_{0},a_{-1}a_{-2}\dots a_{-(m-1)}a_{-m})_{2}=\sum _{k=-m}^{n-1}a_{k}2^{k},$

где:

$m$ — количество цифр дробной части числа,

$a_{k}$ — значения цифр из множества {0,1}.

Веса цифр дробной части равны отрицательным степенями двойки, например:

101,101₂ = (1·2² + 0·2¹ + 1·2⁰ + 1·2^–1 + 0·2^–2 + 1·2^–3)₁₀ = 5,625₁₀

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

Арифметические действия над двоичными числами

В двоичной системе счисления арифметические операции выполняются по тем же правилам, что и во всех позиционных системах.

Правила сложения и вычитания

• Правило сложения одноразрядных двоичных чисел

   0 + 0 =  0
   1 + 0 =  1
   0 + 1 =  1
   1 + 1 = 10 (в младший разряд записывается ноль с переносом единицы в старший разряд)

При сложении многоразрядных чисел применяется правило поразрядного сложения.
Например, при сложении чисел (13 + 5)₁₀ = (1101 + 101)₂ в результате получаем число 10010₂ = 18₁₀:

     1101
   +  101
    ------
    10010

• Правило вычитания одноразрядных двоичных чисел

   0 − 0 = 0
   1 − 0 = 1
   1 − 1 = 0
   0 − 1 = 1 (при вычитании из нуля единицы происходит заём единицы из старшего разряда)

При вычитании многоразрядных чисел применяется правило поразрядного вычитания.
Например, при вычитании чисел (18 − 5)₁₀ = (10010 − 101)₂ в результате получаем число 1110₂ = 13₁₀

     1110
   —  101
     ----
     1001

Правила умножения и деления

• Правило умножения одноразрядных двоичных чисел

   0 × 0 = 0
   1 × 0 = 0
   0 × 1 = 0
   1 × 1 = 1

При умножении многоразрядных чисел применяется правило поразрядного умножения с последующим сложением результатов (умножение «в столбик»)
Например, при умножении чисел (14 × 2)₁₀ = (1110 × 10)₂ в результате получаем число 11110₂ = 28₁₀

     1110
     × 10
   ------
   + 0000
    1110
   ------
    11100

• При делении также необходимо выполнять промежуточные действия, каковыми являются умножение и вычитание (деление «в столбик»).
  Например, при делении чисел (30 : 6)₁₀ = (11110 × 110)₂ в результате получаем число 101₂ = 5₁₀

   11110| 110
        | ---
  −110  | 101
     ---
     110
    −110
     ---
       0

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

Преобразование чисел из двоичной системы счисления в десятичную

Преобразовать число из двоичной системы счисления в десятичную можно следующим образом: каждый разряд двоичного числа необходимо умножить на 2ⁿ, где n - номер разряда, начиная с 0. Затем суммировать полученные значения.

Допустим, дано двоичное число 110001. Для перевода в десятичное число необходимо представить его в развёрнутом виде следующим образом:

110001₂ = (1·2⁵ + 1·2⁴ + 0·2³ + 0·2² + 0·2¹ + 1·2⁰)₁₀

далее произвести суммирование тех разрядов, где произведение не равно нулю:

(32 + 16 + 1)₁₀ = 49₁₀

Преобразование дробных двоичных чисел в десятичные

Преобразование дробных двоичных чисел в десятичные производится по тому же правилу с учётом того, что дробная часть двоичного числа представлена разрядами с отрицательными степенями двойки. Например, преобразуем дробное двоичное число 1011010,101 в форму десятичного числа:

1011010,101₂ = (1·2⁶ + 0·2⁵ + 1·2⁴ + 1·2³ + 0·2² + 1·2¹ + 0·2⁰ + 1·2⁻¹ + 0·2⁻² + 1·2⁻³)₁₀ = (64 + 16 + 8 + 2 + 0,5 + 0,125 )₁₀ = 90,625₁₀

Для удобства перевода целой части двоичного числа можно воспользоваться таблицей десятичных значений степеней двойки (до значения 2¹⁰)

210	29	28	27	26	25	24	23	22	21	20
1024	512	256	128	64	32	16	8	4	2	1

Перевод дробной части методом Горнера

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

Рассмотрим перевод двоичной дроби 0,101₂ в форму десятичной дроби. Ступеней деления будет столько, сколько знаков в двоичном числе после запятой, делителем является основание системы счисления, то есть в данном случае число два:

 1. (0 + 1)/2 = 0,5
 2. (0,5 + 0)/2 = 0,25    (в качестве слагаемого используется результат предыдущей ступени деления = 0,5)
 3. (0,25 + 1)/2 = 0,625  (в качестве слагаемого используется результат предыдущей ступени деления = 0,25)

Ответом будет результат последнего перехода, то есть 0,101₂= 0,625₁₀

Преобразование десятичных чисел в двоичные

Одним из алгоритмов перевода десятичного числа в двоичное является деление нацело на 2 с последующим «сбором» двоичного числа из остатков деления. Например, для перевода десятичного числа 14 в двоичное представление необходимо выполнить следующие действия:

  14 / 2 = 7, остаток 0 — младший разряд двоичного числа
   7 / 2 = 3, остаток 1
   3 / 2 = 1, остаток 1
   1 / 2 = 0, остаток 1 — старший разряд двоичного числа

Таким образом, результат преобразования будет следующим: 14₁₀ = 1110₂

Преобразование дробных десятичных чисел в двоичные

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

• дробь умножается на основание двоичной системы счисления (2);
• в полученном произведении выделяется целая часть, которая принимается в качестве старшего разряда числа в двоичной системе счисления;
• в следующем шаге полученная в результате произведения дробная часть опять умножается на 2;
• алгоритм завершается, если дробная часть полученного произведения равна нулю или если достигнута требуемая точность вычислений.

Например, для перевода дробного десятичного числа 206,625 в дробное двоичное число необходимо выполнить следующие действия:

• производим перевод целой части, где в итоге получаем 206₁₀ = 11001110₂;
• далее действуем в соответствии с алгоритмом перевода дробной части; целые части произведений, полученных в каждом шаге (выделены жирным шрифтом), являются разрядами искомой дробной части:

  0,625·2 = 1,25
  0,25·2  = 0,5
  0,5·2   = 1,0

Таким образом, получаем значение дробной части 0,625₁₀ = 101₂ и в целом имеем результат: 206,625₁₀ = 11001110,101₂

Применение двоичных чисел

Благодаря тому, что множеству символов {0,1} можно сопоставить два устойчивых состояния электронных вентилей «выключено/включено», основное применение двоичная система счисления нашла в вычислительной технике, в цифровых системах контроля и управления. Ядром любого процессора является арифметико-логическое устройство (АЛУ), которое воспринимает управляющие сигналы и операнды в виде двоичных кодов и чисел. Результаты обработки информации также формируются в виде двоичных чисел и результатов логических сопряжений. Этот процесс развился потому, что двоичные сигналы имеют высокую надёжность при передаче и хранении информации, а правила выполнения команд просты и удобны.

Литература

Босова Л. Л., Босова А. Ю. Информатика. Учебник для 8 класса (рус.) / Вед.редактор Полежаева О. — М.: «Бином», 2013. — 155 с. — ISBN 978-5-9963-1166-8. Шаманов А. П. Системы счисления и представление чисел в ЭВМ. Учебное пособие (рус.). — Екатеринбург: Уральский университет, 2016. — 52 с. — ISBN 978-5-7996-1719-6.

Примечания

Данная статья имеет статус «готовой». Это не говорит о качестве статьи, однако в ней уже в достаточной степени раскрыта основная тема. Если вы хотите улучшить статью — правьте смело!