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

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

вд в о и ч н о е .

1.Для данного числа M найдем подбором такую степень

двойки N, при которой

2N −1 M < 2N.

Следовательно,

M= 2N−1 +K

2.Уменьшим число M, вычтя из него 2N−1 :

L = M − 2N−1.

Если L равно 0, то представление числа M в двоичной систе- ме найдено и имеет ровно N цифр:

M = 10K000 2.

Если L не равно 0, то переходим к шагу 3.

3. Для нового числа L найдем подбором такое число K, что

2K −1 L < 2 K.

Следовательно,

M= 2N−1 +K+ 2K −1 +K

4.Уменьшим число L, вычтя из него 2K −1 :

L ← L − 2K−1.

Снова получаем, что если L равно 0, то представление числа M в двоичной системе найдено и имеет вид

M = AN−1AN−2 KA2A1A0 2 ,

где цифры AI , индексы которых совпадают со степенями дво-

ек полученного разложения числа, равны 1, а остальные циф- ры равны 0.

Если L не равно 0, то переходим к шагу 3.

Примеры.

а. Переведем 5 в двоичную систему. Подбором находим, что

22 < 5 < 23.

Следовательно,

5 = 22 +K

Находим разность 5 − 22 = 5 − 4 = 1. Подбором находим, что

20 1 < 21.

Следовательно,

5 = 22 + 20 +K

Находим разность 1 − 20 = 1 − 1 = 0. Следовательно, 5 = 22 + 20 , т. е. 5 = 1012.

б. Переведем 54 в двоичную систему.

25 < 54 < 26 , 54 − 32 = 22, 24 < 22 < 25 , 22 − 16 = 6, 22 < 6 < 23 , 6 − 4 = 2,

21 < 2 < 22 , 2 − 2 = 0, Получаем, что 54 = 25 + 24 + 22 + 21 , т. е. 51 = 1101102.

3°. У п р а ж н е н и я 1. Переведите следующие десятичные числа в двоичные,

пользуясь таблицами.

15; 20; 25; 30; 40; 60; 80; 100.

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

200; 300; 400; 800.

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

1000; 2000; 3000; 10000.

4. Переведите следующие двоичные числа в десятичные.

10101010102; 11011011012; 11001100112; 10010010012.

§3. Представление байта

1.Двоичное представление байта

1°. Б и т . Б а й т Бит — единица измерения количества информации, опре-

деляемая как количество информации в испытании с двумя независимыми равновероятными исходами.

Название «бит» происходит от английского сокращения “bit”, которое происходит либо от слов “BInary elemenT” — «двоичный элемент», либо от слов “BInary digiT” — «двоич- ный разряд».

Бит — это выбор ответа «да» или «нет» на вопрос. Элек- тронным представлением бита является ситуация «есть сигнал/нет сигнала». В математике и информатике «да» обычно обозначается 1, «нет» — 0.

Бит удобно представлять однозначным двоичным числом. Поэтому одним битом можно закодировать два объекта.

Но бит очень уж мал.

Наиболее распространена более большая единица измере- ния информации — байт.

Байт — наименьшая составная единица памяти компьюте- ра, равная 8 битам.

Получаем первый компьютерный инвариант 8: 1 байт = 8 бит.

Почему один байт равен 8 битам, не меньше и не больше? Потому что у здания Большого театра в Москве 8 колонн?

Кодовые таблицы содержат количество кодов, рав- ное два в степени восемь.

Байт представляется 8-значным двоичным числом. Од- ним байтом можно закодировать 256 объектов, приписав каж- дому объекту одно из 256 8-значных двоичных чисел от 0000 00002 до 1111 11112, равные десятичным числам от 0 до 255.

Получаем второй компьютерный инвариант 256:

256 = 28.

При развитии вычислительной техники потребовались производные единицы от байта, аналогичные единицам, как километры, которые в 1000 раз больше метра, или килограм- мы, которые в 1000 раз больше грамма.

Однако при составлении производных единиц от байта ис- пользуется множитель не 1000, а снова степень числа 2 — тре-

тий компьютерный инвариант 1024: 1024 = 210.

Почему 1024? Возможно, потому, что число 1024 име- ет три хорошие свойства:

1)оно на три порядка больше единицы;

2)это число является степенью двойки;

3)1024 подозрительно почти равно 1000.

Перечислим известные производные единицы байта. 1 килобайт = 1 Кбайт = 1 Кб = 1 К = 1024 байта.

1 мегабайт = 1 Мбайт = 1 Мб = 1 М = 1024 К. 1 гигабайт = 1 Гбайт = 1 Гб = 1 Г = 1024 М. 1 терабайт = 1 Тбайт = 1 Тб = 1 Т = 1024 Г. 1 петабайт = 1 Пбайт = 1 Пб = 1 П = 1024 Т. 1 экзабайт = 1 Эбайт = 1 Эб = 1 Э = 1024 П.

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

