Теоретическая Информатика

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

1.Определение двоичной системы счисления

1°. О с н о в н ы е с в е д е н и я

Двоичная система счисления — позиционная система счис-

ления, состоящая только из двух цифр 0 и 1.

Двоичное число — число, записанное двоичными цифрами. Это самая простая система счисления с минимальным ос-

нованием 2. Она используется в компьютерах по причинам:

1)простота аппаратной реализации: 1 — есть сигнал, 0 — нет;

2)самое сложное действие таблицы умножения — это 12 × 12 = 12, таблицы сложения — 12 + 12 = 102.

Итак, число 10 в разных системах счисления имеет разное

количественное значение. Для различения таких значений основание системы пишется после числа в виде нижнего ин- декса. Этот индекс всегда находится в десятичной системе. Ин- декс можно опускать при очевидном контексте.

Приведем таблицы умножения, сложения и вычитания двоичных чисел. Видно, что таблица сложения сложнее таб- лицы умножения; возможно, слово «сложение» происходит от «сложный».

Т а б л и ц а 1 . 8

Таблица умножения двоичных чисел

× 0 1

0 0 0

1 0 1

Т а б л и ц а 1 . 9

Таблицы сложения и вычитания двоичных чисел

46 Глава 1. Числа

Выпишем первые натуральные двоичные числа от 0 до 16. Это можно сделать, используя следующее правило.

Основное свойство натуральных чисел: следующее натураль-

ное число больше предыдущего на 1.

Применяя это свойство, получаем (только все время нужно помнить, что 12 + 12 = 102): 12 + 12 = 102 («десять»), 102 + 12 = 112

Неудобно, но приходится называть двоичное число на русском языке по аналогии с десятичным, хотя такое название не соответствует количественному значению двоичного числа. Например, двоичное число 102 «де- сять» обозначает два предмета, а двоичное число 112 «одиннадцать» — три предмета.

При внимательном изучении табл. 1.11 получаем, что име- ется:

1)только 2 однозначных двоичных числа 0 и 1;

2)4 = 22 двузначных двоичных числа: 00, 01, 102 и 112;

3)8 = 23 трехзначных двоичных чисел от 000 до 1112;

4)16 = 24 четырехзначных двоичных чисел от 0000 до 11112. Рассуждая по аналогии и учитывая подобный опыт подсче-

та количества таких чисел для десятичной системы (табл. 1.7), получим табл. 1.12 (все числа в которой записаны в десятич- ной системе).

Т а б л и ц а 1 . 1 2

Количество однозначных, двузначных и т. д. до десятизначных двоичных чисел

Однозначными двоичными числами можно пронумеровать от 1 до 2 объектов, двузначными — от 1 до 4, трехзначными —

1—8 и т. д.

Значащие цифры в двоичной системе имеют те же свойст- ва, что и в десятичной. Например, значащими цифрами числа

00110,0110100 являются цифры 1100110100.

Рассмотрим четыре элементарные арифметические опера- ции над целыми двоичными числами.

Операции над двоичными числами производятся точно так же, как и над десятичными числами.

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

12 + 12 = 102, 12 + 12 + 12 = 112, а 102 − 12 = 12.

1. Двоичные числа складываются столбиком точно так же, как и десятичные. На рис. 1.13 показано сложение двух пар двоичных чисел: 1100102 (=50) и 1101112 (=55), 1101112 (=55) и 1110112 (=59).

Когда при сложении текущих разрядов двух чисел в дво- ичной системе получается 102 или 112, то 1 переходит в сле- дующий разряд.

Рис. 1.13. Сложение двоичных чисел:

а) 1100102 + 1101112 = 11010012 (50 + 55 = 105); б) 1101112 + 1110112 = 11100102 (55 + 59 = 114)

2. При вычитании следует помнить, что уменьшаемое не должно быть меньше вычитаемого. Если уменьшаемое меньше вычитаемого, то разность переворачивается, а результат ум- ножается на −1.

Двоичные числа вычитаются столбиком точно так же, как и десятичные. На рис. 1.14 показано вычитание двух пар двоич-

