Системы счисления и представления типов данных

Системы счисления и представления типов данных

Содержание

1.Позиционные системы счисления. 3

2.Переходы между основными системами счисления. 5

3.Основные 16‑ичные константы.. 5

4.Реализация целочисленных операций. 7

5.Представление отрицательных чисел. 8

6.Целочисленные типы данных в языке Си. 9

7.Вещественные типы данных в языке Си. 10

8.Кодирование символов. 12

9.Схемы алгоритмов. 14

1. Позиционные системы счисления

Позиционные системы счисления (СС) – это системы счисления, в которых количественный эквивалент каждой цифры зависит от ее положения (позиции) в записи числа. Например:

1) шестидесятиричная (Древний Вавилон) – первая позиционная система счисления. До сих пор при измерении времени используется основание равное 60 (1 мин = 60 с, 1 ч = 60 мин);

2) двенадцатеричная система счисления (широкое распространение получила в XIX в. Число12 – «дюжина»: в сутках две дюжины часов. Счет не по пальцам. а по суставам пальцев. На каждом пальце руки, кроме большого, по 3 сустава – всего 12;

3) в настоящее время наиболее распространенными позиционными системами счисления являются десятичная, двоичная, восьмеричная и шестнадцатеричная.

Система счисления – способ записи (изображения) чисел. Символы, при помощи которых записывается число, называются цифрами. Алфавитом системы счисления называется совокупность различных цифр, используемых в позиционной системе счисления для записи чисел. Например: Алфавиты некоторых позиционных систем счисления. Десятичная система: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Двоичная система: {0, 1}

Восьмеричная система: {0, 1, 2, 3, 4, 5, 6, 7}

Шестнадцатеричная система: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}

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

Базисом позиционной системы счисления называется последовательность чисел, каждое из которых задает количественное значение или «вес» каждого разряда. Например: Базисы некоторых позиционных систем счисления.

Десятичная система: 100
, 101
, 102
, 103
, 104
,…, 10n
,…

Двоичная система: 20
, 21
, 22
, 23
, 24
,…, 2n
,…

Восьмеричная система: 80
, 81
, 82
, 83
, 84
,…, 8n
,…

Свернутой формой записи числа называется запись в виде

A=an
-1
an
-2
…a1
a0
.a-1
…a-
m

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

Пример
. Десятичное число 4718,63, двоичное число 1001,1, восьмеричное число 7764,1, шестнадцатеричное число 3АF16

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

А= ± (an-1
qn-1
+an-2
qn-2
+ … +a0
q0
+a-1
q-1
+a-2
q-2
+ … +a-
m
q-
m
)

Здесь А – само число, q – основание системы счисления, ai
– цифры, принадлежащие алфавиту данной системы счисления, n – число целых разрядов числа, m – число дробных разрядов числа. Развернутая форма записи числа – сумма произведений коэффициентов на степени основания системы счисления.

Пример
. Десятичное число А10
= 4718,63 в развернутой форме запишется так:

А10
= 4·103
+ 7·102
+ 1·101
+ 8·100
+ 6·10-1
+ 3·10-2

Двоичное число А2
= 1001,1 = 1·23
+ 0·22
+ 0·21
+ 1·20
+ 1·2-1

Восьмеричное число А8
= 7764,1 = 7·83
+ 7·82
+ 6·81
+ 4·80
+ 1·8-1

Шестнадцатеричное число А16
= 3АF16 = 3·162
+ 10·161
+ 15·160

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

Основные СС имеют основания 2, 8,10, 16. Системы с основаниями 2, 8 и 16 являются родственными, так как их основания являются степенями двойки. Переходы между ними реализуются легко.

2 ® 8. Двоичное число разбивается справа налево на триады (тройки цифр) и каждая триада заменяется на 8‑ичную цифру.

2 ® 16. Двоичное число разбивается справа налево на тетрады (четверки цифр) и каждая тетрада заменяется на 16‑ичную цифру.

8 ® 16 и 16 ® 8. Преобразование идет через двоичную СС.

Любое основание ® 10. Осуществляется по определению позиционной системы счисления.

10 ® 16. Имеется два способа преобразования.

1. Метод деления «уголком» строит результирующее 16‑ичное число от младших цифр к старшим. Для этого запоминаются целые остатки от деления исходного числа на 16, пока частное не станет равным 0. Записывая эти остатки в обратном порядке, получим ответ.

2. Метод «вычерпывания» состоит из нескольких итераций. На каждой итерации исходное число х оценивается снизу максимальной степенью m нового основания p= 16: х ≥ 16m
. Затем определяем число r вхождений степени 16m
в число х. Наконец, 16‑ичную цифру r записываем в результирующее число в разряд с номером m. Число x заменяем на меньшее число х – r · 16m
. Если новое число х = 0, то алгоритм заканчивается, и остальные разряды результата заполняем нулями. В противном случае, переходим к следующей итерации.

3. Основные 16‑ичные константы

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

Таблица 1.Шестнадцатеричные константы

16‑ичная константа	Десятично-буквенное значение	Примечания
0х10	24 = 16	Размер параграфа
0х100	28 = 256	Размер физического сектора
0х200	512	Размер кластера на дискете
0х400	210 = 1024 = К	Килобайт
0х1000	4 К
0х10000	64 К	Размер сегмента
0хА0000	640 К	Верхняя граница ОЗУ для размещения исполняемого кода в DOS
0х100000	220 = М	Мегабайт

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

Таблица 2. Степени числа 2

