Презентация Простые типы данных языка С. Лекция 3 онлайн

Содержание слайда: Простые типы данных языка С лекция 3

Содержание слайда: План лекции Простые типы данных Ограничения на простые типы данных Машинное представление простых типов данных Системы счисления (представление целых чисел чисел)

Содержание слайда: Простые типы данных Тип данных – это пара, состоящая из множества значений и набора операций над ними Языки программирования позволяют строить одни типы данных из других типов данных Простые типы данных – это типы данных, которые нельзя построить из других типов данных Составные типы данных – это типы данных, которые строятся из других типов данных

Содержание слайда: Простые типы данных Си Символы, 8-битовые целые Целые Числа с плавающей точкой Перечислимые типы

Содержание слайда: Простые типы данных -- символы С89 спецификатор-символьного-типа ::= [signed|unsigned] char Символы и 8-битовые целые со знаком (signed) или без знака (unsigned) CHAR_MIN, CHAR_MAX, UCHAR_MAX и др. в limits.h Стандарт не определяет, есть ли знак у значений типа char

Содержание слайда: Простые типы данных -- целые С89 спецификатор-целого-типа ::= [signed|unsigned] [short|long] int С99, С11 (поддержка есть в gcc 4.6) спецификатор-целого-типа ::= [signed|unsigned] [short|long [long]] int С89/C99/C11 не определяют, есть ли знак у int Все известные компиляторы считают int = singed int Нестандартные целые типы __int16, __int32, __int64, __int128 Наличие и смысл зависят от компилятора

Содержание слайда: Простые типы данных -- целые

Содержание слайда: Простые типы данных – числа с плавающей точкой С89/С99/С11 спецификатор-типа-с-плавающей ::= float | [long] double sizeof(float) <= sizeof(double) <= sizeof(long double) FLT_MIN, FLT_MAX, DBL_MIN, DBL_MAX, LDBL_MIN, LDBL_MAX и др. в файле float.h

Содержание слайда: Простые типы данных – перечислимые типы С89/С99/С11 enum-спецификатор ::= 'enum' [имя] '{' список-перечислителей '}' | 'enum' [имя] '{' список-перечислителей ',' '}' | 'enum' имя список-перечислителей ::= перечислитель | список-перечислителей ',' перечислитель перечислитель ::= перечислимая-константа | перечислимая-константа '=' константное-выражение перечислимая-константа ::= имя константное-выражение на след. лекции Тип, диапазон значений и размер в памяти такие же, как у int

Содержание слайда: Простые типы данных – перечислимые типы Примеры enum my_boolean_t { my_false = 0, my_true = 1 } enum my_boolean_t { my_false, my_true } my_false = 0 my_true = my_false+1 = 1 enum my_boolean_t { my_false = 0, my_true = 0 } my_false = my_true = 0 enum my_day_t { mon, tue, wed, thu, fri, sat, sun }

Содержание слайда: Машинное представление данных простых типов Символы, 8-битовые целые Целые Числа с плавающей точкой

Содержание слайда: Машинное представление значений типа char, signed char, unsigned char 1 байт памяти, signed char целые числа от -128 до 127 unsigned char целые числа от 0 до 255 Программы на Си используют значения типов char, signed char, unsigned char для печати текстовых сообщений на экране, бумаге и т.п. Соответствие значений и символов определяется кодировкой ОС

Содержание слайда: Машинное представление значений типа char, signed char, unsigned char Кодировка CP866 (MS DOS)

Содержание слайда: Машинное представление значений типа char, signed char, unsigned char Linux (КОИ8) Win 1251 Mac OS

Содержание слайда: Машинное представление беззнаковых (unsigned) целых Двоичная запись числа Ч -- набор bn … b1 b0 такой, что Ч = b0∙20 + b1 ∙ 21 + … + bn ∙ 2n М.П. unsigned числа x – это двоичная запись числа x mod 28∙sizeof(T)

Содержание слайда: Машинное представление целых со знаком (signed) М.П. signed числа x двоичная запись x mod 28∙sizeof(T), если x >= 0 дополнительный код |x| -- двоичная запись 28∙sizeof(T) - |x| mod 28∙sizeof(T), если x < 0 Свойство дополнительного кода М.П.(х) + М.П.(-х) = М.П.(0)

