Турбо Паскаля
Турбо Паскаль является достаточно эффективным языком для программирования вычислительных задач. В нем реализован необходимый набор математических функций, позволяющий на их основе достраивать библиотеку научных подпрограмм. В этой главе мы рассмотрим математические средства Турбо Паскаля. Максимальную скорость вычислений с высокой точностью можно достичь при использовании математического сопроцессора. Ряд аспектов его применения также будет рассмотрен в этой главе.
Базовые операции
Математические выражения в алгоритмической записи состоят из операций и операндов. Большинство операций в языке Турбо Паскаль являются бинарными, т.е. содержат два операнда. Некоторые операции являются унарными и содержат только один операнд. В бинарных операциях используется обычное двухместное алгебраическое представление. В унарных операциях операция всегда предшествует операнду, например: -b.
В сложных выражениях порядок, в котором выполняются операции, соответствует приоритету операций (табл. 9.1).
Таблица 9.1
| Название | Тип операндов | Тип результата | Вид | |
| Первый (высший) приоритет | ||||
| @ | Взятие адреса | Любой | Pointer | Унарные операции |
| - + not not | Унарный минус Унарный плюс Логическое 'НЕ' Поразрядное 'НЕ' | Целый Вещественный Целый Вещественный Логический Целый | Целый Вещественный Целый Вещественный {161} Логический Целый | |
| Второй приоритет | ||||
| * | Операция умножения | Целый*Целый Целый*Вещественный Вещественный*Целый Вещественный*Вещественный | Целый Вещественный Вещественный Вещественный | Бинарные операции |
| / | Операция деления | Целый/Целый Целый/Вещественный Вещественный/Целый Вещественный/Вещественный | Вещественный Вещественный Вещественный Вещественный | |
| div | Целочисленное деление | Целый div Целый | Целый | |
| mod | Остаток от деления нацело | Целый mod Целый | ||
| and and | Логическое 'И' Поразрядное 'И' | Логический Целый | Логический Целый | |
| shl shr | Циклический сдвиг влево Циклический сдвиг вправо | Целый Целый | Целый Целый | |
| Третий приоритет | ||||
| + | Операция сложения | Целый+Целый Целый+Вещественный Вещественный+Целый Вещественный+Вещественный | Целый Вещественный Вещественный Вещественный | Бинарные операции {162} |
| – | Операция вычитания | Целый–Целый Целый–Вещественный Вещественный-Целый Вещественный– Вещественный | Целый Вещественный Вещественный Вещественный | |
| or or | Логическое 'ИЛИ' Поразрядное 'ИЛИ' | Логический Целый | Логический Целый | |
| xor xor | Логическое исключающее 'ИЛИ' Поразрядное исключающее 'ИЛИ' | Логический Целый | Логический Целый | |
| Четвертый (низший) приоритет | ||||
| = <> < > <= >= | Операции отношения | Число и число Строка и число Строка и литера Pointer и Pointer Множества | Логический | Бинарные операции |
| in | Вхождение в множество | Элементарный и множество | Логический |
Примечания:
1. Под вещественными понимаются тип Real и вещественные типы, поддерживаемые математическим сопроцессором (типы с повышенной точностью).
2. Под целыми понимаются целочисленные типы языка.
3. В таблице указан оператор @, не имеющий никакого отношения к математике. Он включен только для показа его приоритета.
При вычислениях сначала применяются операции наивысшего порядка, затем более низкого. Операции равного приоритета вычисляются слева направо:
2*3/4/5 = ((2 * 3)/4)/5
Применение скобок позволяет явно расставлять приоритеты и менять порядок вычислений.
Значение выражения X/Y всегда будет вещественного типа, независимо от типов операндов. Если Y равно 0, то произойдет фатальная ошибка (номер 200) и останов программы. {163}
Значение выражение i div j представляет собой математическое частное i/j, округленное в меньшую сторону до значения целого типа. Если j равно 0, то результатом будет фатальная ошибка.
Операция деления по модулю mod возвращает остаток, полученный путем деления двух ее операндов, т.е.
i mod j = i - (i div j) * j
Знак результата операции mod будет тем же, что и знак i. Если j равно нулю, то результатом будет фатальная ошибка.
Битовая арифметика
Кроме стандартных для всех языков математических действий над вещественными и целыми числами, Турбо Паскаль вводит дополнительные операции над целыми числами, в том числе и так называемую битовую, или поразрядную, арифметику.
Битовая арифметика хорошо развита в языке Турбо Паскаль. Необходимость в ее применении возникает, когда надо работать не с десятичными значениями чисел, а с их двоичным представлением. В этом случае можно сравнивать отдельные биты двух чисел, выделять двоичные фрагменты, заменять их и т.п. Это часто используется при работе с видеопамятью в текстовом или графическом режимах. Кроме того, есть ряд чисто математических задач, которые удобно решать в двоичном представлении.
Ограничение на битовые операции одно: они должны применяться только над целыми типами — Byte, ShortInt, Word, Integer, LongInt и совместимыми с ними. Именно эти типы кодируют значения в правильные двоичные числа, как в школьном учебнике по информатике. (То, что в памяти некоторые целые типы хранят свои байты значений в обратном порядке, никак не влияет на поразрядные действия и логику работы с ними. Все особенности учитываются самими поразрядными операциями, и мы можем о них даже не вспоминать.) Например, значения 4 и 250 типа Byte представляются как двоичные наборы 00000100 и 11111010, число 65535 типа Word — это уже 16 бит: 11111111 11111111 и т.д.
Общая формула для значений типов Byte и Word имеет вид
Byte: Значение = B7*27 + B6*2б + B5*25 +...+ B1*2* + B0;
Word: Значение = B15*215 + B14*214+...+B7*27 +...+ B0.
Множители B0, B1 и т.п. — это значения соответствующих битов, равные либо 0, либо 1, а числовые множители — это 2 в степени номера бита. {164}
Внутреннее отличие имеют представления целых типов со знаком: ShortInt, Integer и LongInt. По размеру тип ShortInt равен типу Byte, a Integer — типу Word. Но они могут хранить отрицательные целые числа, правда, меньшие по абсолютному значению чем 255 и 65535:
ShortInt: -128..127 (8 бит),
Integer: -32768.. 32767 (16 бит),
LongInt: -2147483648.. 2147483647 (32 бит).
Самый левый бит в представлении отрицательного числа всегда равен 1, если значение отрицательное, и 0 в противном случае. Формула перевода битов в значение для типов ShortInt, Integer, LongInt такова:
Shortlnt: Знач= -B7*27 + B6*26 + B5*25 +...+ B1*21 + B0;
Integer: Знач=-B15*215 + B14*214+...+B7*27 +...+ B0;
LongInt: Знач=-B31*231 + B30*230+...+B15*215 +...+ B0;
Примеры кодировки отрицательных чисел для типа ShortInt (бит знака числа отделен здесь пробелом):
-1:1 1111111 (-1*128 + 127)
-2: 1 1111110 (-1*128 + 126)
-3: 1 1111101 (-1*128 + 125)
-125: 1 0000011 (-1*128 + 3)
-128: 1 0000000 (-1*128 + 0)
Если в кодировании положительных значений абсолютное значение числа тем больше, чем больше единиц в его записи, то для отрицательных значений нули и единицы как бы поменяются местами — и абсолютное значение числа тем больше, чем больше будет в записи нулей. Поэтому, например, двоичное представление того же числа -128 в формате Integer (это уже 16 бит) будет 11111111 10000000.
Вещественные типы кодируются каждый раз по-разному, но всегда достаточно сложно: одна группа битов составляет мантиссу числа, вторая — порядок, да еще знак... Битовые операции к вещественным числам (типам) не применяются.
Посмотреть двоичную форму представления целых чисел можно с помощью функции (рис. 9.1). Операции shl и shr из примера на рис. 9.1 будут рассмотрены чуть позже. {165}
| {ФУНКЦИЯ ПЕРЕВОДА ЦЕЛОГО ЧИСЛА В ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ} { X - целое число (можно передавать и другие типы) } { NumOfBits - число позиций в двоичном представлении } FUNCTION Binary(X:LongInt; NumOfBits: Byte): String; VAR bit, i: Byte; { вспомогательные переменные } s: String[32]; BEGIN s: = ' '; { обязательная чистка строки } for i:=0 to 31 do begin { цикл перевода } bit:= (X shl i) shr (31); { выделение бита } s:= s + Chr(Ord('0') + bit) { запись в строку } end; {for} { конец цикла } Delete(s, 1, 32-NumOfBits); { отсечение лишних битов} Binary:- s { возвращаемая строка } END; VAR i: Integer; {=== ПРИМЕР ВЫЗОВА === } BEGIN for i:=-5 to 5 do WriteLn(i:7, '--> ', Binary(i, 8*SizeOf(i))); Readln { пауза до нажатия клавиши ввода } END. |
Рис. 9.1
Итак, какие же действия предоставляет поразрядная арифметика? Первая группа — это логические операции над битами (табл. 9.2).
Таблица 9.2
| Операции | Название | Форма записи | Приоритет |
| not | Поразрядное отрицание | not A | 1 (высший) |
| and | Логическое умножение | A1 and A2 | |
| or | Логическое сложение | A1 or A2 | |
| xor | Исключающее 'ИЛИ' | A1 xor A2 | 4 (низший) |
Not — поразрядное отрицание — «переворачивает» значение каждого бита на противоположное. Так, если A в двоичном виде представляется как 01101100, то not A станет 10010011:
not [1] = 0
not [0] = 1
Квадратные скобки вокруг аргументов обозначают действие над одним битом. {166}
And — так называемое логическое умножение или поразрядная операция 'И':
[0] and [1] = [1] and [0] = [0]
[0] and [0] = [0]
[1] and [1] = [1]
Здесь аргументы специально взяты в скобки — их надо рассматривать как отдельные единичные биты; реальные же примеры не столь очевидны:
(6 and 4) = 4
(6 and 1) = 0
и т.п. Все станет ясно, если 6 и 4 представить как двоичные числа:
0000110 (6) 0000110 (6)
and 0000100 (4) и and 0000001 (1)
______________ ______________
0000100 (4) 0000000 (0)
Впрочем, вовсе не обязательно записывать числа в виде нулей и единиц. Операция and в 99% случаев нужна для двух целей: проверить наличие битов или убрать (т.е. обнулить) некоторые из них.
Такая проверка нужна, когда число является набором флагов. Например, большое число системных ячеек памяти ПЭВМ содержит сведения о конфигурации машины или ее состоянии. При этом один байт может трактоваться так: бит 6 равен 1 — значит включен режим CapsLock, бит 4 равен 0 — следовательно какой-либо другой режим Lock выключен и т.д. Пусть A содержит этот самый байт с восемью флагами, и надо проверить состояние бита номер 5 (нумерация идет справа налево, от 0 до 7). Единица в бите 5 дает число 25 = 32. Это второй аргумент. Если в A в пятом бите есть единица, то должно выполниться условие
(A and 32) = 32
Осталось оформить все это в оператор IF. Можно проверить наличие сразу нескольких «включенных» битов, например, 5-го, 2-го и 0-го. Число с единицами в этих позициях и нулями в остальных равно 2+2 + 1 = 32+4+1 = 37. Если A среди прочих имеет единицы в битах 5, 2 и 0, то в этом случае будет истинным выражение
(A and 37) = 37
Исключение или выключение битов достигается следующим образом. Пусть надо исключить бит 3 из переменной A типа Byte (здесь важно знать тип, в который «умещается» текущее значение A). Исключить — значит, задать нулем. Первым делом определяется {167} число, в котором все биты равны 1, кроме бита номер 3. Для типа Byte оно равно (255 – 23) = 247, где 255 — максимальное значение, вписываемое в байт. Если теперь это число логически умножить на A, то единицы в 247 никак не повлияют на состояние битов в переменной A, а ноль в третьем бите заместит любое значение в A на том же месте. Таким образом, можно записать
A:= A and (255 – 8);
чтобы получить значение A с отключенным 3-м битом.
Все это верно и для нескольких битов сразу: если надо исключить биты 3 и 7, то просто запишем
A:= A and (255 – 8 – 128);
где 8 = 23 и 128 = 27.
Or — логическое сложение; оно же операция 'ИЛИ', определяется следующими действиями над битами:
[1] or [0] = [0] or [1] = [1]
[0] or [0] = [0]
[1] or [1] = [1]
Квадратные скобки обозначают один бит. Эта операция может с успехом применяться при включении (установки в 1) отдельных битов двоичного представления целых чисел. Так, если надо, чтобы бит 4 значения A стал равным единице, а остальные не изменились, то следует записать
A:= A or 16;
где 16 = 24. При этом не имеет значения, что было в 4-м бите значения A. В любом случае там появится единица.
Аналогичным образом можно включать сразу несколько битов, например, 4-й, 1-й и 0-й:
A:= A or (16 + 2 + 1);
Кроме перечисленных, введена еще одна операция xor — исключающее 'ИЛИ' (математическое название — «сложение по модулю 2»). Эта операция возвращает 0, если оба ее аргумента равны, и 1 в противном случае:
[1] xor [1] = [0]
[0] xor [0] = [0]
[1] xor [0] = [0] xor [1] = [1]
Операцию xor можно с успехом применять при смене значения бита (или нескольких битов) на противоположные. Пусть необходимо {168} переключить состояние бита 5 числа А. Это будет сделано операцией A xor 32, где 32 = 25.
Исключающее 'ИЛИ' обладает одной особенностью: примененное дважды к одной и той же переменной, оно восстановит ее исходное значение, т.е. всегда выполняется равенство:
A = (A xor B) xor B
Следующая группа поразрядных операций — циклические сдвиги (табл. 9.3).
Таблица 9.3
| Операция | Название | Форма записи |
| shl | Циклический сдвиг влево на N позиций | A shl N |
| shr | Циклический сдвиг вправо на N позиций | A shr N |
Приоритет операций shl и shr одинаков и среди всех остальных невысок (см. табл. 9.1). Поэтому, как правило, выражения сдвига должны быть заключены в скобки.
Суть операций shr и shl одинакова: они сдвигают двоичную последовательность значения A на N ячеек (битов) вправо или влево. При этом те биты, которые «уходят» за край разрядности (8, 16 и 32 в зависимости от значения A), теряются, а освободившееся место с другой стороны заполняется нулями (всегда при сдвиге влево и иногда вправо) или единицами (только при сдвиге вправо отрицательных значений типа ShortInt, Integer и LongInt). Например, число с двоичным представлением 11011011 будет трансформироваться при сдвигах влево следующим образом:
(11011011 shl 0) = 11011011
(11011011 shl 1) = 10110110
(11011011 shl 2) = 01101100
(11011011 shl 3) = 11011000
(11011011 shl 4) = 10110000
...
(11011011 shl 7) = 10000000 (11011011 shl 8 } = 00000000
Если бы число имело значение типа Word от 256 до 65535, то эффект был бы тем же, только биты «переезжали» бы в поле длиной 16 бит. Для LongInt поле составит 32 бита. При применении операций shl и shr к отрицательным величинам типов ShortInt, Integer, LongInt освобождаемое слева место заполняется единицами.{169}
Конечно, операции сдвига достаточно специфичны и реально нужны только при обработке битовых последовательностей. Пример их использования был дан на рис. 9.1. Там каждый бит последовательно сдвигается к самому левому краю, стирая тем самым все впереди стоящие биты, а затем возвращается в самую правую позицию, стирая тем самым все стоящие правее его биты. В итоге получаем число, равное 0 или 1, в зависимости от содержимого очередного бита.
Операция shl может заменять умножение целых чисел на степени двойки:
J shl 1 = J*2
J shl 2 = J*4
J shl 3 = J*8
Сжатие и кодирование информации. Обычная емкость памяти ПЭВМ (640K) — не так уж велика, как может показаться. Часто вопросы эффективного хранения данных становятся важными для работоспособности программ. Пусть, к примеру, нужно хранить в памяти выборку целых чисел со значениями от 0 до 15, состоящую из 80000 чисел. Так как минимальный тип для каждого числа применительно к Турбо Паскалю — Byte, то всего понадобится 80000 байт. Массив на 80000 байт не пропустит компилятор (максимум, что он сможет «переварить», — это 64K). Кроме того, для представления значения от 0 до 15 достаточно четырех битов, а отводится восемь.
Именно здесь заложена идея и принцип сжатия информации: в одном байте можно уместить два четырехбитовых значения. Тогда понадобится всего 40000 байт, что дает двукратный выигрыш! При этом потери заключаются в необходимости кодирования и декодирования значений. Процедуры преобразования могут иметь вид, показанный на рис. 9.2.
Если бы значения в выборке были целыми и имели диапазон 0..3 (т.е. занимали два бита), то можно было бы в один байт уместить четыре таких значения и т.д. Логика останется той же, изменятся лишь параметры в процедурах преобразования.
К сожалению, подобный подход нельзя применить к вещественным значениям. Единственное, что можно посоветовать — это посмотреть, нужны ли именно вещественные формы хранения данных. Так, если хранится массив вещественных (Real — 6 байт на элемент) значений размеров чего-либо в метрах с точностью до сантиметра, и самое длинное измерение не превосходит 2,55 м, то гораздо эффективнее будет хранить их как массив размеров в сантиметрах. И одно значение будет свободно размещаться в одном байте! Тип Byte занимает 1 байт — экономия шестикратная. {170}
| {Процедура кодирования X1 и X2 в один байт (X1, X2<=15) } PROCEDURE Code2to1(X1,X2: Byte; VAR X1X2: Byte); BEGIN X1X2:= X1 + (X2 shl 4) END; {Процедура декодирования X1 и X2 из одного байта } PROCEDURE DeCode1to2{ X1X2: Byte; VAR X1,X2: Byte); BEGIN X1:= X1X2 and 15; { X1X2 and $F } X2:= X1X2 shr 4 END; VAR {== ПРИМЕР ВЫЗОВА ==} C, C1, C2: Byte; BEGIN Code2to1(8,7, C); WriteLn('8 и 7 - кодируются в —> ',C); DeCode1to2(C, C1, C2); WriteLn(C:3, — декодируются в --> ',C1:-3,' и ',C2); ReadLn { пауза до нажатия клавиши ввода } END. |
Рис. 9.2