ных чисел: 11001102 (=102) и 10012 (=9), 1011112 (=47) и 111000002 (=224).

При вычитании в двоичной системе если из 0 вычитается 1, то этот 0 в вычитаемом становится 102, ближайшая слева 1 ста- новится 0, а все нули между ними становятся 1.

Рис. 1.14. Вычитание двоичных чисел:

а) 11001102 − 10012 = 10111012 (102 − 9 = 93); б) 1011112 − 111000002 = −101100012 (47 − 224 = −177)

3. Двоичные числа умножаются столбиком точно так же, как и десятичные. На рис. 1.15 показано умножение двух пар двоичных чисел: 100012 (=17) и 10112 (=11); 1010012 (=41) и 11010002 (=104).

Становится очевидным, что самое сложное в умножении двоичных чисел — сложение нескольких чисел, равных первому сомножителю, цифры которого просто сдвинуты по разрядам влево.

Рис. 1.15. Умножение двоичных чисел:

а) 100012 × 10112 = 101110112 (17 × 11 = 187); б) 1010012 × 11010002 = 10000101010002 (41 × 104 = 4264)

4. Двоичные числа делятся столбиком точно так же, как и десятичные. На рис. 1.16 показано деление двух пар двоичных чисел: 1001002 (=36) и 112 (=3); 100011112 (=143) и 11012 (=13).

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

Рис. 1.16. Деление двоичных чисел:

а) 1001002 : 112 = 11002 (36 : 3 = 12); б) 100011112 : 11012 = 10112 (143 : 13 = 11)

3°. У п р а ж н е н и я

1.Составьте таблицу с десятичными и двоичными числами от 0 до 32. Используйте ее для перевода чисел.

2.К одной телефонной станции подключено 100 номеров, к другой — 1000. Одной компьютерной программе доступны 5000 ячеек памяти, другой — 8000. Двоичными числами какой минимальной длины можно закодировать эти номера и ячейки?

4.Вычислите в двоичной системе счисления.

а. 111012 + 100012; 110112 + 100112; 101112 + 101112; 111112 + 101112.

б. 111002 − 100012; 110102 − 100112; 101102 − 101112; 111102 − 101112.

в. 111012 100012; 110112 100112; 101112 101112; 111112 101112.

г. 110112/112; 110012/1012; 11111102/1102; 1111112/10012.

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

1°. П е р е в о д д в о и ч н ы х ч и с е л в д е с я т и ч н ы е Будем заниматься переводом только натуральных чисел. Как было сказано выше, любое натуральное число можно

разложить единственным образом по степеням десятки с ко- эффициентами, принимающими значение от 0 до 9.

Точно так же любое натуральное число M > 0 можно разло- жить единственным образом по степеням двойки:

M = A0 + A2 22 +K+ AN−2 2N−2 + AN−1 2N−1 , AN−1 = 1.

Равенство AN −1 = 1 означает, что все степени двойки со степе-

нями, большими или равными N, равны 0. Остальные коэф- фициенты разложения A0 , A1 , K, AN −2 равны либо 0, либо 1.

Нуль является исключением: все его коэффициенты равны нулю: 0 = 0.

Примеры.

а. 1 = 20. б. 2 = 21.

в. 3 = 20 + 21.

г. 4 = 22.

Это разложение по степеням двойки и положено в основу перевода двоичных чисел в десятичные и обратно.

Кроме того, любое натуральное число M можно записать в двоичной системе счисления, причем двоичные цифры совпа- дают с коэффициентами разложения числа M по степеням двойки, но расположены в обратном порядке по сравнению с предыдущей формулой:

M = AN−1AN−2 KA1A0 2 , AN−1 = 1.

Равенство AN −1 = 1, как и прежде, означает, что старший раз-

ряд числа равен 1. Остальные N − 1 цифры A0 , A1 , K, AN −2 рав-

ны либо 0, либо 1.

Объединяя две последние формулы, получаем самый из- вестный и простой алгоритм перевода двоичных чисел в деся- тичные.