Содержание слайда: Машинное представление целых со знаком (signed) Построение дополнительного кода |x| b[n] – двоичная запись |x| d[n] – дополнительный код |x| Алгоритм for (i = 0; i < n; i = i+1) d[i] = 1-b[i]; for (i = 0; i < n && d[i] == 1; i = i+1) d[i] = 0; if (i < n) d[i] = 1;

Содержание слайда: Машинное представление чисел с плавающей точкой Числа вида S ∙ M ∙ 2P S – знак +1 или -1, 1 бит M – мантисса, x/2mb от 0 до 1 mb – число битов в мантиссе Intel, AMD, ARM -- 23 для float, 52 для double x – целое от 0 до 2mb-1 P – порядок Intel, AMD, ARM – 8 битов для float, 11 битов для double float занимает 1+8+23 = 32 бита double занимает 1+11+52 = 64 бита long double обычно совпадает с double или эмулируется

Содержание слайда: Машинное представление значений типа double – стандарт IEEE 754

Содержание слайда: Машинное представление значений типа float – стандарт IEEE 754

Содержание слайда: Машинное представление данных простых типов -- разное Адрес значения переменной простого типа B выровнен (кратен) sizeof(B)

Содержание слайда: Системы счисления

Содержание слайда: Значение и обозначение числа 9, IX, девять, nine, 1001(2) Значение числа Числовая величина, «чистая» Отвлеченная от измеряемых объектов и единиц измерения Обозначение (форма, внешнее представление) числа Название или знак в некотором языке или системе обозначений, позволяющих отличать данное число от других Значение числа не зависит от обозначения

Содержание слайда: Система счисления (с.с.) Cистема правил для построения названий чисел некоторым регулярным способом Непозиционные системы счисления возникли первыми Основаны на простом суммировании «весов» – цифр - «разновесов», занятых в записи числа. Римская с.с. Цифры берутся с плюсом или минусом в зависимости от веса соседа слева – IX = 9, XI = 11 Позиционные системы счисления Вклад каждой цифры зависит от «веса» ее позиции в записи числа

Содержание слайда: Представление целых чисел в позиционных системах счисления с произвольным основанием Позиционная система счисления, использующая b цифр, называется b-ичной системой счисления (с.с.) Если b  10, то первые b цифр из 0, 1, ..., 9 Если 10  b  36, то первые b знаков из 0, 1, ..., 9, A, B, …, Z 10 – A, 11 – B, и т.д.

Содержание слайда: Запись целого числа S = 0  ai < b, i – индекс позиции (разряда), в которой расположена цифра ai Запись числа называется k-значной, если индекс разряда первой значащей цифры числа равен k – 1 Примеры 10011001(2), 248933, 7DAB(16) 123454(5) - неправильная запись

Содержание слайда: Соотношение записи целого числа со значением

Содержание слайда: Соотношение записи целого числа со значением – схема Горнера

Содержание слайда: Примеры N(10011(2))= 124+023+022+121+120 =19 N(10011(2))=(((12+0)2+0)2+1)2+1=19 N(30A(16)) = 3162+0161+10160 = 778 N(30A(16)) =(316+0)16+10 = 778

Содержание слайда: Теорема 1 Любое число однозначно представимо в виде цифр заданной b-с. с. Доказательство -- упражнение

Содержание слайда: Алгоритм перевода b-ичной записи значение Вход: b > 0, k > 0 (число цифр), набор ak-1, ak-2, … , a1, a0. цикл по i = 1 до k – 1 конец цикла; Выход: N (2k - 2) операций * (k-1) операций +

Содержание слайда: Схема Горнера Вход: b > 0, k > 0 (число цифр), набор цикл по i от k - 2 вниз до 0 N = N  b + ai ; конец цикла; Выход: N k-1 операция * k-1 операция +

Содержание слайда: Построение записи в b-ичной с.с. Вход: N ≥ 0, b > 0; i = 0; цикл ai = N mod b; (mod – остаток от деления нацело) N = N div b; (div – целое деление) i = i + 1; пока N ≠ 0; Выход: набор ai, i ( число значащих цифр) число операций деления = i

Содержание слайда: Пример – построение 2-ной записи 325 Целая часть | Остаток от деления на 2 325(10) = 101000101(2)

Содержание слайда: Перевод числа из b1-с.с. в b2-с.с.

Содержание слайда: Представление действительных чисел Если в дробной части числа конечное число знаков k, то нижний индекс суммы равен — k . 0.375=(3+(7+5/10)/10)/10=(3+(7+(5+0)/10)/10)/10

