2. Простые типы данных
Эти типы обозначают множества целых чисел в различных диапазонах. Значения целого типа могут задаваться в десятичном, например, 5; -10, или шестнадцатеричном виде (шестнадцатеричном константы начинаются со знака $), например, $1A; $FFFF.
Размер в байтах
Диапазон допустимых значений
-128…127 (-2 7 …2 7 -1)
-32768…32767 (-2 15 …2 15 -1)
Над целыми числами допустимы следующие операции:
4 арифметических операции:
+ сложение * умножение b:=a*b;
— вычитание / деление c:=10/2-b;
2 дополнительных операции:
div – деление нацело b:=10 div 3 -> b=3; p:=32 div 5 -> p=6
mod – остаток от деления b:=10 mod 3 -> b=1; p:=32 mod 5 -> p=2
2.2 Вещественные типы
Группа вещественных типов обозначает множества вещественных значений в различных диапазонах. Вещественные числа могут задаваться в форме с фиксированной точкой (например, 3.14159265; –10.2) или с плавающей точкой (например, 1.2Е–2 = 1.210 -2 ; 2.1234Е15 = 2.123410 15 ).
Размер в байтах
Число значащих цифр
Операции над переменными вещественного типа:
4 арифметических операции: +, *, -, /
Типы результатов операций
Типы операндов
Тип результата
Хотя бы один вещественный
2.3 Cимвольный тип данных
Char 1 байт 256 значений
Значениями этого типа являются символы из набора ASCII – американского стандартного кода для обмена информацией.
Каждый символ имеет свой код от 0 до 255. Символы с кодами 0-127 – стандартные символы ASCII:
0-31 – управляющие символы;
32-47 – знаки препинания;
58-127 – латинские буквы.
Расширение кода ASCII: 128-255 – русские буквы, псевдографика (│, ┌, ┐, └, ┘…).
Символы, имеющие графическое представление, заключаются в кавычки: С=’*’. Для символов, не имеющих графического представления, используется знак #, после которого записывается код символа:
#
10 перевод строкиVar c: char;
#13 переход к началу строки x: integer;
#7 звуковой сигнал begin
#8 возврат на символ c:=’*’; x:=10;
Writeln(#7,a); writeln (#7,c,x,c);
Для переменных символьного типа допустимы операции сравнения, при этом сравниваются коды символов:
Коды прописных латинских букв: A — 65; B – 66; C – 67 и т.д.
Коды строчных латинских букв: a — 97; b – 98; c – 99 и т.д.
Для преобразования символа в число, равное коду символа, и наоборот, используются следующие функции:
chr(x) – преобразование ASCII-кода в символ; аргумент – целый 0-255;
ord(x) – преобразование символа в целое число.
1.Типы данных, виды. классификация, примеры
Привет, сегодня поговорим про типы данных, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое типы данных , настоятельно рекомендую прочитать все из категории Структуры данных.
Введение
Компьютер — это машина, которая обрабатывает информацию. Изучение компьютерных наук предполагает изучение того, каким образом эта информация организована внутри компьютера, как она обрабатывается и как может быть использована. Следовательно, для изучения предмета студенту особенно важно понять концепции организации информации и работы с ней.
Так как вычислительная техника базируется на изучении информации, то первый возникающий вопрос заключается в том, что такое информация. К сожалению, несмотря на то , что концепция информации является краеугольным камнем всей науки о вычислительной технике, на этот вопрос не может быть дано однозначного ответа. В этом контексте понятие "информация" в вычислительной технике сходно с понятием "точка", "прямая" и "плоскость" в геометрии — все это неопределенные термины, о которых могут быть сделаны некоторые утверждения и выводы, но которые не могут быть объяснены в терминах более элементарных понятий.
Базовой единицей информации является бит, который может принимать два взаимоисключающих значения. Если устройство может находиться более чем в двух состояниях, то тот факт, что оно находится в одном из этих состояний, уже требует нескольких битов информации.
Для представления двух возможных состояний некоторого бита используются двоичные цифры — нуль и единица.
Число битов, необходимых для кодирования символа в конкретной вычислительной машине, называется размером байта, а группа битов в этом числе называется байтом. Размер байта в большинстве компьютеров равен 8.
Память вычислительной машины представляет собой совокупность битов. в любой момент функционирования в ЭВМ каждый из битов памяти имеет значение 0 или 1 (сброшен или установлен). Состояние бита называется его значением или содержимым.
Биты в памяти ЭВМ группируются в элементы большего размера, например в байты. В некоторых ЭВМ несколько байтов объединяются в группы, называемые словами. Каждому такому элементу назначается адрес, который представляет собой имя, идентифицирующее конкретный элемент памяти среди аналогичных элементов. Этот адрес обычно числовой. Он называется ячейкой, а содержимое ячейки есть значение битов, которые ее составляют.
Итак, мы видим, что информация в ЭВМ сама по себе не имеет конкретного смысла. С некоторой конкретной битовой комбинацией может быть связано любое смысловое значение. Именно интерпретация битовой комбинации придает ей заданный смысл.
Метод интерпретации битовой информации часто называется типом данных. Каждая ЭВМ имеет свой набор типов данных.
Важно осознавать роль, выполняемую спецификацией типа в языках высокого уровня. Именно посредством подобных объявлений программист указывает на то, каким образом содержимое памяти ЭВМ интерпретируется программой. Эти объявления детерминируют объем памяти, необходимый для размещения отдельных элементов, способ интерпретации этих элементов и другие важные детали. Объявления также сообщают интерпретатору точное значение используемых символов операций.
часть 1. введение в теорию структур данных и алгоритмов их обработки
1. типы данных
В математике принято классифицировать переменные в соответствие с некоторыми важными характеристиками. Мы различаем вещественные, комплексные и логические переменные ,переменные ,представляющие собой отдельные значения, множества значений или множества множеств. В обработке данных понятие классификации играет такую же, если не большую роль. Мы будем придерживаться того принципа, что любая константа, переменная, выражение или функция относятся к некоторому типу.
Фактически тип характеризует множество значений, которые может принимать некоторая переменная или выражение и которые может формировать функция.
В информатике тип данных или просто тип представляет собой классификацию информационных сущностей (например, таких как значения или выражения ), определяющую возможность их использования в рамках заданной формальной системы. Понятие имеет несколько определений, которые могут частично пересекаться или приводить к тождественному содержанию. Наиболее принципиально различимых, хотя и не противоречащих друг другу, определений два:
- декларативное — тип есть множество допустимых значений , которые могут принимать данные, принадлежащие к этому типу;
- процедурное — тип определяется поведением, т.е. набором действий, которые можно осуществлять над данными, принадлежащими к этому типу.
Декларативное определение чаще всего используется в императивном программировании, процедурное — в параметрическом полиморфизме. Объектно-ориентированное программирование использует процедурное определение при описании взаимодействия компонентов программы, и декларативное — при описании реализации этих компонентов на ЭВМ, соответственно, рассматривая « класс -как-поведение» и «класс-как- объект в памяти».
Операция назначения типа информационным сущностям называется типизацией. Назначение и проверка согласования типов может осуществляться заранее (статическая типизация), непосредственно при использовании (динамическая типизация) или совмещать оба метода. Типы могут назначаться «раз и навсегда» (сильная типизация) или позволять себя изменять (слабая типизация) — см. сильная и слабая типизация.
Теория типов формально изучает типы и результаты от их назначения. Неотъемлемой частью большинства языков программирования являются системы типов, использующие типы для обеспечения той или иной степени типобезопасности . Лишь немногие языки могут считаться типизированными в полной мере, большинство языков предоставляет лишь некоторый уровень типизированности.
Понятие типобезопасности опирается преимущественно на процедурное определение типа. Например, попытка деления «числа» на «строку» будет отвергнута большинством языков, так как для этих типов не определено соответствующее поведение. Слабо типизированные языки тяготеют к декларативному определению. Например, «число» и «запись» имеют различное поведение, но значение адреса «записи» в памяти ЭВМ может иметь то же низкоуровневое представление, что и «число». Слабо типизированные языки предоставляют возможность нарушить[en] систему типов, назначив этому значению поведение «числа» посредством операцииприведения типа. Подобные трюки могут использоваться для повышения эффективности программ, но несут в себе риск крахов , и поэтому не допускаются вбезопасных языках.
К не полным по Тьюрингу языкам описания данных (таким как SGML) процедурное определение не применимо.
Единообразная обработка данных разных типов называется полиморфизмом.
Классификация типов днных
Существуют различные классификации типов и правил их назначения.
Например, типы делятся на примитивные и агрегатные (последние также называются составными, композитными или структурными). Примерами примитивных типовслужат вещественные, целое, логическое и др. Примерами агрегатных типов служат кортежи, массивы, списки и др. Нередко встречаются также предопределенные вспомогательные типы, полезные для промышленных разработок, такие так «время», «календарная дата» и пр.
Структурные (агрегатные) типы не следует отождествлять со структурами данных: одни структуры данных непосредственно воплощаются определенными структурными типами, но другие строятся посредством их композиции, чаще всего рекурсивной . Об этом говорит сайт https://intellect.icu . В последнем случае говорят о рекурсивных типах данных[en]. Примером структур данных, которые почти всегда строятся посредством композиции объектов рекурсивного типа, являются бинарные деревья .
По другой классификации типы делятся на самостоятельные и зависимые. Важными разновидностями последних являются ссылочные типы, частным случаем которых, в свою очередь, являются указатели. Ссылки (в том числе и указатели) представляют собой несоставной зависимый тип, значения которого являются адресом в памяти ЭВМ другого значения. Например, в языке Си тип «указатель на целое без знака» записывается как «unsigned *», в языке ML тип «ссылка на целое без знака» записывается как «word ref».
Также типы делятся на мономорфные и полиморфные (см. переменная типа).
Примеры
- примитивные типы, в том числе:
- логические типы
- целые типы
- вещественные типы
- обнуляемые типы
- массивы
- записи
- кортежи
- абстрактные типы ( АТД , англ . Об этом говорит сайт https://intellect.icu . ADT)
- вариантные типы
В большинстве языков программирования различают стандартные типы данных и типы, заданные пользователем. К стандартным относят 5 типов:
a) целый (INTEGER);
b) вещественный (REAL) ;
c) логический (BOOLEAN);
d) символьный (CHAR);
e) указательный (POINTER).
К пользовательским относят 2 типа:
a) перечисляемый;
b) диапазонный.
Любой тип данных должен быть охарактеризован областью значений и допустимыми операциями над этим типом данных.
https://amdy.su/wp-admin/options-general.php?page=ad-inserter.php#tab-8Кроме того в днамически типизированных языках программирования существует понятие — Истинноподобное значение.
Например В JavaScript истинноподобное (truthy) значение — это значение, рассматривающиеся как true в булевом контексте. К истинноподобным значениям относятся все значения кроме ложноподобных значений. То есть все значения истинноподобны кроме false , 0 , -0 , 0n , "" , null , undefined и NaN .
В булевых контекстах JavaScript использует механизм приведения типов.
Типы данных
Примитивные типы
- Логическое , истина или ложь.
- символ
- Числа с плавающей запятой , аппроксимация вещественных чисел с ограниченной точностью .
- Включая поплавки одинарной и двойной точности IEEE 754 , среди прочего
Составные типы или непримитивные типы
- Массив (например, String, представляющий собой массив символов)
- Запись (также называемая ассоциативным массивом, картой или структурой )
- Объединение ( объединение с тегами — это подмножество, также называемое вариантом , вариантной записью, размеченным объединением или непересекающимся объединением)
Абстрактные типы данных
- Контейнер
- Список
- Кортеж
- Multimap
- Задавать
- Мультисет (сумка)
- Стек
- Очередь (пример очереди с приоритетом )
- Двусторонняя очередь
- График (пример Tree , Heap )
Некоторые свойства абстрактных типов данных:
Состав порядок Уникальный Список да нет Ассоциативный массив нет да Задавать нет да Стек да нет Multimap нет нет Мультисет (сумка) нет нет Очередь да нет Порядок означает, что последовательность вставки имеет значение. Уникальный означает, что повторяющиеся элементы не допускаются на основании некоторых встроенных или, альтернативно, определяемых пользователем правил для сравнения элементов.
1.1 Целый тип — INTEGER
Этот тип включает некоторое подмножество целых, размер которого варьируется от машины к машине. Если для представления целых чисел в машине используется n разрядов, причем используется дополнительный код, то допустимые числа должны удовлетворять условию -2 n-1 <= x< 2 n-1 .
Считается, что все операции над данными этого типа выполняются точно и соответствуют обычным правилам арифметики. Если результат выходит за пределы представимого множества, то вычисления будут прерваны. Такое событие называется переполнением.
Числа делятся на знаковые и беззнаковые. Для каждого из них имеется свой диапазон значений:
a)(0..2 n -1) для беззнаковых чисел
b) (-2 N-1 .. 2 N-1 -1) для знаковых.
При обработке машиной чисел, используется формат со знаком. Если же машинное слово используется для записи и обработки команд и указателей, то в этом случае используется формат без знака.
Операции над целым типом:
d) Целочисленное деление.
e) Нахождение остатка по модулю.
f) Нахождение экстремума числа (минимума и максимума)
g) Реляционные операции (операции сравнения) (<,>,<=, >=,=,<>)
Во всех операциях, кроме реляционных, в результате получается целое число.
1.2 Вещественный тип — REAL
Вещественные типы образуют ряд подмножеств вещественных чисел, которые представлены в машинных форматах с плавающей точкой. Числа
в формате с плавающей точкой характеризуются целочисленными значениями мантиссы и порядка, которые определяют диапазон изменения
и количество верных знаков в представлении чисел вещественного типа.
X = +/- M * q (+/-P) — полулогарифмическая форма представления числа, показана на рисунке 2.
937,56 = 93756 * 10 -2 = 0,93756 * 10 3
Удвоенная точность необходима для того, чтобы увеличить точность мантиссы.
1.3 Логический тип — BOOLEAN
Стандартный логический тип Boolean (размер-1 байт) представляет собой тип данных, любой элемент которого может принимать лишь 2 значения: True и False.
Над логическими элементами данных выполняются логические операции. Основные из них:
a) Отрицание (NOT)
b) Конъюнкция (AND)
c) Дизъюнкция (OR)
Таблица истинности основных логических функций.
Логические значения получаются также при реляционных операциях с целыми числами.
1.4 Символьный тип — CHAR
Тип CHAR содержит 26 прописных латинских букв и 26 строчных, 10 арабских цифр и некоторое число других графических символов, например, знаки пунктуации.
Подмножества букв и цифр упорядочены и "соприкасаются", т.е.
("A"<= x)&(x <= "Z") — x представляет собой прописную букву
Тип CHAR содержит некоторый непечатаемый символ, пробел, его можно
использовать как разделитель.
c) Определения номера данной литеры в системе кодирования. ORD(Wi)
d) Нахождение литеры по номеру. CHR(i)
e) Вызов следующей литеры. SUCC(Wi)
f) Вызов предыдущей литеры. PRED(Wi)
1.5 Указательный тип — POINTER
Переменная типа указатель является физическим носителем адреса величины базового типа. Cтандартный тип-указатель Pointer дает указатель, не связанный ни с каким конкретным базовым типом. Этот тип совместим с любым другим типом-указателем.
b) Операции с беззнаковыми целыми числами.
При помощи этих операций можно вычислить адрес данных. В машинном виде эти типы занимают максимально возможную длину.
Например:
ABCD:1234 — значение указателя в шестнадцатеричной системе счисления — относительный адрес.
Первое число (ABCD) — адрес сегмента
Второе число (1234) — адрес внутри сегмента.
Получение абсолютного адреса из относительного:
Для получения абсолютного адреса необходимо произвести сдвиг адреса сегмента влево, и к полученному числу прибавить адрес внутреннего сегмента.
Например:
- Сдвигаем ABCD на один разряд влево. Получаем АВСD0.
- Прибавляем 1234. Полученный результат и является абсолютным адресом.
ACF04 — абсолютный адрес данного числа.
1.6 Стандартные типы пользователя
1.6.1 Перечисляемый
Перечисляемый тип определяется конечным набором значений, представленных списком идентификаторов в объявлении типа. Значениям из этого набора присваиваются номера в соответствии с той последовательностью, в которой перечислены идентификаторы. Формат
объявления перечисляемого типа таков:
Если идентификатор указан в списке значений перечисляемого типа, он считается именем константы, определенной в том блоке, где объявлен перечисляемый тип. Порядковые номера значений в объявлении перечисляемого типа определяются их позициями в списке идентификаторов, причем у первой константы в списке порядковый номер равен нулю. К данным перечисляемого типа относится, например, набор цветов:
TYPE <Цвет> = (Красный, Зеленый, Синий)
Операции те же, что и для символьного типа.
1.6.2 Диапазонный или интервальный
В любом порядковом типе можно выделить подмножество значений, определяемое минимальным и максимальным значениями, в которое входят все значения исходного типа, находящиеся в этих границах, включая сами границы. Такое подмножество определяет диапазонный тип. Он задается указанием минимального и максимального значений, разделенных двумя точками.
Минимальное значение при определении такого типа не должно быть больше максимального.
Самоприменение типов данных
Тип может быть параметризован другим типом, в соответствии с принципами абстракции и параметричности. Например, для реализации функции сортировки последовательностей нет необходимости знать все свойства составляющих ее элементов — необходимо лишь, чтобы они допускали операцию сравнения — и тогда составной тип «последовательность» может быть определен как параметрически полиморфный. Это означает, что его компоненты определяются с использованием не конкретных типов (таких как «целое» или «массив целых»), а параметров-типов. Такие параметры называются переменными типа (англ. type variable) — они используются в определении полиморфного типа так же, как параметры-значения в определении функции. Подстановка конкретных типов в качестве фактических параметров для полиморфного типа порождает мономорфный тип. Таким образом, параметрически полиморфный тип представляет собой конструктор типов, то есть оператор над типами в арифметике типов.
Определение функции сортировки как параметрически полиморфной означает, что она сортирует абстрактную последовательность, то есть последовательность из элементов некоторого (неизвестного) типа. Для функции в этом случае требуется знать о своем параметре лишь два свойства — то, что он представляет собойпоследовательность, и что для ее элементов определена операция сравнения. Рассмотрение параметров процедурным, а не декларативным, образом (т.е. их использование на основе поведения, а не значения) позволяет использовать одну функцию сортировки для любых последовательностей — для последовательностей целых чисел, для последовательностей строк, для последовательностей последовательностей булевых значений, и т. д. — и существенно повышает коэффициентповторного использования кода. Ту же гибкость обеспечивает и динамическая типизация, однако, в отличие от параметрического полиморфизма, первая приводит к накладным расходам. Параметрический полиморфизм наиболее развит в языках, типизированных по Хиндли — Милнеру, то есть потомках языка ML. В объектно-ориентированном программировании параметрический полиморфизм принято называть обобщенным программированием.
Несмотря на очевидные преимущества параметрического полиморфизма, порой возникает необходимость обеспечивать различное поведение для разных подтипов одного общего типа, либо аналогичное поведение для несовместимых типов — т.е. в тех или иных формах ad hoc полиморфизма. Однако, ему не существует математического обоснования, так что требование типобезопасности[en] долгое время затрудняло его использование. Ad hoc полиморфизм реализовывался внутри параметрически полиморфной системы типов посредством различных трюков. Для этой цели использовались либо вариантные типы[en], либо параметрические модули (функторы), либо так называемые «значения, индексированные типами» (англ. type-indexed values), которые, в свою очередь, также имеют ряд реализаций . Классы типов, появившиеся в языке Haskell, предоставили более изящное решение этой проблемы.
Если рассматриваемой информационной сущностью является тип, то назначение ей типа приведет к понятию «тип типа», или «метатип». В теории типов это понятие носит название «род типов» (англ. kind of a type или type kind). Например, род «*» включает все типы, а род «* -> *» включает все унарные конструкторы типов. Рода явным образом применяются при полнотиповом программировании — например, в виде конструкторов типов в языках семейства ML.
Расширение безопасной полиморфной системы типов классами[en] и родами типов сделало Haskell первым типизированным в полной мере языком. Полученная система типов оказала влияние на другие языки (например, Scala, Agda).
Ограниченная форма метатипов присутствует также в ряде объектно-ориентированных языков в форме метаклассов. В потомках языка Smalltalk (например, Python) всякая сущность в программе является объектом, имеющим тип, который сам также является объектом — таким образом, метатипы являются естественной частью языка. В языке C++ отдельно от основной системы типов языка реализована подсистема RTTI, также предоставляющая информацию о типе в виде специальной структуры.
Динамическое выяснение метатипов называется отражением (а также рефлексивностью или интроспекцией).
В математике, логике и компьютерных науках теорией типов считается какая-либо формальная система, являющаяся альтернативой наивной теории множеств, сопровождаемая классификацией элементов такой системы с помощью типов, образующих некоторую иерархию. Также под теорией типов понимают изучение подобных формализмов.
Теория типов — математически формализованная база для проектирования, анализа и изучения систем типов данных в теории языков программирования (раздел информатики). Многие программисты используют это понятие для обозначения любого аналитического труда, изучающего системы типов в языках программирования. В научных кругах под теорией типов чаще всего понимают более узкий раздел дискретной математики, в частности λ-исчисление с типами.
Современная теория типов была частично разработана в процессе разрешения парадокса Рассела и во многом базируется на работе Бертрана Рассела и Альфреда Уайтхеда «Principia mathematica»
Представление в компьютере
Наиболее заметным отличием реального программирования от формальной теории информации является рассмотрение вопросов эффективности не только в терминахО-нотации, но и с позиций экономической целесообразности воплощения тех или иных требований в физически изготовляемой ЭВМ. И в первую очередь это сказывается на допустимой точности вычислений: понятие «число» на ЭВМ на практике не тождественно понятию числа в арифметике. Число на ЭВМ представляется ячейкойпамяти, размер которой определяется архитектурой ЭВМ, и диапазон значений числа ограничивается размером этой ячейки. Например, процессоры архитектуры Intel x86 предоставляют ячейки, размер которых в байтах задается степенью двойки: 1, 2, 4, 8, 16 и т. д. Процессоры архитектуры Сетунь предоставляли ячейки, размер которых в трайтах задавался кратным тройке: 1, 3, 6, 9 и т. д.
Попытка записи в ячейку значения, превышающего максимально допустимый для нее предел (который известен) приводит к ошибке переполнения. При необходимости расчетов на более крупных числах используется специальная методика, называемая длинной арифметикой, которая в силу значительной ресурсоемкости не может осуществляться в реальном времени. Для наиболее распространенных в настоящее время архитектур ЭВМ «родным» является размер ячеек в 32 и 64 бит (то есть 4 и 8байт).
Кроме того, целые и вещественные числа имеют разное представление в этих ячейках: неотрицательные целые представляются непосредственно, отрицательные целые — в дополнительном коде, а вещественные кодируются особым образом. Из-за этих различий сложение чисел «1» и «0.1», которое в теории дает значение «1.1», на ЭВМ непосредственно невозможно. Для его осуществления необходимо сперва выполнить преобразование типа, породив на основании значения целого типа «1» новое значение вещественного типа «1.0», и лишь затем сложить «1.0» и «0.1». В силу специфики реализации вещественных чисел на ЭВМ, такое преобразование осуществляется не абсолютно точно, а с некоторой долей приближения. По той же причине сильно типизированные языки (например, Standard ML) рассматривают вещественный тип как «не допускающий проверку на равенство[en]».
Важное значение также имеет понятие о выравнивании данных.
Контрольные вопросы:
- Каковы основные характеристики структур данных?
- Какие типы данных вы знаете ?
- Какие из них относятся к стандартным, а какие к пользовательским ?
- Как представляются вещественные числа ?
- Что представляют собой данные логического типа ?
- Какие типы данных относятся к стандартным пользовательским ?
- Какому условию должны удовлетворять допустимые числа типа INTEGER ?
- Какие операции можно производить над целыми числами ?
- Перечислите булевские операции.
- Какова структура типа CHAR ?
- Какие операции возможны над данными этого типа ?
- Что можно вычислить с помощью данных указательного типа ?
- Что представляет собой перечисляемый тип данных?
- Как задается диапазонный тип ?
Вау!! 😲 Ты еще не читал? Это зря!
- Система типов
- Алгебраический тип данных, конструктор данных, конструктор типов
- Рекурсивный тип данных
- Подтип
- Функциональный тип
- Полиморфизм типов и переменная типа
- Класс типов
- структуры днных структуры данных ,
- теория типов , базовые вычислительные формализмы ,
- типы данных в javascript , типы переменных в javascript ,
- непрозрачный тип данных , odt ,
- типы данных в php ,
- тип данных — класс ,
- переменная
Напиши свое отношение про типы данных. Это меня вдохновит писать для тебя всё больше и больше интересного. Спасибо Надеюсь, что теперь ты понял что такое типы данных и для чего все это нужно, а если не понял, или есть замечания, то нестесняся пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных
Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.
Представление вещественных чисел
Вещественные числа обычно представляются в виде чисел с плавающей запятой. Числа с плавающей запятой — один из возможных способов представления действительных чисел, который является компромиссом между точностью и диапазоном принимаемых значений, его можно считать аналогом экспоненциальной записи чисел, но только в памяти компьютера.
Число с плавающей запятой состоит из набора отдельных двоичных разрядов, условно разделенных на так называемые знак (англ. sign), порядок (англ. exponent) и мантиссу (англ. mantis). В наиболее распространённом формате (стандарт IEEE 754) число с плавающей запятой представляется в виде набора битов, часть из которых кодирует собой мантиссу числа, другая часть — показатель степени, и ещё один бит используется для указания знака числа ( [math]0[/math] — если число положительное, [math]1[/math] — если число отрицательное). При этом порядок записывается как целое число в коде со сдвигом, а мантисса — в нормализованном виде, своей дробной частью в двоичной системе счисления. Вот пример такого числа из [math]16[/math] двоичных разрядов:
Знак Порядок Мантисса 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 10 9 0 Знак — один бит, указывающий знак всего числа с плавающей точкой. Порядок и мантисса — целые числа, которые вместе со знаком дают представление числа с плавающей запятой в следующем виде:
[math](-1)^S \times M \times B^E[/math] , где [math]S[/math] — знак, [math]B[/math] — основание, [math]E[/math] — порядок, а [math]M[/math] — мантисса. Десятичное число, записываемое как [math] ReE[/math] , где [math]R[/math] — число в полуинтервале [math][1; 10)[/math] , [math]E[/math] — степень, в которой стоит множитель [math]10[/math] ; в нормализированной форме модуль [math]R[/math] будет являться мантиссой, а [math]E[/math] — порядком, а [math]S[/math] будет равно [math]1[/math] тогда и только тогда, когда [math]R[/math] принимает отрицательное значение. Например, в числе [math]-2435e9[/math]
- [math]S[/math] [math]=[/math] [math]1[/math]
- [math]B[/math] [math]=[/math] [math]10[/math]
- [math]M[/math] [math]=[/math] [math]2435[/math]
- [math]E[/math] [math]=[/math] [math]9[/math]
Порядок также иногда называют экспонентой или просто показателем степени.
При этом лишь некоторые из вещественных чисел могут быть представлены в памяти компьютера точным значением, в то время как остальные числа представляются приближёнными значениями.
Более простым вариантом представления вещественных чисел является вариант с фиксированной точкой, когда целая и вещественная части хранятся отдельно. Например, на целую часть отводится всегда [math]X[/math] бит и на дробную отводится всегда [math]Y[/math] бит. Такой способ в архитектурах процессоров не присутствует. Отдаётся предпочтение числам с плавающей запятой, как компромиссу между диапазоном допустимых значений и точностью.
Содержание
Нормальная и нормализованная форма
Нормальной формой (англ. normal form) числа с плавающей запятой называется такая форма, в которой мантисса (без учёта знака) в десятичной системе находится на полуинтервале [math][0; 1)[/math] . Такая форма записи имеет недостаток: некоторые числа записываются неоднозначно (например, [math]0<,>0001[/math] можно записать в 4 формах — [math]0<,>0001 \times 10[/math] [math]0[/math] , [math]0<,>001 \times 10[/math] [math]−1[/math] , [math]0<,>01 \times 10[/math] [math]−2[/math] , [math]0<,>1 \times 10[/math] [math]−3[/math] ), поэтому распространена также другая форма записи — нормализованная (англ. normalized), в которой мантисса десятичного числа принимает значения от [math]1[/math] (включительно) до [math]10[/math] (не включительно), а мантисса двоичного числа принимает значения от [math]1[/math] (включительно) до [math]2[/math] (не включительно). То есть в мантиссе слева от запятой до применения порядка находится ровно один знак. В такой форме любое число (кроме [math]0[/math] ) записывается единственным образом. Ноль же представить таким образом невозможно, поэтому стандарт предусматривает специальную последовательность битов для задания числа [math]0[/math] (а заодно и некоторых других полезных чисел, таких как [math]-\infty[/math] и [math]+\infty[/math] ). Так как старший двоичный разряд (целая часть) мантиссы вещественного числа в нормализованном виде всегда равен « [math]1[/math] », то его можно не записывать, сэкономив таким образом один бит, что и используется в стандарте IEEE 754. В позиционных системах счисления с основанием большим, чем [math]2[/math] (в троичной, четверичной и др.), этого замечательного свойства нет (ведь целая часть там может быть не только единицей).
Типы чисел с плавающей точкой (по IEEE 754)
Число половинной точности (Binary16, Half precision)
Число́ полови́нной то́чности — компьютерный формат представления чисел, занимающий в памяти половину машинного слова (в случае 32-битного компьютера — [math]16[/math] бит или [math]2[/math] байта). В силу невысокой точности этот формат представления чисел с плавающей запятой обычно используется в видеокартах, где небольшой размер и высокая скорость работы важнее точности вычислений.
Знак Порядок Мантисса 0 0 0 0 0 0 1, 0 0 0 0 0 0 0 0 0 0 14 10 9 0 Порядок записан со сдвигом [math]-15[/math] . То есть чтобы получить актуально значение порядка нужно вычесть из него сдвиг. Сдвиг можно получить по формуле [math]2^
-1[/math] , где [math]b[/math] — число бит, отведенное на хранение порядка (в случае числа половинной точности [math]b=5[/math] ). Ограничения точности
- Целые от нуля до [math]2048[/math] передаются как есть.
- Целые от [math]2049[/math] до [math]4096[/math] округляются к ближайшему чётному целому.
- Целые от [math]4097[/math] до [math]8192[/math] округляются до ближайшего целого, делящегося нацело на четыре.
- Целые от [math]8193[/math] до [math]16384[/math] округляются до ближайшего целого, делящегося на восемь.
- Целые от [math]16385[/math] до [math]32768[/math] округляются до ближайшего целого, делящегося на шестнадцать.
- Целые от [math]32769[/math] до [math]65535[/math] округляются до ближайшего целого, делящегося на тридцать два.
Число одинарной точности (Binary32, Single precision, float)
Число́ одина́рной то́чности — компьютерный формат представления чисел, занимающий в памяти одно машинное слово (в случае 32-битного компьютера — [math]32[/math] бита или [math]4[/math] байта). Используется для работы с вещественными числами везде, где не нужна очень высокая точность.
Знак Порядок (8 бит) Мантисса (23+1 бита) 0 0 0 0 0 0 0 0 0 1, 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 23 22 0 Порядок записан со сдвигом [math]-127[/math] .
Число двойной точности (Binary64, Double precision, double)
Число́ двойно́й то́чности — компьютерный формат представления чисел, занимающий в памяти два машинных слова (в случае 32-битного компьютера — [math]64[/math] бита или [math]8[/math] байт). Часто используется благодаря своей неплохой точности, даже несмотря на двойной расход памяти и сетевого трафика относительно чисел одинарной точности.
Знак Порядок
(11 бит)Мантисса
(52+1 бит)0 0 0 0 0 0 0 0 0 0 0 0 1, 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 62 52 51 0 Порядок записан со сдвигом [math]-1023[/math] .
Число четверной точности (Binary128, Quadruple precision)
Число́ четверно́й то́чности — компьютерный формат представления чисел, занимающий в памяти четыре машинных слова (в случае 32-битного компьютера — [math]128[/math] бит или [math]16[/math] байт). Используется в случае необходимости крайне высокой точности.
Знак Порядок
(15 бит)Мантисса
(112+1 бит)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1, 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 126 112 111 Мантисса
(112+1 бит)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Порядок записан со сдвигом [math]-16383[/math] .
Обычно этот формат реализуется программно, случаи аппаратной реализации крайне редки. Также не гарантируется поддержка этого типа в языках программирования, хотя кое-где она и реализована (например, компилятор gcc для архитектуры x86 позволяет использовать тип __float128, являющийся программной реализацией числа с четверной точностью). В совокупности эти факторы делают Quadruple весьма экзотичным и редко встречающимся форматом чисел с плавающей запятой.
Диапазон значений чисел с плавающей запятой
Диапазон чисел, которые можно записать данным способом, зависит от количества бит, отведённых для представления мантиссы и показателя. Пара значений показателя (когда все разряды нули и когда все разряды единицы) зарезервирована для обеспечения возможности представления специальных чисел. К ним относятся ноль, значения NaN (Not a Number, «не число», получается как результат операций типа деления нуля на ноль) и [math]\pm\infty[/math] .
Данная таблица только лишь примерно указывает границы допустимых значений, без учета возрастающей погрешности с ростом абсолютного значения и существования денормализованных чисел.
Название в IEEE 754 Название типа переменной в Си Диапазон значений Бит в мантиссе Бит на переменную Half precision — 6,10×10 -5 ..65504 11 16 Single presicion float -3,4×10 38 ..3,4×10 38 23 32 Double precision double -1,7×10 308 ..1,7×10 308 53 64 Extended precision На некоторых архитектурах (например в сопроцессоре Intel) long double -3,4×10 4932 ..3,4×10 4932 65 80 Особые значения чисел с плавающей точкой
Ноль (со знаком)
Как уже было оговорено выше, в нормализованной форме числа с плавающей точкой невозможно представить ноль. Поэтому для его представления зарезервированы специальные значения мантиссы и порядка — число считается нулём, если все его биты, кроме знакового, равны нулю. При этом в зависимости от значения бита знака ноль может быть как положительным, так и отрицательным.
Знак Порядок Мантисса 0 /1 0 0 0 0 0 1, 0 0 0 0 0 0 0 0 0 0 = [math]\pm0[/math] 14 10 9 0 Арифметика нуля со знаком
Арифметика отрицательного нуля аналогична таковой для любого отрицательного числа и понятна интуитивно. Вот несколько примеров:- [math]\frac<-0>< \left| x \right| >= -0\,\![/math] (если [math]x\ne0[/math] )
- [math](-0) \cdot (-0) = +0\,\![/math]
- [math]\left| x \right| \cdot (-0) = -0\,\![/math]
- [math]x + (\pm 0) = x\,\![/math]
- [math](-0) + (-0) = -0\,\![/math]
- [math](+0) + (+0) = +0\,\![/math]
- [math]\frac<-0><-\infty>= +0\,\![/math]
- [math]\frac<\left|x\right|><-0>= -\infty\,\![/math] (если [math]x\ne0[/math] )
Неопределенность (NaN)
NaN — это аббревиатура от фразы «not a number«. NaN является результатом арифметических операций, если во время их выполнения произошла ошибка (примеры см. ниже). В IEEE 754 NaN представлен как число, в котором все двоичные разряды порядка — единицы, а мантисса не нулевая.
Знак Порядок Мантисса 0 /1 1 1 1 1 1 1, 0 /1 0 /1 0 /1 0 /1 0 /1 0 /1 0 /1 0 /1 0 /1 0 /1 = [math]NaN[/math] 14 10 9 0 Любая операция с NaN возвращает NaN. При желании в мантиссу можно записывать информацию, которую программа сможет интерпретировать. Стандартом это не оговорено и мантисса чаще всего игнорируется.
Как можно получить NaN?
- [math]\infty+(-\infty)= NaN[/math]
- [math]0\times\infty= NaN[/math]
- [math]\frac<\pm0><\pm0>= NaN[/math]
- [math]\frac<\pm\infty><\pm\infty>= NaN[/math]
- [math]\sqrt
= NaN[/math] , где [math]x\lt 0[/math]
Есть и другие способы получения NaN, подробности можно найти по ссылкам в соответствующем разделе.
По определению NaN ≠ NaN, поэтому, для проверки значения переменной нужно просто сравнить ее с собой.
Бесконечности
В число с плавающей запятой можно записать значение [math]+\infty[/math] или [math]-\infty[/math] . Как и нули со знаком, бесконечности позволяют получить хотя бы близкий к правильному результат вычисления в случае переполнения. Согласно стандарту IEEE 754 число с плавающей запятой считается равным бесконечности, если все двоичные разряды его порядка — единицы, а мантисса равна нулю. Знак бесконечности определяется знаковым битом числа.
Знак Порядок Мантисса 0 /1 1 1 1 1 1 1, 0 0 0 0 0 0 0 0 0 0 = [math]\pm\infty[/math] 14 10 9 0 Получить бесконечность можно при переполнении и при делении ненулевого числа на ноль. При этом [math] \frac
<0>[/math] [math]= \begin +\infty,&\text<если $x\gt 0$;>\\ NaN,&\text<если $x=0$;>\\ -\infty,&\text <если $x\lt 0$.>\end [/math] Денормализованные числа
Денормализованные числа (англ. denormalized/subnormal numbers) — это способ увеличить количество представимых числом с плавающей запятой значений около нуля, дабы повысить точность вычислений. Каждое значение денормализованного числа меньше самого маленького нормализованного («обычного») значения числа с плавающей запятой. Согласно стандарту, если порядок равен своему минимальному значению (все его биты — нули, а истинное значение порядка равно его сдвигу) и все биты мантиссы равны нулю, то это [math]\pm0[/math] . Если же мантисса не равна нулю, то это число с порядком, на единицу большим минимального (все биты порядка, кроме младшего — нули) и данной мантиссой, целая часть которой считается равной нулю, а не единице.
То есть число с плавающей запятой, при учете вышесказанного, можно задать следующим образом:
- [math](-1)^s\times1,M\times2^E[/math] , если [math]E_
\le E \le E_ [/math] (нормализованное число)
- [math](-1)^s\times0,M\times2^
-1[/math] (денормализованное число)
Где [math]s[/math] — бит знака, [math]M[/math] — последовательность битов мантиссы, [math]E[/math] — значение порядка (с учетом сдвига), [math]E_
[/math] — минимальное значение порядка, используемое для записи чисел (1 — сдвиг) , [math]E_ -1[/math] — минимальное значение порядка, которое он в принципе может принять (все биты нули, 0 — сдвиг). Хоть денормализованные числа и позволяют бороться с погрешностями и обрабатывать очень маленькие значения, за эти возможности приходится дорого платить. Ввиду сложности денормализованные числа крайне редко реализуют на аппаратном уровне — вместо этого используются программные реализации, работающие значительно медленнее.
В современных процессорах обработка денормализованных чисел происходит в десятки раз медленнее, чем обработка нормализованных чисел. Ниже приведена часть таблицы из статьи Isaac Dooley, Laxmikant Kale «Quantifying the Interference Caused by Subnormal Floating-Point Values» [1]
Производитель Процессор Замедление (разы) IBM PowerPC 970 2,4 AMD Athlon 6,0 Intel Pentium 3 15,8 AMD Athlon 64 21,4 AMD Opteron64 23,8 Intel Core Duo 44,2 Intel P4 Xeon 97,9 Intel Pentium 4 131,0 Intel Itanium 2 183,2 Sun UltraSPARC IV 520,0 В таблице приведены наихудшие результаты тестирования среди всех использованных компиляторов (gcc, icc, xlc) со всеми доступными флагами оптимизации. Исследователи утверждают, что различие среднего случая с худшим незначительно.
Поскольку в стандартных форматах (одинарной и двойной точности) денормализованные числа получаются действительно очень маленькими и практически никак не влияют на результат некоторых вычислений (при этом заметно замедляя их скорость), то иногда они просто игнорируются. При этом используются два простых механизма, получивших называние Flush-to-zero (FTZ) и Denormals-are-zero (DAZ). Первый механизм заставляет операции возвращать ноль, как только становится ясно, что результат будет денормализованным. Второй механизм заставляет операции рассматривать поступающие на вход денормализованные числа как нули.
Ярким примером подобного «отсечения» денормализованных чисел могут послужить видеокарты, в которых резкое падение скорости вычислений в сотню раз недопустимо. Так же, например, в областях, связанных с обработкой звука, нет нужды в очень маленьких числах, поскольку они представляют столь тихий звук, что его не способно воспринять человеческое ухо.В версии стандарта IEEE 754-2008 денормализованные числа (denormal или denormalized numbers) были переименованы в subnormal numbers, то есть в числа, меньшие «нормальных». Поэтому их иногда еще называют «субнормальными«.
Действия с числами с плавающей запятой
Умножение и деление
Самыми простыми для восприятия арифметическими операциями над числами с плавающей запятой являются умножение и деление. Для того, чтобы умножить два вещественных числа в нормализованной форме необходимо перемножить их мантиссы, сложить порядки, округлить и нормализовать полученное число.
Соответственно, чтобы произвести деление нужно разделить мантиссу делимого на мантиссу делителя и вычесть из порядка делимого порядок делителя. Затем точно так же округлить мантиссу результата и привести его к нормализованной форме.
Сложение и вычитание
Идея метода сложения и вычитания чисел с плавающей точкой заключается в приведении их к одному порядку. Сначала выбирается оптимальный порядок, затем мантиссы обоих чисел представляются в соответствии с новым порядком, затем над ними производится сложение/вычитание, мантисса результата округляется и, если нужно, результат приводится к нормализированной форме. Пример:
Алгоритм получения представления вещественного числа в памяти ЭВМ
Покажем преобразование действительного числа для представления его в памяти ЭВМ на примере величины типа Double.
Как видно из таблицы, величина этого типа занимает в памяти [math]8[/math] байт. На рисунке ниже показано, как здесь представлены поля мантиссы и порядка (нумерация битов осуществляется справа налево):
Знак Смещённый порядок Мантисса 63 62..52 51..0 Можно заметить, что старший бит, отведенный под мантиссу, имеет номер [math]51[/math] , т.е. мантисса занимает младшие [math]52[/math] бита. Черта указывает здесь на положение двоичной запятой. Перед запятой должен стоять бит целой части мантиссы, но поскольку она всегда равна [math]1[/math] , здесь данный бит не требуется и соответствующий разряд отсутствует в памяти (но он подразумевается). Значение порядка хранится здесь не как целое число, представленное в дополнительном коде. Для упрощения вычислений и сравнения действительных чисел значение порядка в ЭВМ хранится в виде смещенного числа, т.е. к настоящему значению порядка перед записью его в память прибавляется смещение. Смещение выбирается так, чтобы минимальному значению порядка соответствовал нуль. Например, для типа Double порядок занимает [math]11[/math] бит и имеет диапазон от [math]2[/math] [math]-1023[/math] до [math]2[/math] [math]1023[/math] , поэтому смещение равно [math]1023[/math] ( [math]10[/math] ) [math]=[/math] [math]1111111111[/math] ( [math]2[/math] ). Наконец, бит с номером [math]63[/math] указывает на знак числа.
Таким образом, из вышесказанного вытекает следующий алгоритм для получения представления действительного числа в памяти ЭВМ:
- перевести модуль данного числа в двоичную систему счисления;
- нормализовать двоичное число, т.е. записать в виде M [math] \times [/math] 2 p , где M — мантисса (ее целая часть равна [math]1[/math] ( [math]2[/math] )) и p — порядок, записанный в десятичной системе счисления;
- прибавить к порядку смещение и перевести смещенный порядок в двоичную систему счисления;
- учитывая знак заданного числа (0 — положительное; 1 — отрицательное), выписать его представление в памяти ЭВМ.
Пример. Запишем код числа [math]-312[/math] , [math]3125[/math] .
- Двоичная запись модуля этого числа имеет вид [math]100111000<,>0101[/math] .
- Имеем [math]100111000<,>0101[/math] [math]=[/math] [math]1<,>001110000101[/math] [math]\times[/math] [math]2[/math] [math]8[/math] .
- Получаем смещенный порядок [math]8[/math] [math]+[/math] [math]1023[/math] [math]=[/math] [math]1031[/math] . Далее имеем [math]1031[/math] ( [math]10[/math] ) [math]=[/math] [math]10000000111[/math] ( [math]2[/math] ).
- Окончательно
1 10000000111 0011100001010000000000000000000000000000000000000000 63 62..52 51..0
Очевидно, что более компактно полученный код стоит записать следующим образом: C073850000000000(16).
Другой пример иллюстрирует обратный переход от кода действительного числа к самому числу.
#3 — Типы данных
Этот видеоурок мы посвятим типам данных в языках программирования, которые будут рассмотрены на примерах языков python и javascript.
Виды типов данных
Данные в языках программирования бывают разные.
Язык программирования python имеет типы данных:
В языке javascript используются следующие типы данных:
Рассмотрим некоторые из них.
Тип данных — «строка»
В javascript строкой — string — называют фрагмент текста (последовательность символов). Строка может состоять из букв, чисел, знаков(например, точки и запятые) или пробелов, то есть из символов. Обычно их записывают в одинарных кавычках (но в js можно и в двойных), начинаться и заканчиваться строка должна кавычками одного вида.
Строки можно склеивать вместе или вырезать из них выбранные части. Подобно тому как сложение двух чисел дает новое число, можно сложить две строки. Получится строка, состоящая из исходных строк, склеенных вместе. У каждого символа в строке есть номер, который соответствует его позиции. Этот номер можно использовать, чтобы узнать отдельный символ или чтобы вырезать его из строки. Отсчет ведется с нуля.
В некоторых языках программирования есть специальный тип данных для одного символа. Например, в языке С это «char».
Тип данных — «число»
Единый тип «число» используется как для целых, так и для дробных чисел.
В языках программирования есть следующие типы числовых данных:
Целые числа хороши для подсчета чего-либо, а вещественные — для измерения таких свойств, как вес.
Булевый (логический) тип данных — boolean.
Истина или ложь? Компьютеры принимают решения о том, что делать дальше, задавая вопросы и анализируя ответы — «да» или «нет». Вопросы, на которые есть лишь два варианта ответа, называют булевыми (логическими) выражениями.
Булевый тип может принимать одно из двух значений — true (истина) или false (ложь). Программы принимают решения о том, что делать дальше, сравнивая переменные, числа и строки с помощью булевых выражений — тех, что возвращают либо true, либо false.
Бывают также такие типы данных, как null, undefined, object (объект) — в javascript или list (список), tuple (кортеж), dict (словарь) — в python. Но для понимания общих основ программирования вам будет достаточно знания трех типов данных: «число», «строка» и булево значение.
Преобразование типов данных
Не все типы данных в программе совместимы. Порой один тип нужно преобразовать в другой, иначе возникнет ошибка.
В javascript оператор typeof возвращает тип аргумента. В python, чтобы узнать тип, применяют команду type.