Показатель степени	Степень	Примечания
0	1
1	2
2	4
3	8
4	16
5	32
6	64
7	128
8	256
9	512
10	К = 1024 » 103 , К	Килобайт, Kilobyte
20	М = К·К = К2 » 106 , М	Мегабайт, Megabyte
30	Г = К3 » 109 , G	Гигабайт, Gigabyte
40	Т = К4 = М2 » 1012 , T	Терабайт, Terabyte
50	П » 1015 , P	Петабайт, Petabyte
60	Э » 1018 , E	Экзабайт, Exabyte
70	З » 1021 , Z	Зетабайт, Zettabyte
80	Й » 1024 , Y	Йотабайт, Yottabyte

Последние строки кратных единиц были дополнены ГОСТом в 1991. Вычисления с числами, представленными в десятично-буквенном виде, можно осуществлять без перехода в десятичную СС. Например, 32 Т / 256 К = 245
/ 218
= 227
= 128 М.

Таблицы 1 и 2 позволяют переводить 16‑ичные числа в десятично-буквенную запись без применения вычислительных средств. Например, 0х7D8A30 = 7·0x100000 + 13·0x10000 + 8·0x1000 + 10·0x100 + 3·16 = 7 M + 13·64 K + 8·4 K + 10·(K/4) + 48 = 7 M + 866,5 K + 48.

Отметим, что для десятично-буквенных чисел не выполняется дистрибутивный закон, то есть 1 М + 100 К не равен 1,1 М.

4. Реализация целочисленных операций

Представление чисел в компьютере осуществляется в двоичной СС. Однако для краткости записи чисел используют родственную 16‑ичную СС.

Определение 1
. Логическим адресом ячейки памяти в ОЗУ с 20‑битной адресной шиной называется запись xxxx:yyyy, где хххх – шестнадцатеричный сегментный адрес, yyyy – шестнадцатеричное смещение. Физическим адресом этой ячейки называется число xxxx0 + yyyy.

Пример
. Область кода программы расположена с ячейки 55А3:3000 по ячейку 9EEF:A0FF. Оценить размер области в килобайтах.

Решение
. Физический адрес начала области 0х55А30 + 0х3000 = 0х58A30, конца области 0х9EEF0 + 0хA0FF = 0хA8FEF. Размер этой области равен 0хA8FEF– 0х58A30 + 1 = 0x505C0 = 5·64 К + 0·4 К + 10· (К/4) + 12·16= (320 + 2,5) К + 192 = 322,5 К + 192.

Определение 2
. Нормализованным адресом ячейки памяти ОЗУ с 20‑битной адресной шиной называется запись xxxx:yyyy, где хххх – шестнадцатеричное число, yyyy – шестнадцатеричное смещение, не превосходящее размера параграфа, то есть из диапазона от 0 до 15.

Арифметические операции сложения, вычитания, умножения и деления с 16‑ичными числами осуществляются аналогично 10‑ичным числам, то есть «столбиком». Однако, имеются некоторые отличия.

Пример
. Критерии деления 16‑ичного целого числа на 3 и на 5 выглядят одинаково: сумма цифр должна делится, соответственно, на 3 и на 5.

Пример
. Оказывается в 16‑ичной СС 0x112
= 0x121, 0x122
= 0x144, 0x132
= 0x169.

Пример
. Десятичное число 0,1 нельзя представить в виде конечной 2‑ичной дроби A= 0, a-1
…a-
m
= a-1
2-1
+ a-2
2-2
+… + a-
m
2-
m
. В противном случае, умножая равенство 0,1 = А на 10·2m
, получим 2m
= 10·(a-1
2m
-1
+ a-2
2m
-2
+… + a-
m
20
). Последнее равенство невозможно, так как правая часть делится на 5, а левая – нет.

5. Представление отрицательных чисел

Целые отрицательные числа хранятся в компьютере в двоичном «дополнительном» коде: положительное двоичное число необходимо побитово инвертировать и прибавить единицу.

Этот код основан на простом соображении, что x+ (-x) = 0 при сложении двоичных чисел столбиком. При этом единица, которая переходит из старшего 7‑го бита в несуществующий 8‑ой бит, пропадает. Например, для однобайтного числа x = 5 имеем

x = 5 = 0000 0101

+

– x = -5 = **** ****

____________________

0 = 0 = 0000 0000

Теперь конструируем число -5 = 1111 1011.

6. Целочисленные типы данных в языке Си

Таблица 3. Целочисленные типы данных

Название типа	Размер в байтах	Диапазон
unsigned char	1	0 … 255, 0. 28 -1
char, signed char	1	-128 … 127, -27 … 27 -1
unsigned int	2	0. 65535, 0. 216 -1, 0…64K–1
int, signed int	2	-32758 … 32757, -215 … 215 - 1, -32 K… 32 K– 1
unsignedlong	4	0… 232 - 1, 0… 4 M– 1
long	4	-231… 231 - 1, 0… 4 M– 1

По умолчанию целые десятичные константы имеют тип int. Поэтому все целые числа должны содержаться в диапазоне -32758… 32757. Например, запись x = 100000 будет ошибочна независимо от типа переменной x. Для обозначения целой константы типа long используется суффикс l. Тогда инициализация longx = 100000l будет корректна.

Компилятор не проверяет выход результата целочисленного выражения за диапазон типа. Запись longx = 20000 + 20000 будет ошибочна, так как 40000 не содержится в диапазоне типа int. Это будет «хорошо скрытая» ошибка. Реально x будет содержать значение 40000 – 64 К. Запись longx = 20000l + 20000 будет уже корректна, так как результат будет иметь уже тип long.