Содержание слайда: Связь дробной части числа со значением

Содержание слайда: Примеры N(«1.101(2)») = 120 +12-1 +02-2 +12-3 = 1 + 0.5 + 0.125 = 1.625 Nf(«0.101(2)») =(1 +(0 +(1 +0)/2)/2)/2 = (1 + (0 + 0.5)/2 )/2 = (1 + 0.25) / 2 = 0.625 Nf(«0.01(3)») = 13-2 = = 0.(1)

Содержание слайда: Окончание лекции

Содержание слайда: Алгоритм (построения) записи дробной части в b-с.с Вход -- Nf ( 0 ≤ Nf < 1), b >1 i = -1; цикл a[i] = ц.ч.(Nf*b); // первая цифра дробной // части числа Nf Nf = Nf*b-a[i]; i = i – 1; пока Nf != 0 Выход -- набор i < 0, a[i+], a[i+2], …, a[-1] Когда алгоритм не завершится?

Содержание слайда: Пример построения 2-ичной записи дробного числа

Содержание слайда: Конечная представимость рациональных чисел Несократимая дробь p/q конечно представима в b-ной с. с. тогда и только тогда, когда все простые делители q делят b 121/675 конечна в 15-с.с., т.к. 675 = 33*52 и 15 = 3*5 1/675 = 5*15-3 = 0.005(15); 121*5*15-3 = (2*152 + 10*151 + 5)*15-3 = 2*15-1 + 0*15-2 + 5*15-3 121/675 = 0.2A5(15); Запись 1/10 бесконечна в 2-с.с.

Содержание слайда: Вычисление значения по b-ичной записи Вход: b > 1, к > 0 (число дробных цифр), набор a[-k], a[-k+1],…, a[-1] Nf = 0; S = 1/b; // S накапливает степень цикл по i от -1 вниз до –k Nf = Nf+a[i]*S; S = S/b; конец цикла Выход: Nf 2k операций *, / k операций +

Содержание слайда: Вычисление значения по b-ичной записи по схеме Горнера Вход: b > 1, k > 0 (число цифр), набор a[-k], a[-k+1], … a[-1] Nf = 0; цикл по i от -k до -1 Nf = (a[i]+Nf)/b; конец цикла Выход: Nf k операций + и /

Содержание слайда: Кратные системы счисления Если основания двух систем счисления b1 и b2 связаны соотношением b2= b1m для некоторого натурального m, то такие системы счисления называются кратными Упражнение – сформулируйте алгоритм перевода для кратных с.с.

Содержание слайда: Объявление и инициализация переменных простых типов Для РБНФ <Х> обозначим <Х>* РБНФ <список Х>, заданную правилом <список Х> ::= <X> | <список Х> <X>

Содержание слайда: Объявление и инициализация переменных простых типов <единица-трансляции> ::= <внешнее-объявление>* <внешнее-объявление> ::= <определение-функции> | <объявление> <определение-функции> ::= [<спецификаторы-объявления>] <объявитель> [<список-объявлений>] <составная-инструкция> <объявление> ::= <простое-объявление> | <составное-объявление>

Содержание слайда: Объявление и инициализация переменных простых типов <инструкция>::= | <помеченная-инструкция> | <инструкция-выражение> | <составная-инструкция> | <инструкция-выбора> | <циклическая-инструкция> | <инструкция-перехода> <инструкция-выражение>::= [<выражение>] ';' <составная-инструкция>::= '{' [<объявление>*] [<инструкция>*] '}'