52 Глава 1. Числа

А л г о р и т м 1 . 1 7 . П е р е в о д д в о и ч н о г о ч и с л а в д е с я т и ч н о е .

N-значное двоичное число переводится в десятичное по следующей формуле:

AN−1AN−2 KA1A0 2 = A0 + A1 21 +K+ AN−2 2N−2 + AN−1 2N−1 , AN−1 = 1,

где все числа в правой части равенства записаны в десятичной системе.

Примеры.

а. 100102 = 0 + 1 2 + 0 4 + 0 8 + 1 16 = 18. б. 110102 = 0 + 1 2 + 0 + 1 8 + 1 16 = 26. в. 1000102 = 1 2 + 1 32 = 34.

г. 1010102 = 2 + 8 + 32 = 42.

Несмотря на то, что это самый простой из всех алгоритмов перевода между двоичными и десятичными числами, четвер- тый пример показывает, что алгоритм 1.17 можно немного уп- ростить.

А л г о р и т м 1 . 1 8 . У п р о щ е н н ы й п е р е в о д д в о - и ч н ы х ч и с е л в д е с я т и ч н ы е .

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

Примеры.

а. 1 0 1 2 = 20 + 22 = 1 + 4 = 5.

2 1 0

б. 1 1 0 0 1 1 2 = 20 + 21 + 24 + 25 = 1 + 2 + 16 + 32 = 51.

5 4 3 2 1 0

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

Примеры.

а. 1 1 0 2 = 4 + 2 = 6.

4 2 1

б. 1 1 0 1 1 0 2 = 32 + 16 + 4 + 2 = 54.

32 16 8 4 2 1

2°. П е р е в о д д е с я т и ч н ы х ч и с е л в д в о и ч н ы е Приведенное в п. 1° разложение произвольного натураль-

ного числа M > 0 по степеням двойки

M = A0 + A1 21 + A2 22 +K+ AN−2 2N−2 + 2N−1

позволяет также по числу M вычислить коэффициенты разло- жения A0 , A1 , K, AN −2 и максимальную ненулевую степень

двойки N − 1.

Заметим, что, поскольку формулу можно переписать в виде

M = A0 + 2(A1 + A2 21 +K+ AN−2 2N−3 + 2N−2 ),

то при делении числа M на 2 остаток равен A0 , а частное равно

A1 + A2 21 +K+ AN−2 2N−3 + 2N−2 = A1 + 2(A2 +K+ AN−2 2N−4 + 2N−3 ).

Тогда при делении этого частного на 2 остаток равен A1 , и т. д.:

коэффициент A0 равен остатку от делении M на 21 ;

коэффициент A1 равен остатку от делении M на 22 ;

…

коэффициент AN −1 равен всегда 1: остатку от делении M на 2N.

Другими словами, коэффициент AI в разложении произ-

вольного числа M по степеням двойки равен остатку от деле- ния произвольного числа M на два в степени I + 1. Здесь I — это индекс, пробегающий значения от 0 до N − 1, где N − 1 — это максимальная степень двойки, не превышающая исходного

числа M:

2N −1 M < 2N.

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

M = AN−1AN−2 KA2A1A0 2 ,

получаем алгоритм перевода десятичного числа в двоичное. Алгоритм прост, поскольку деление производится в хорошо знакомой десятичной системе.

вд в о и ч н о е .

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

санными справа налево.

2.Процесс деления прекращается, когда частное становится равным нулю.

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

Рис. 1.20. Перевод десятичных чисел в двоичные:

а) 20 = 101002; б) 30 = 111102

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

Рассмотрим теперь алгоритм перевода десятичных чисел в двоичные слева направо, в котором цифры двоичного числа находятся, начиная со старшего разряда.

Снова воспользуемся разложением произвольного нату- рального числа M > 0 по степеням двойки

M= A0 + A1 21 +K+ AN−2 2N−2 + 2N−1

итем фактом, что имеется показатель степени N такой, что

2N −1 M < 2N.