Воспользовавшись близостью чисел 1024 и 1000, не- мецкий компьютерный журнал напечатал изображение новой денежной единицы — одной киломарки, равной 1024 маркам. К сожалению, затем произошел переход не к киломаркам, а к евро.

Примеры.

а. 1 Мб = 210 Кб. б. 1 Кб = 2−10 Мб.

в. 1 Мб = 210 Кб = 210 210 б = 220 б.

г. 1 б = 2−10 Кб = 2−10 2−10 Мб = 2−20 Мб.

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

Т а б л и ц а 1 . 2 2

Коэффициенты перевода производных единиц от байта

Пусть нужно перевести 5 Гб в байты. В этой таблице в стро- ке Гб и столбце байт стоит коэффициент 230. Следовательно, 5 Гб = 5 230 б.

Аналогично 7 Кб = 7 2−20 Гб.

3°. У п р а ж н е н и я 1. Пересчитайте в мегабайты.

а. 10240 Кб; 1024000 Кб. б. 10 Гб; 1000 Гб.

в. 20 б; 1000 б.

г. 20 Тб; 1000 Тб.

2. Шестнадцатеричное представление байта

1°. Ш е с т н а д ц а т е р и ч н а я с и с т е м а с ч и с л е н и я Рассмотрим еще одну недесятичную систему счисления,

которая часто используется при программировании и в Ин- тернете.

В некотором смысле эта система счисления противополож- на двоичной. Двоичная система имеет количество цифр, меньшее десяти, а шестнадцатеричная — большее десяти.

Шестнадцатеричная система счисления — позиционная сис-

тема счисления, состоящая из шестнадцати цифр

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Шестнадцатеричное число — число, записанное шестнадца- теричными цифрами.

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

Как и при работе с двоичной системой, выпишем сначала первые шестнадцатеричные числа от 0 до 32. Снова воспользу- емся основным свойством натуральных чисел, гласящим, что следующее число равно предыдущему плюс 1.

При вычислении первых шестнадцатеричных чисел в че- тырех местах могут возникнуть для новичка характерные трудности, «пороги», связанные с тем, что количество шестна- дцатеричных цифр больше десяти.

Перечислим эти четыре «порога»:

9 + 1 = A;

F + 1 = 1016; 1916 + 1 = 1A;

1F + 1 = 2016.

Заметим, что с ростом основания системы разрядность чи- сел снижается (см. также прил. 1.2)!

Т а б л и ц а 1 . 2 3

Двоичные, десятичные и шестнадцатеричные числа от 0 до 32

Двоичное Десятич- 16-ричное Двоичное Десятич- 16-ричное

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

Имея таблицу с шестнадцатеричными числами от 0 до 32, легко составить следующую таблицу сложения шестнадцате- ричных чисел.

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

Т а б л и ц а 1 . 2 4

Шестнадцатеричная таблица сложения

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

прил. 1.3.

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

Шестнадцатеричные числа переводятся в десятичные ана- логично переводу двоичных, поэтому на этом вопросе мы не будем останавливаться.

Интерес представляет простой алгоритм перевода шестна- дцатеричных чисел в двоичные. Следующая технология осно- вана на том факте, что однозначное шестнадцатеричное число является четырехзначным двоичным числом (см. табл. 1.23).

А л г о р и т м 1 . 2 5 . П е р е в о д ш е с т н а д ц а т е р и ч - н о г о ч и с л а в д в о и ч н о е .

1.Каждая цифра шестнадцатеричного числа записывается четырехзначным двоичным числом.

2.Незначащие нули, стоящие слева, можно отбросить.

Примеры.

а. D = 11012.

б. 2A = 0010 10102 = 1010102.

Опишем теперь простой алгоритм перевода чисел из дво- ичной системы в шестнадцатеричную, который является про- сто обращением предыдущего алгоритма 1.25.

Следующая технология основана на том факте, что четы- рехзначное двоичное число является однозначным шестна- дцатеричным числом (см. табл. 1.23).

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

ше с т н а д ц а т е р и ч н о е .

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

2.Если для последней четверки не хватает цифр, слева от двоичного числа дописываются нули.

Примеры.

а. 11012 = D.

б. 1010102 = 0010 10102 = 2A.

Байты, которые записываются двоичными числами от 0000 00002 до 1111 11112, гораздо проще записывать соответст- вующими шестнадцатеричными числами от 0016 до FF16. На- пример, символ уникода кодируется 2 байтами и может при- нимать значения от 00 0016 до FF FF16, а глубина цвета задается 3 байтами и принимает значения от 00 00 0016 до FF FF FF16.

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

1.Переведите следующие шестнадцатеричные числа в де- сятичную систему по аналогии перевода двоичных чисел.

а. 8D. б. AB. в. 1BA. г. 2D8.

2.Переведите следующие шестнадцатеричные числа в дво- ичные.

а. 8D. б. AB. в. 1BA. г. 2D8.

3.Переведите следующие двоичные числа в шестнадцате- ричные.

а. 11 1011 11012. б. 111 1110 01112. в. 1001 1001 10012. г. 1111 1101 10112.