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

Содержание

• 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}

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

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

Десятичная система: 10⁰, 10¹, 10², 10³, 10⁴,…, 10ⁿ,…

Двоичная система: 2⁰, 2¹, 2², 2³, 2⁴,…, 2ⁿ,…

Восьмеричная система: 8⁰, 8¹, 8², 8³, 8⁴,…, 8ⁿ,…

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

A=a_n-1a_n-2…a₁a₀.a_-1…a_-m

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

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

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

А = ± (a_n-1q^n-1+a_n-2q^n-2+ … +a₀q⁰+a_-1q^-1+a_-2q^-2+ … +a_-mq^-m)

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

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

А₁₀ = 4·10³ + 7·10² + 1·10¹ + 8·10⁰ + 6·10^-1 + 3·10^-2

Двоичное число А₂ = 1001,1 = 1·2³ + 0·2² + 0·2¹ + 1·2⁰ + 1·2^-1

Восьмеричное число А₈ = 7764,1 = 7·8³ + 7·8² + 6·8¹ + 4·8⁰ + 1·8^-1

Шестнадцатеричное число А₁₆ = 3АF16 = 3·16² + 10·16¹ + 15·16⁰

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: х ? 16^m. Затем определяем число r вхождений степени 16^m в число х. Наконец, 16_ичную цифру r записываем в результирующее число в разряд с номером m. Число x заменяем на меньшее число х - r · 16^m. Если новое число х = 0, то алгоритм заканчивается, и остальные разряды результата заполняем нулями. В противном случае, переходим к следующей итерации.

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

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

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

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

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

Последние строки кратных единиц были дополнены ГОСТом в 1991. Вычисления с числами, представленными в десятично-буквенном виде, можно осуществлять без перехода в десятичную СС. Например, 32 Т / 256 К = 2⁴⁵ / 2¹⁸ = 2²⁷ = 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_ичной СС 0x11² = 0x121, 0x12² = 0x144, 0x13² = 0x169.

Пример. Десятичное число 0,1 нельзя представить в виде конечной 2_ичной дроби A = 0, a_-1…a_-m = a_-12^-1 + a_-22^-2 +… + a_-m2^-m. В противном случае, умножая равенство 0,1 = А на 10·2^m, получим 2^m = 10·(a_-12^m-1 +
a_-22^m-2 +… + a_-m2⁰). Последнее равенство невозможно, так как правая часть делится на 5, а левая - нет.

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

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

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

x = 5 = 0000 0101

+

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

____________________

0 = 0 = 0000 0000

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

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

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

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

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

Построим область корректного сложения для типа char.

char x, y, z;

x = y = 100;

z = x + y;

Нарисуем в системе координат (x, y) множество, для которого z будет содержать корректный ответ. Имеем систему

решением которой является шестиугольник.

Рис. 1. Диапазон корректного сложения

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

Вещественные типы всегда имеют знак.

Определение 3. Нормализованной формой ненулевого числа x называется запись x = M10^p, где M - мантисса, 0,1 M < 1, p - порядок числа х.

Нормализованная форма числа единственна.

Таблица 4. Вещественные типы данных

Определение 4. Машинным нулем для данного вещественного типа называется минимальное положительное число того же типа

m₀ = min {x: x > 0}.

Определение 5. Машинным эпсилон для данного вещественного типа называется минимальное число того же типа, для которого 1 + x > 1

m = min {x: 1 + x > 1}.

Определение 6. Машинной бесконечностью для данного вещественного типа называется максимальное число того же типа

m = max{x}.

По диапазону типа можно определить m₀, m. Машинный эпсилон определяется размером мантиссы. Так, например, для типа float имеем

m₀ = 3,410^-38, m = 3,410³⁸, m 10^-8.

Определение 7. «Правым соседом» числа x данного вещественного типа назовем минимальное число y того же типа, для которого x < y

«Правый сосед» х = min {y: x < y}.

«Правый сосед» числа х больше самого х на величину равную

m 10^{порядок числа х}.

Приближенно можно считать, что «правый сосед» числа х х + m x.