Содержание слайда: Объявление и инициализация переменных простых типов <простое-объявление> ::= <спецификаторы-объявления> [<простой-объявитель-инициализатор>*] C89: Объявления переменных встречаются либо вне самого внешнего блока { }, либо сразу же после { C99: Объявления переменных встречаются в любом месте кода

Содержание слайда: Объявление и инициализация переменных простых типов <простой-объявитель-инициализатор> ::= <простой-объявитель> | <простой-объявитель> '=' <инициализатор> <простой-объявитель> ::= <идентификатор> <инициализатор> ::= <выражение-присваивания>

Содержание слайда: Объявление и инициализация переменных простых типов <спецификаторы-объявления> ::= ( <спецификатор-класса-памяти> | <спецификатор-простого-типа> | <квалификатор-типа> )*

Содержание слайда: Объявление и инициализация переменных простых типов <спецификатор-класса-памяти> ::= | 'auto' | 'register' | 'static' | 'extern' | 'typedef' auto На стеке (по умолчанию) register В регистре static В статической памяти единицы компиляции extern В статической памяти программы typedef Вне памяти, объявляемый идентификатор далее обозначает тип

Содержание слайда: Объявление и инициализация переменных простых типов <спецификатор-простого-типа> ::= 'void' | 'char' | 'short' | 'int' | 'long' | 'float' | 'double' | 'signed' | 'unsigned' | <спецификатор-enum> -- было | <typedef-имя> <typedef-имя> ::= <идентификатор> <квалификатор-типа> ::= 'const' | 'volatile' const Неизменяемое значение volatile Значение может асинхронно изменяться – например, в многопоточной программе

Содержание слайда: Примеры объявлений переменных простых типов int x; auto int x; // то же, что выше const int x; // как задать начальное // значение?! const double x = 1.234567; float x = 0, y = x+1; static int x = 5; extern unsigned long long global_uuid;

Содержание слайда: Примеры объявлений переменных простых типов typedef int my_int; // my_int – синоним int my_int x = 0, y = x+1;

Содержание слайда: Заключение Простые типы данных Ограничения на простые типы данных Машинное представление простых типов данных Системы счисления Представление целых и вещественных чисел Объявление и инициализация переменных простых типов

Содержание слайда:

Содержание слайда: Пример Перевести 101.101(2) в 10-с.с. 1) умножим на 23  101101(2) 2) переведем в 10-с.с.  45 3) разделим: 45/8 = 5.625(10) 101.101=1*22+1*20+1*2-1+1*23 =5+1/2+1/8=5.625

Содержание слайда: Кратные системы счисления Если основания двух систем счисления b1 и b2 связаны соотношением b2= b1m для некоторого натурального т, то такие системы счисления называются кратными. Перевод числа из одной с. с. в другую для таких систем можно выполнить проще. Сгруппируем цифры в b1-записи числа по m от точки влево и вправо (добавив при нехватке цифр нужное количество незначащих нулей):

Содержание слайда:

Содержание слайда: Таблицы соответствия последовательностей цифр кратных с.с.

Содержание слайда: Алгоритм А8: перевод из меньшей кратной с.с. в большую Вход: b1 > 1, b2 = b1m, b1 - представление числа; • разбить число на группы по т цифр, начиная от точки, в обе стороны (если в крайних группах цифр меньше т, добавить незначащие нули: в целой части спереди, в дробной сзади); • заменить каждую группу b2-цифрой по формуле (8) или таблице. Выход: b2 -представление исходного числа.

Содержание слайда: Алгоритм А9: перевод из большей кратной с.с. в меньшую Вход: b1> 1, b2= b1m; b2-представление числа; заменить каждую b2-цифру цепочкой из т b1-цифр по формуле (8) или таблице; отбросить незначащие нули слева и справа. Выход: b1-представление исходного числа.

Содержание слайда: Универсальные алгоритмы для арифметических операций Все так называемые численные алгоритмы для арифметических операций сложения, вычитания, умножения и деления (в том числе, вычисления «столбиком») являются символьными, потому что оперируют входными, выходными и промежуточными данными как строками символов. Символьные вычисления являются формальными в том смысле, что манипулируют только знаками, не обращаясь к их значениям. Абстрагирование от смысла данных различной природы и описание алгоритма в терминах чисто символьных преобразований является одним из основных методов программирования обработки данных произвольной природы.

Содержание слайда: Алгоритм А10: сложение двух чисел Вход: две строки цифр, представляющие слагаемые; • выравнивание: расположить слагаемые одно под другим в произвольном порядке так, чтобы разряды с одинаковым весом находились друг под другом; если какое-то число короче других слева или справа, дополнить его нулями; • начальные установки: обнулить цифру переноса в следующий разряд; установить результат равным пустой строке; • цикл по текущему разряду от младшего до старшего: определить сумму переноса и цифр в столбце текущего разряда чисел; младшую цифру суммы записать в текущий разряд результата, старшую — в перенос; конец цикла; • окончание: если перенос не равен 0, то дописать перенос в начало результата Выход: строка, представляющая результат.

Содержание слайда:

Содержание слайда:

Содержание слайда: Особенности умножения и деления на основание системы счисления В b-с. с. число b всегда имеет представление «10(b)». Умножение на b сводится к дописыванию справа к целому числу или (что то же), сдвигом b-ичной точки на один разряд влево. Деление на b равносильно сдвигу точки на один разряд вправо или отбрасыванию младшей цифры целого числа — при делении нацело. Аналогично число b всегда представляется единицей с k нулями, а умножение (деление) на b сводится к сдвигу точки на k позиций вправо (влево). Остатком от деления целого числа нацело на b является число, составленное из k младших цифр. Добавление k нулей справа и отбрасывание k младших цифр можно рассматривать как две новые операции арифметического сдвига на k позиций.

Содержание слайда: Арифметические сдвиги Добавление k нулей справа и отбрасывание k младших цифр можно рассматривать как операции арифметического сдвига на k позиций. В Си определены операции арифметического сдвига на k позиций, которые равносильны умножению или целочисленному делению на 2k. << — сдвиг влево >> — сдвиг вправо Примеры: a = 5 << 3; /* после выполнения присваивания a будет иметь значение 40 */ b = 112 >> 4; /* b будет равно 7 */

Содержание слайда: Особенности двоичной арифметики

Содержание слайда: Сложность арифметических алгоритмов Затраты памяти на хранение чисел и времени на выполнение операций с ними зависят от длины записи числа в цифрах рабочей системы счисления. Для заданной b-с. с. следующие величины: kn — длина записи (натурального) числа N, Nk — максимальное натуральное число, записываемое k цифрами, связаны соотношениями: kn = [logbN] + 1, где [x] — наибольшее целое, не превышающее x; Nk = bk − 1. Верхние оценки для размера результата арифметической операции над парой целых чисел N1 и N2 (пусть N1 > N2): для сложения и вычитания — kN1 +1, для умножения — kN1 + kN2, для деления — kN1 +1, (так как N2 > 1).

Содержание слайда: Время исполнения Алгоритмы сложения содержат один проход по всем разрядам числа, причем каждый разряд обрабатывается не более одного раза. Поэтому время работы алгоритма сложения линейно по k: Тслож(k)~k. Алгоритмы умножения и деления выполняют сложение и вычитание несколько раз (не более, чем k), со сдвигом на одну позицию. Так как время сложения линейно, время умножения и деления квадратично по k: Tyмн ~k2,, Tдел (k) ~ k2. В системах команд компьютеров есть команды типа сложения и умножения, которые работают не с отдельными битами, а с байтами; они обычно рассматриваются как элементарные. Проведенные выше оценки сохраняют свою силу, если заменить базовую с. с. кратной ей (со степенью кратности равной длине слова).

Содержание слайда: Упражнения 1. Выразить целую часть 17.5 * X через сложение и операции поразрядных сдвигов числа X вправо и влево. 17.5(10) = 16 + 1 + 0.5 = 24 + 20 + 2–1 = 10001.1(2) 17.5 *X = X* (24 + 20 + 2–1 ) = = X*24 + X*20 + X*2–1 = = (X << 4) + X + (X >> 1) 2. Если 120(x) делится на 11(10), то как выглядит (чему равно?) 310 в системе счисления с основанием x? Подбором можно определить, что x = 9, т.к. 120(9) = 99(10) – делится на 11 без остатка. 310 = 32*5= (32)5 = 95 = 100000(9)

Содержание слайда: Объявление и инициализация переменных простых типов <объявитель> ::= [<указатель>] <собственно-объявитель> <указатель> ::= ( '*' [<квалификаторов-типа>*] )* <собственно-объявитель> ::= <идентификатор> | '(' <объявитель> ')' | <собственно-объявитель> '[' [<константное-выражение>] ']' | <собственно-объявитель> '(' <список-типов-параметров> ')' | <собственно-объявитель> '(' [<список-идентификаторов>] ')' <список-типов-параметров>::= <список-параметров> | <список-параметров> ',' '...' список-параметров::= <объявление-параметра>* объявление-параметра::= спецификаторы-объявления объявитель спецификаторы-объявления абстрактный-объявительнеоб инициализатор: выражение-присваивания { список-инициализаторов } { список-инициализаторов , } имя-типа: список-спецификаторов-квалификаторов абстрактный-объявительнеоб абстрактный-объявитель: указатель указательнеоб собственно-абстрактный-объявитель собственно-абстрактный-объявитель: ( абстрактный-объявитель ) собственно-абстрактный-обьявительнеоб [ константное-выражениенеоб ] собственно-аострактныи-объявительнеоб ( список-типов-параметровнеоб ) typedef-имя: идентификатор