М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

В математике для представления чисел со знаком используется специаль­ный символ «-», за которым следует обычная запись абсолютного значения числа. Компьютеру с таким представлением работать неудобно. Поэтому боль­шинство компьютеров представляет целые числа со знаком в записи, называ­ющейся дополнением до двух *. Положительное число представляется старшим нулевым битом и следующим за ним обычным двоичным представлением зна­чения. Из этого вытекает, что самое большое положительное целое число, ко­торое может быть представлено словом из w битов, не превышает 2^W-1 - 1.

Для того чтобы получить представление числа -п по двоичному представ­лению В = b1b2...b_wчисла n:

• берут логическое дополнение В, т. е. заменяют в каждом b ноль на едини­цу, а единицу на ноль,

• прибавляют единицу.

Например, представление -1, -2 и -127 в виде 8-разрядных слов получается так:

У отрицательных значений в старшем бите всегда будет единица.

Дополнение до двух удобно тем, что при выполнении над такими пред­ставлениями операций обычной двоичной целочисленной арифметики полу­чается правильное представление результата:

(-!)-! = -2

1111 1111-00000001 = 1111 1110

Отметим, что строку битов 1000 0000 нельзя получить ни из какого поло­жительного значения. Она представляет значение -128, тогда как соответству­ющее положительное значение 128 нельзя представить как 8-разрядное число. Необходимо учитывать эту асимметрию в диапазоне типов integer, особенно при работе с типами short.

Альтернативное представление чисел со знаками — дополнение до единицы, в котором представление значения -n является просто дополнением п. В этом случае набор значений симметричен, но зато есть два представления для нуля: 0000 0000 называется положительным нулем, а 1111 1111 называется отрица­тельным нулем.

Если в объявлении переменной синтаксически не указано, что она без знака (например, unsigned), то по умолчанию она считается целой со знаком:

I

nt i; /* Целое со знаком в языке С */

I: Integer; -- Целое со знаком в языке Ada

Целочисленные операции

К целочисленным операциям относятся четыре основных действия: сложе­ние, вычитание, умножение и деление. Их можно использовать для составле­ния выражений:

а + b/с - 25* (d - е)

К целочисленным операциям применимы обычные математические правила старшинства операций; для изменения порядка вычислений можно исполь­зовать круглые скобки.

Результат операции над целыми числами со знаком не должен выходить за диапазон допустимых значений, иначе произойдет переполнение, как рассмотрено ниже. Для целых чисел без знака используется циклическая ариф­метика. Если short int хранится в 16-разрядном слове, то:

unsigned short int i; /* Диапазон i= 0...65535*/

i = 65535; /* Наибольшее допустимое значение*/

i = i + 1; /*Циклическая арифметика, i = 0 */

Разработчики Ada 83 сделали ошибку, не включив в язык целые без знака. Ada 95 обобщает концепцию целых чисел без знака до модульных типов, кото­рые являются целочисленными типами с циклической арифметикой по про­извольному модулю. Обычный байт без знака можно объявить как:

type Unsigned_Byte is mod 256;

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

Ada type Randomjnteger is mod 41;

Обратите внимание, что модульные типы в языке Ada переносимы, так как частью определения является только циклический диапазон, а не размер пред­ставления, как в языке С.

Деление

В математике в результате деления двух целых чисел а/b получаются два зна­чения: частное q и остаток r, такие что:

а = q * b + r

Так как результатом арифметического выражения в программах является единственное

значение, то для получения частного используют оператор «/», а для получения остатка применяют другой оператор (в языке С это «%», а в Ada — rem). Выражение 54/10 дает значение 5, и мы говорим, что результат операции был усечен (truncated). В языке Pascal для целочисленного деления используется специальная операция div.

При рассмотрении отрицательных чисел определение целочисленного де­ления не столь тривиально. Чему равно выражение -54/10: -5 или -6? Другими словами, до какого значения делается усечение: до меньшего («более отрица­тельного») или до ближайшего к нулю? Один вариант — это усечение в сторону нуля, поскольку, чтобы удовлетворить соотношение для целочис­ленного деления, достаточно просто сменить знак остатка:

-54 = -5*10 + (-4)

Однако существует и другая математическая операция, взятие по модулю (modulo), которая соответствует округлению отрицательных частных до мень­шего («более отрицательного») значения:

-54 = -6* 10+ 6

-54 mod 10 = 6

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

Значение операций «/» и «%» в языке С зависит от реализации, поэтому программы, использующие эти целочисленные операции, могут оказаться не­переносимыми. В Ada операция «/» всегда усекает в сторону нуля. Операция rem возвращает остаток, соответствующий усечению в сторону нуля, в то вре­мя как операция mod возвращает остаток, соответствующий усечению в сто­рону минус бесконечности.

Переполнение

Говорят, что операция приводит к переполнению, если она дает результат, ко­торый выходит за диапазон допустимых значений. Следующие рассуждения для ясности даются в терминах 8-разрядных целых чисел.

Предположим, что переменная i типа signed integer имеет значение 127 и что мы увеличиваем i на 1. Компьютер просто прибавит единицу к целочис­ленному представлению 127:

0111 1111+00000001 = 10000000

и получит -128. Это неправильный результат, и ошибка вызвана переполне­нием. Переполнение может приводить к странным ошибкам:

for (i = 0; i < j*k; i++)….