Например, для типа float «правый сосед» числа 10¹⁰ 10¹⁰ + 10^-8 10¹⁰ = 10¹⁰ + 100.

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

Параметры типа в таблице 4 связаны между собой.

Задача. Вещественный тип doom занимает 15 байт, под порядок отведено 30 бит. Определить остальные параметры этого типа.

Решение. Порядок занимает 30 бит, поэтому минимальное двоичное значение порядка равно -2²⁹. Для перевода этого числа к десятичному основанию решим показательное уравнение -2²⁹ = -10^х. Логарифмируя по основанию 10, получаем х = 29 lg2 29 0,3010 = 8,729. Таким образом, m₀ равен 0,5 10^{-161290865,49} 1,54 10^-161290865.

Мантисса в двоичной системе счисления занимает 90 бит, из которых один бит определяет знак мантиссы. Так как первые знаки двоичной мантиссы равны 0,1 и всегда одинаковы, то под них память не отводится. Поэтому остальные 89 бит мантиссы занимают разряды с номерами от -2 до -90. «Правый сосед» единицы равен 0,100…001₂ 2¹, где последняя единица стоит в -90_ом разряде. Тогда

m = 2^-89 = 10^{-89 lg(2)} = 10^-26,79 = 6,17 10^-26

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

Для кодирования символов с помощью одного байта используется ASCII_таблица (American Standard Code for Information Interchage)

В ASCII_таблице содержатся различные символы и соответствующие им коды. Например, символу `0' соответствует код 0x30 = 48. Символы и строки хранятся в памяти в виде соответствующих кодов из ASCII_таблицы. Например, строка «123» в памяти будет храниться в виде последовательности байт 0х31 0х32 0х33 0х00. Иногда строки, у которых 0 является признаком конца, называют asciiz_строками.

Таблица 5. ASCII - таблица символов

Символу `b' соответствует «ASCII_код» 0x62. В десятичной системе это будет 98, а в двоичной - 01100010. Код символа `b' вы можете посмотреть из ASCII_таблицы. Таблицы символов для разных шрифтов можно найти с помощью программы Таблица Символов: Пуск - Стандартные - Системные утилиты - Таблица Символов).

В русской кодировочной странице 866 буква Ё имеет код 0xF0, а буква ё - код 0хF1.

В языке Си символьные константы обозначаются `\xxx', где ххх - код этого символа, записанный в восьмеричной СС. Иначе говоря,
`\xxx' - это код символа, у которого код равен ххх.

Примеры. 1. Количество букв в английском алфавите равно
`Z' - `A' + 1.

2. Количество букв в русском алфавите равно `Я' - `А' + 2.

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

Для облегчения вычерчивания и нахождения на схеме символов рекомендуется поле листа разбивать на зоны. Размеры зон устанавливают с учетом минимальных размеров символов, изображенных на данном листе. Допускается один символ размещать в двух и более зонах, если размер символа превышает размер зоны. Координаты зоны проставляют: по горизонтали - арабскими цифрами слева направо в верхней части листа; по вертикали - прописными буквами латинского алфавита сверху вниз в левой части листа. Координаты зон в виде сочетания букв и цифр присваивают символам, вписанным в поля этих зон, например: A1, A2, A3, B1, B2, B3 и т.д. Если поле листа не разбито на зоны, символам присваивают порядковые номера.

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

Сокращения слов и аббревиатуры, кроме стандартных и общепринятых, должны быть расшифрованы в нижней части поля схемы или в документе, к которому эта схема относится. Записи внутри символа должны быть представлены так, чтобы их можно было читать слева направо и сверху вниз, независимо от направления потока. (вид а должен быть прочитан как вид б).

Рис. 2. Эквивалентные фрагменты схемы алгоритма

Таблица 6. Соединитель

Таблица 7. Межстраничный соединитель

Таблица 8. Линии потока

Таблица 9. Возможные варианты отображения решения

Таблица 10

Символы в схемах алгоритмов

Размер a должен выбираться из ряда 10, 15, 20 мм. Допускается увеличивать размер a на число, кратное 5. Размер b равен 1,5  a. При ручном выполнении схем алгоритмов и программ допускается устанавливать b равным 2  a.