Если происходит переполнение выражения j*k, верхняя граница может ока­заться отрицательной и цикл не будет выполнен.

Предположите теперь, что переменные a, b и с имеют значения 90, 60 и 80, соответственно. Выражение (а - b + с) вычисляется как 110, потому что (а - b) дает 30, и затем при сложении получается 110. Однако оптимизатор для вычис­ления выражения может выбрать другой порядок, (а + с - b), давая непра­вильный ответ, потому что сложение (а + с) дает значение 170, что вызывает переполнение. Если вам в средней школе говорили, что сложение является коммутативным и ассоциативным, то речь шла о математике, а не о програм­мировании!

В некоторых компиляторах можно задать режим проверки на переполне­ние каждой целочисленной операции, но это может привести к чрезмерным издержкам времени выполнения, если обнаружение переполнения не делает­ся аппаратными средствами. Теперь, когда большинство компьютеров ис­пользует 32-разрядные слова памяти, целочисленное переполнение встреча­ется редко, но вы должны знать о такой возможности и соблюдать осторож­ность, чтобы не попасть в ловушки, продемонстрированные выше.

Реализация

Целочисленные значения хранятся непосредственно в словах памяти. Неко­торые компьютеры имеют команды для вычислений с частями слов или даже отдельными байтами. Компиляторы для этих компьютеров обычно помещают short int в часть слова, в то время как компиляторы для компьютеров, которые распознают только полные слова, реализуют целочисленные типы int и short int одинаково. Тип long int обычно распределяется в два слова, чтобы получить больший диапазон значений.

Сложение и вычитание компилируются непосредственно в соответствую­щие команды. Умножение также превращается в одну команду, но выпол­няется значительно дольше, чем сложение и вычитание. Умножение двух слов, хранящихся в регистрах R1 и R2, дает результат длиной в два слова и тре­бует для хранения двух регистров. Если регистр, содержащий старшее значе­ние, — не ноль, то произошло переполнение.

Для деления требуется, чтобы компьютер выполнил итерационный алго­ритм, аналогичный «делению в столбик», выполняемому вручную. Это дела­ется аппаратными средствами, и вам не нужно беспокоиться о деталях, но, ес­ли для вас важна эффективность, деления лучше избегать.

Арифметические операции выполняются для типа long int более чем вдвое дольше, нежели операции для int. Причина в том, что нужны дополнительные команды для «распространения» переноса, который может возникать, из слова младших разрядов в слово старших.

4.2. Типы перечисления

Языки программирования типа Fortran и С описывают данные в терминах компьютера. Данные реального мира должны быть явно отображены на типы данных, которые существуют на компьютере, в большинстве случаев на один из целочисленных типов. Например, если вы пишете программу для управле­ния нагревателем, вы могли бы использовать переменную dial для хранения текущей позиции регулятора. Предположим, что реальная шкала имеет четы­ре позиции: off (выключено), low (слабо), medium (средне), high (сильно). Как бы вы объявили переменную и обозначили позиции? Поскольку компьютер не имеет команд, которые работают со словами памяти, имеющими только четы­ре значения, для объявления переменной вы выберете тип integer, а для обо­значения позиций четыре конкретных целых числа (скажем 1, 2, 3, 4):

int dial; /* Текущая позиция шкалы */

if (dial < 4) dial++; /* Увеличить уровень нагрева*/

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

#define Off 1

#define Low 2

#define Medium 3

#define High 4

int dial;

if(dial<High)dial++;

Однако улучшение документации ничего не дает для предотвращения следу­ющих проблем:

dial=-1; /* Нет такого значения*/

dial = High + 1; /* Нераспознаваемое переполнение*/

dial = dial * 3; /* Бессмысленная операция*/

Другими словами, представление шкалы с четырьмя позициями в виде цело­го числа позволяет программисту присваивать значения, которые выходят за допустимый диапазон, и выполнять команды, бессмысленные для реального объекта. Даже если программист не создаст преднамеренно ни одну из этих проблем, опыт показывает, что они часто появляются в результате отсутствия I взаимопонимания между членами группы разработчиков программы, опеча- ток и других ошибок, типичных при создании сложных систем.

Решение состоит в том, чтобы разрешить разработчику программы созда- вать новые типы, точно соответствующие тем объектам реального мира, кото­рые нужно моделировать. Рассматриваемая здесь короткая упорядоченная последовательность значений настолько часто встречается, что современные языки программирования поддерживают создание типов, называемых типа­ми — перечислениями (enumiration types)*. В языке Ada вышеупомянутый при­мер выглядел бы так:

Ada type Heat is (Off, Low, Medium, High);

Dial: Heat;

Dial := Low;

if Dial < High then Dial := Heat'Succ(DialJ;

Dial:=-1; —Ошибка

Dial := Heat'Succ(High); -- Ошибка

Dial := Dial * 3; - Ошибка

Перед тем как подробно объяснить пример, обратим внимание на то, что в языке С есть конструкция, на первый взгляд точно такая же:

typedef enum {Off, Low, Medium, High} Heat;

Однако переменные, объявленные с типом Heat, — все еще целые, и ни од­на из вышеупомянутых команд не считается ошибкой (хотя компилятор мо­жет выдавать предупреждение):

Heat dial;

dial = -1; /*He является ошибкой!*/

dial = High + 1; /* Не является ошибкой! */

dial = dial * 3; /* Не является ошибкой! */

Характеристики

Список файлов книги