Целочисленные переменные

Тип целое число является основным для любого алгоритмического языка. Связано это с тем, что содержимое ячейки памяти или регистра процессора можно рассматривать как целое число. Адреса элементов памяти также представляют собой целые числа, с их помощью записываются машинные команды и т.д. Символы представляются в компьютере целыми числами - их кодами в некоторой кодировке. Изображения также задаются массивами целых чисел: для каждой точки цветного изображения хранятся интенсивности ее красной, зеленой и синей составляющей (в большинстве случаев - в диапазоне от 0 до 255). Как говорят математики, целые числа даны свыше, все остальное сконструировал из них человек.

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

232 - 1 = 4294967295

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

a+b = b+a, ab = ba (a+b) + c = a+(b+c), (ab)c = a(bc) a(b+c) = ab+ac

Интерпретация положительных и отрицательных чисел

В кольце вычетов невозможно определить порядок, согласованный с операциями (т.е. так, чтобы, к примеру, сумма двух положительных чисел была положительной). Таким образом, в компьютере нет, строго говоря, положительных и отрицательных целых чисел, поскольку компьютерные целые числа - это на самом деле элементы кольца вычетов. Выбирая либо неотрицательную, либо симметричную систему остатков, можно интерпретировать эти числа либо как неотрицательные в диапазоне от нуля до m-1, либо как отрицательные и положительные числа в диапазоне от -k до k, где k - целая часть от деления m на 2.

В программировании симметричная система остатков более популярна, поскольку трудно обойтись без отрицательных чисел. При этом следует понимать, что сумма двух положительных чисел может оказаться отрицательной, или, наоборот, сумма двух отрицательных чисел - положительной. Иногда в программировании такую ситуацию называют переполнением. Привычные свойства целочисленных операций в компьютере выполняются лишь для небольших чисел, когда результат операции не превосходит числа m = 232. В случае целочисленных переменных переполнение не является экстраординарной ситуацией и не приводит к аппаратным ошибкам или прерываниям. (Это, кстати, отличает компьютерные целые числа от вещественных.) Переполнение - совершенно нормальная ситуация, если вспомнить, что компьютер работает с элементами кольца вычетов по модулю m, а не с настоящими целыми числами.

Следует также отметить, что симметричная система остатков кольца Zm в случае четного m (а m для компьютера равно 232, т.е. четно) не вполне симметрична. Поскольку ноль не имеет знака, то число положительных остатков не может равняться числу отрицательных.

Какой остаток выбрать в классе эквивалентности числа k = m/2? Для этого элемента выполняется непривычное с точки зрения школьной математики равенство

k+k

0 (mod m),

т.е.

-k (mod m)

Как отрицательный остаток -k, так и положительный k в равной мере подходят для представления этого класса эквивалентности.
По традиции выбирается отрицательный остаток. Таким образом, в компьютере количество отрицательных целых чисел на единицу больше, чем количество положительных. Так как m = 232 = 4294967296, то k = 231 = 2147483648, и симметричная система остатков состоит из элементов

-2147483648, -2147483647, ..., -2, -1, 0, 1, 2, ..., 2147483647.

В двоичном представлении старший разряд у отрицательных целых чисел равен единице, у положительных - нулю. Двоичные разряды представления целого числа в программировании нумеруют от 0 до 31 справа налево. Старший разряд имеет номер 31 и часто называется знаковым разрядом. Таким образом, знаковый разряд равен единице у всех отрицательных чисел и нулю у неотрицательных. Двоичное представление максимального по абсолютной величине отрицательного числа k состоит из единицы и тридцати одного нуля:

-214748364810 = 100000000000000000000000000000002

Двоичное представление числа -1 состоит из тридцати двух единиц:

-110 = 111111111111111111111111111111112

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

214748364710 = 011111111111111111111111111111112

Следует отметить, что в программировании часто используют также короткие целые числа, двоичная запись которых занимает восемь разрядов, т.е. один байт, или шестнадцать разрядов, т.е. два байта. Работа с такими короткими целыми числами поддерживается на аппаратном уровне. В языке Си однобайтовым целым числам соответствует тип char (тип char в Си - это именно целые числа, символы представляются их целочисленными кодами), двухбайтовым - тип short. Однобайтовые целые числа - это элементы кольца вычетов Zm, где m = 28 = 256. Симметричная система остатков в этом случае состоит из элементов

-128, -127, ..., -2, -1, 0, 1, 2, ..., 127.

В случае двухбайтовых целых чисел (тип short) m = 216 = 65536, а симметричная система остатков состоит из элементов

-32768, -32767, ..., -2, -1, 0, 1, 2, ..., 32767.

Кольцо вычетов по модулю m

Целочисленный тип компьютера в точности соответствует важнейшему понятию математики - понятию кольца вычетов по модулю m. В качестве m выступает число 232 = 4294967296. В математике кольцо Zm определяется следующим образом. Все множество целых чисел Z разбивается на m классов, которые называются классами эквивалентности. Каждый класс содержит числа, попарная разность которых делится на m. Первый класс содержит числа

{...,-2m,-m,0,m,2m, ...}

второй

{..., -2m+1, -m+1, 1, m+1, 2m+1, ...}

последний

{..., -m-1, -1, m-1, 2m-1, 3m-1, ...}

Элементами кольца Zm являются классы эквивалентности. Их ровно m, так что, в отличие от множества целых чисел Z, кольцо Zm содержит конечное число элементов. Операции с классами выполняются следующим образом: надо взять по одному представителю из каждого класса, произвести операцию и определить, в какой класс попадает результат. Этот класс и будет результатом операции. Легко показать, что он не зависит от выбора представителей.

Все числа, принадлежащие одному классу эквивалентности, имеют один и тот же остаток при делении на m. Таким образом, класс эквивалентности однозначно определяется остатком от деления на m. Традиционно остаток выбирается неотрицательным, в диапазоне от 0 до m -1. Остатки используют для обозначения классов, при этом используются квадратные скобки. Так, выражение [5] обозначает класс эквивалентности, состоящий из всех чисел, остатки которых при делении на m равны пяти. Все кольцо Zm состоит из элементов

[0],[1],[2], ...,[m-1],

например, кольцо Z5 состоит из элементов

[0],[1],[2],[3],[4].

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

3%5 = 3, 17%5 = 2, (-3)%5 = 2, (-17)%5 = 3.

Отсюда видно, что в школьной математике не выполняется равенство

(-a)%b = -(a%b),

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

3%5 = 3, 17%5 = 2, (-3)%5 = -3, (-17)%5 = -2.

При делении на положительное число знак остатка совпадает со знаком делимого. При таком определении тождество

(-a)%b = a%(-b) = -(a%b)

справедливо. Это позволяет во многих алгоритмах не следить за знаками (так же, как в тригонометрии формулы, выведенные для углов, меньших 90 градусов, автоматически оказываются справедливыми для любых углов).

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

0,1,2,3, ...m-1.

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

k = целая часть(m/2)

тогда симметричная система остатков при нечетном m состоит из элементов

-k, -k+1, ..., -1, 0, 1, ..., k-1, k,

а при четном m - из элементов

-k, -k+1, ..., -1, 0, 1, ..., k-1.

Например, при m = 5 симметричная система остатков состоит из элементов

-2, -1, 0, 1, 2.

Кольцо Zm можно представлять состоящим из элементов, принадлежащих выбранной системе остатков. Арифметические операции определяются следующим образом: надо взять два остатка, произвести над ними операцию как над обычными целыми числами и выбрать тот остаток, которой лежит в том же классе эквивалентности, что и результат операции. Например, для симметричной системы остатков множества Z5 имеем:

1+1 = 2, 1+2 = -2, 1+(-2) = -1, 1+(-1) = 0, (-2)+2 = 0, (-2)+(-2) = 1.

Машинный эпсилон

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

a+b = a при b

Более того, для сложения не выполняется закон ассоциативности:

a+(b+c)

(a+b)+c

Действительно, пусть ? - максимальное плавающее число среди чисел, удовлетворяющих условию

1.0+? = 1.0

(приведенные выше рассуждения показывают, что такие числа существуют). Тогда

(1.0+?)+?

1.0+(?+?)

поскольку левая часть неравенства равна единице, а правая строго больше единицы (это следует из максимальности числа ?).

Число ? часто называют машинным эпсилоном или, чуть менее корректно, машинным нулем, поскольку при прибавлении к единице оно ведет себя как ноль. Величина машинного эпсилона характеризует точность операций компьютера. Она примерно одинакова для всех современных компьютеров: большинство процессоров работают с восьмибайтовыми плавающими числами (тип double в Си), а арифметика плавающих чисел подчиняется строгим международным стандартам.

Оценим величину машинного эпсилона для типа double. Число 1.0 записывается в плавающей форме как

1.0 = +20*1.0.

Порядок плавающего числа 1.0 равен нулю. При сложении 1.0 с числом ? производится выравнивание порядка путем многократного сдвига мантиссы числа ? вправо и увеличения его порядка на 1. Поскольку все разряды числа ? должны в результате выйти за пределы разрядной сетки, должно быть выполнено 53 сдвига. Порядок числа ? после этого должен стать равным порядку числа 1.0, т.е. нулю. Следовательно, изначально порядок числа ? должен быть равным -53:

? = 2-53*m

где m - число в диапазоне от единицы до двух. Таким образом, величина машинного эпсилона составляет примерно

2-53

10-16

Приблизительно точность вычислений составляет 16 десятичных цифр. (Это также можно оценить следующим образом: 53 двоичных разряда составляют примерно 15.95 десятичных, поскольку 53/log210

53/3.321928

15.95.)

В случае четырехбайтовых плавающих чисел (тип float языка Си) точность вычислений составляет примерно 7 десятичных цифр. Это очень мало, поэтому тип float чрезвычайно редко применяется на практике. К тому же процессор сконструирован для работы с восьмибайтовыми вещественными числами, а при работе с четырехбайтовыми он все равно сначала приводит их к восьмибайтовому типу. В программировании следует избегать типа float и всегда пользоваться типом double.

Некоторые процессоры применяют внутреннее представление плавающих чисел с большим количеством разрядов мантиссы. Например, процессор Intel использует 80-битовое (десятибайтовое) представление. Поэтому точность вычислений, которые не записывают промежуточные результаты в память, может быть несколько выше указанных оценок.

Кроме потери точности, при операциях с вещественными числами могут происходить и другие неприятности:

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

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

бесконечно большое число - это плавающее число с очень большим положительным порядком и, таким образом, очень большое по абсолютной величине.Оно может иметь знак плюс или минус; бесконечно малое, или денормализованное, число - это ненулевое плавающее число с очень большим отрицательным порядком (т.е. очень маленькое по абсолютной величине); Not a Number, или NaN - двоичный код, который не является корректным представлением какого-либо вещественного числа.

Любые операции с константой NaN приводят к прерыванию, поэтому она удобна при отладке программы - ею перед началом работы программы инициализируются значения всех вещественных переменных. Если в результате ошибки программиста при вычислении выражения используется переменная, которой не было присвоено никакого значения, то происходит прерывание из-за операции со значением NaN и ошибка быстро отслеживается. К сожалению, в случае целых чисел такой константы нет: любой двоичный код представляет некоторое целое число.

Типы переменных

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

Вещественные переменные

Вещественные числа представляются в компьютере в так называемой экспоненциальной, или плавающей, форме. Вещественное число r имеет вид

r = ±2e* m

Представление числа состоит из трех элементов:

знак числа - плюс или минус. Под знак числа отводится один бит в двоичном представлении, он располагается в старшем, т.е. знаковом разряде. Единица соответствует знаку минус, т.е. отрицательному числу, ноль - знаку плюс. У нуля знаковый разряд также нулевой; показатель степени e, его называют порядком или экспонентой. Экспонента указывает степень двойки, на которую домножается число. Экспонента может быть как положительной, так и отрицательной (для чисел, меньших единицы). Под экспоненту отводится фиксированное число двоичных разрядов, обычно восемь или одиннадцать, расположенных в старшей части двоичного представления числа, сразу вслед за знаковым разрядом; мантисса m представляет собой фиксированное количество разрядов двоичной записи вещественного числа в диапазоне от 1 до 2:

m<2

Следует подчеркнуть, что левое неравенство нестрогое - мантисса может равняться единице, а правое - строгое, мантисса всегда меньше двух. Разряды мантиссы включают один разряд целой части, который ввиду приведенного неравенства всегда равен единице, и фиксированное количество разрядов дробной части. Поскольку старший двоичный разряд мантиссы всегда равен единице, хранить его необязательно, и в двоичном коде он отсутствует. Фактически двоичный код хранит только разряды дробной части мантиссы.

В языке Си вещественным числам соответствуют типы float и double. Элемент типа float занимает 4 байта, в которых один бит отводится под знак, восемь - под порядок, остальные 23 - под мантиссу (на самом деле, в мантиссе 24 разряда, но старший разряд всегда равен единице, поэтому хранить его не нужно). Тип double занимает 8 байтов, в них один разряд отводится под знак, 11 - под порядок, остальные 52 - под мантиссу. На самом деле в мантиссе 53 разряда, но старший всегда равен единице и поэтому не хранится.
Поскольку порядок может быть положительным и отрицательным, в двоичном коде он хранится в смещенном виде: к нему прибавляется константа, равная абсолютной величине максимального по модулю отрицательного порядка. В случае типа float она равна 127, в случае double - 1023. Таким образом, максимальный по модулю отрицательный порядок представляется нулевым кодом.

Основным типом является тип double, именно он наиболее естественен для компьютера. В программировании следует по возможности избегать типа float, так как его точность недостаточна, а процессор все равно при выполнении операций преобразует его в тип double. (Один из немногих случаев, где применение типа float оправдано, - трехмерная компьютерная графика.)

Несколько примеров представления вещественных чисел в плавающей форме:

1.0 = +20*1.0

Здесь порядок равен 0, мантисса - 1. В двоичном коде мантисса состоит из одних нулей, так как старший разряд мантиссы (всегда единичный) в коде отсутствует. Порядок хранится в двоичном коде в смещенном виде, он равен 127 в случае float и 1023 в случае double;

3.5 = +21*1.75

Порядок равен единице, мантисса состоит из трех единиц, из которых в двоичном коде хранятся две: 1100...0; смещенный порядок равен 128 для float и 1024 для double;

0.625 = +2-1*1.25

Порядок отрицательный и равен -1, дробная часть мантиссы равна 0100...0; смещенный порядок равен 126 для float и 1022 для double;

100.0 = +26*1.5625

Порядок равен шести, дробная часть мантиссы равна 100100...0; смещенный порядок равен 133 для float и 1029 для double.

При выполнении сложения двух положительных плавающих чисел происходят следующие действия:

выравнивание порядков. Определяется число с меньшим порядком. Затем последовательно его порядок увеличивается на единицу, а мантисса делится на 2, пока порядки двух чисел не сравняются. Аппаратно деление на 2 соответствует сдвигу двоичного кода мантиссы вправо, так что эта операция выполняется быстро. При сдвигах правые разряды теряются, из-за этого может произойти потеря точности (в случае, когда правые разряды ненулевые); сложение мантисс; нормализация: если мантисса результата стала равна или превысила двойку, то порядок увеличивается на единицу, а мантисса делится на 2.В результате этого мантисса попадает в интервал 1

m<2. При этом возможна потеря точности, а также переполнение, когда порядок превышает максимально возможную величину.

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

Запись вещественных констант

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

1.2, 0.725, 1., .35, 0.

В трех последних случаях отсутствует либо дробная, либо целая часть. Десятичная точка должна обязательно присутствовать, иначе константа считается целой. Отметим, что в программировании именно точка, а не запятая, используется для отделении дробной части; запятая обычно служит для разделения элементов списка.

Экспоненциальная форма записи вещественной константы содержит знак, мантиссу и десятичный порядок (экспоненту). Мантисса - это любая положительная вещественная константа в форме с фиксированной точкой или целая константа. Порядок указывает степень числа 10, на которую домножается мантисса. Порядок отделяется от мантиссы буквой "e" (от слова exponent), она может быть прописной или строчной. Порядок может иметь знак плюс или минус, в случае положительного порядка знак плюс можно опускать. Примеры:

1.5e+6 константа эквивалентна 1500000.0 1e-4 константа эквивалентна 0.0001 -.75E3 константа эквивалентна -750.0

Логические переменные и выражения

Логические переменные принимают два значения: истина и ложь. Логические, или условные, выражения используются в качестве условия в конструкциях ветвления "если ... то ... иначе ... конец если" и цикла "пока". В первом случае в зависимости от истинности условия выполняется либо ветвь программы после ключевого слова "то", либо после "иначе"; во втором случае цикл выполняется до тех пор, пока условие продолжает оставаться истинным.

В качестве элементарных условных выражений используются операции сравнения: можно проверить равенство двух выражений или определить, какое из них больше. Любая операция сравнения имеет два аргумента и вырабатывает логическое значение "истина" или "ложь" (true и false в языке C++). Мы будем обозначать операции сравнения так, как это принято в языке Си:

операция проверки равенства двух выражений обозначается двойным знаком равенства == (мы не используем обычный знак равенства во избежание путаницы, поскольку часто знак равенства применяется для обозначения операции присваивания); неравенство

обозначается != (в Си восклицательный знак используется для отрицания); для сравнения величин выражений применяются четыре операции больше >, больше или равно `>=, меньше <, меньше или равно <=.

Несколько примеров логических выражений:

x == 0 - выражение истинно, если значение переменной x равно нулю, и ложно в противном случае;

0!= 0 - выражение ложно;

3>= 2 - выражение истинно.

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

результат логической операции "и" истинен, когда истинны оба ее аргумента. Например, логическое выражение

0 <= x и x <= 1

истинно, когда значение переменной x принадлежит отрезку [0, 1]. Логическую операцию "и" называют также логическим умножением или конъюнкцией; в языке Си логическое умножение обозначается двойным амперсандом &&; результат логической операции "или" истинен, когда истинен хотя бы один из ее аргументов.
Например, логическое выражение

x != 0 или y != 0

ложно в том и только том случае, когда значения обеих переменных x и y равны нулю. Логическую операцию "или" называют также логическим сложением или дизъюнкцией; в Си логическое сложение обозначается двойной вертикальной чертой ||; в отличие от логических операций "и" и "или", логическая операция "не" имеет только один аргумент. Ее результат истинен, когда аргумент ложен, и, наоборот, ложен, когда аргумент истинен. Например, логическое выражение

не x == 0

истинно, когда значение переменной x отлично от нуля. Логическая операция "не" называется логическим отрицанием (иногда негацией); в Си логическое отрицание обозначается восклицательным знаком "!".

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

Обратим внимание на чрезвычайно важную особенность операций реализации логического сложения и умножения - так называемое сокращенное вычисление результата. А именно, в случае логического умножения всегда сначала вычисляется значение первого аргумента. Если оно ложно, то значение выражения полагается ложным, а второй аргумент не вычисляется вообще! Благодаря этой особенности можно корректно использовать выражения вроде

x != 0 и y/x > 1

При вычислении значения этого выражения сначала вычисляется первый аргумент конъюнкции "x != 0". Если значение переменной x равно нулю, то первый аргумент ложен и значение второго аргумента "y/x > 1" уже не вычисляется. Это очень хорошо, поскольку при попытке его вычислить произошло бы аппаратное прерывание из-за деления на ноль.

То же самое относится и к логическому сложению. Сначала всегда вычисляется первый аргумент логической операции "или". Если он истинен, то значение выражения полагается истинным, а второй аргумент не вычисляется вообще.Таким образом, операции логического сложения и умножения, строго говоря, не коммутативны. Может так случиться, что выражение "a и b" корректно, а выражение "b и a" - нет. Программисты очень часто сознательно используют эту особенность реализации логических операций.

Массивы

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

Все элементы массива имеют один и тот же тип. Элементы массива обычно нумеруются индексами от 0 до n-1, где n - число элементов массива. В некоторых языках можно задавать границы изменения индексов, в других нижняя граница значения индекса равна единице, а не нулю. Мы, тем не менее, будем придерживаться языка Си (а также C++, Java, C#), в котором нижней границей индекса всегда является ноль. Это очень удобно, т.к. индекс элемента массива в этом случае равен его смещению относительно начала массива. Длина массива задается при его описании и не может быть изменена в процессе работы программы.

При описании массива указывается тип и число его элементов. Тип записывается перед именем массива, размер массива указывается в квадратных скобках после его имени. Примеры:

цел a[100]; описан массив целых чисел размера 100 (индекс меняется от 0 до 99) вещ r[1000]; описан вещ. массив из 1000 элементов.

В языке Си соответствующие описания выглядят следующим образом:

int a[100]; double r[1000];

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

a[3] := 0; элементу массива a с индексом 3 присваивается значение 0; a[10] := a[10]*2; элемент массива a с индексом 10 удваивается.

Массив - это самая важная конструкция алгоритмического языка. Важность массива определяется тем, что память компьютера логически представляет собой массив (его можно рассматривать как массив байтов или как массив четырехбайтовых машинных слов). Индекс в этом массиве обычно называют адресом. Элементы массива читаются и записываются исключительно быстро, за одно действие, независимо от размера массива и величины индекса. Для программиста конструкция массива как бы дана свыше. Большинство других структур данных, используемых в программировании, моделируются на базе массива.

Символьные переменные

Значением символьной переменной является один символ из фиксированного набора. Такой набор обычно включает буквы, цифры, знаки препинания, знаки математических операций и различные специальные символы (процент, амперсенд, звездочка, косая черта и др.). Подчеркнем, что, в отличие от строковой переменной, символьная всегда содержит ровно один символ. (Строковая содержит строку из нескольких символов.)

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

диапазоном значений кодов. Например, самая распространенная в мире кодировка ASCII (от слов American Standard Code of Information Interchange - Американский стандартный код обмена информацией) имеет диапазон значений кодов от 0 до 127, т.е. требует семь бит на символ. Большинство современных кодировок имеют диапазон кодов от 0 до 255, т.е. один байт на символ. Наконец, сейчас во всем мире осуществляется переход на кодировку Unicode, которая использует коды в диапазоне от 0 до 65535, т.е. 2 байта на символ; множеством изображаемых символов. Например, кодировка ASCII содержит буквы латинского алфавита, в западноевропейской кодировке к символам ASCII добавлены буквы с умлаутами и акцентами, дополнительные знаки препинания, в частности, испанские перевернутые вопросительные и восклицательные знаки, и другие символы европейских языков, основанных на латинской графике. Любая из русских кодировок содержит кириллицу; отображением множества кодов на множество символов. Например, русские кодировки КОИ-8 (Код обмена информацией восьмибитовый) и "Windows CP-1251", традиционно используемые в операционных системах Unix и MS Windows, имеют один и тот же диапазон кодов и один и тот же набор символов, но отображения их различны (одни и те же символы имеют разные коды в кодировках КОИ-8 и Windows).

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

кодировка КОИ-8 ( это наиболее старый стандарт, принятый еще в конце 70-х годов XX века). КОИ-8 в основном используется в системе Unix и до недавнего времени была стандартом де-факто для русскоязычной электронной почты. Последнее время, однако, все чаще в электронной почте используют кодировку Windows; так называемая альтернативная кодировка CP-866, которая используется в системе MS DOS. Она не удовлетворяет некоторым требованиям международных стандартов - например, ряд русских букв совпадает с кодами символов, используемых для управления передачей по линии. Альтернативная кодировка постепенно уходит в прошлое вместе с системой DOS; кодировка Windows CP-1251, которая появилась значительно позже кодировки КОИ-8, но создатели русской версии Windows не захотели воспользоваться КОИ-8 (по-видимому, из-за того, что коды русских букв в КОИ-8 не упорядочены в соответствии с алфавитом; в CP-1251 коды русских букв упорядочены, за исключением буквы е). В связи с распространением операционной системы Windows, кодировка Windows получает все большее распространение; кодировка, используемая в компьютерах Apple Macintosh.

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

С повсеместным переходом на кодировку Unicode все проблемы такого рода должны исчезнуть. Кодировка Unicode включает символы алфавитов всех европейских стран и кириллицу. К сожалению, большинство существующих компьютерных программ приспособлено к представлению одного символа в виде одного байта. Поэтому в настоящее время часто используется промежуточное решение: компьютерные программы работают с внутренним представлением символов в кодировке Unicode (такое решение принято в языках Java и C#). При записи в файл символы Unicode приводятся к однобайтовой кодировке в соответствии с текущей языковой установкой.При этом, конечно, часть символов теряется - например, в кодировке Windows невозможно одновременно записать русские буквы и немецкие умлауты, поскольку умлауты в западно-европейской кодировке имеют те же коды, что и русские буквы в русской кодировке.

Текстовые строки

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

строка заканчивается символом с нулевым кодом, т.е. либо нулевым байтом в случае однобайтового представления символов, либо двумя нулевыми байтами в случае двухбайтового представления. Такой способ принят в языке Си. Отметим, что нулевой байт - это вовсе не символ '0'! Символ '0' имеет код 48 в кодировках ASCII и UNICODE, а изображаемых символов с нулевым кодом не существует; строка в качестве первого элемента (байта или двух байтов) содержит общее число символов, не включая начального элемента. Затем идут сами символы в указанном количестве. Такой способ используется в языке Паскаль.

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

Впрочем, существуют и другие способы представления строк, которые используются в объектно-ориентированных языках. Строка рассматривается как объект, внутреннее устройство которого скрыто от пользователя, хотя, как правило, он содержит массив или адрес массива символов и длину строки. Обычно в случае представления строк в виде объектов ограничения на длину строки отсутствуют.

Арифметический цикл

В рассмотренных выше программах в цикле перебираются элементы массива с индексом i, где i пробегает значения от 0 до n-1 (в последней программе - от 0 до n, поскольку многочлен n-й степени имеет n+1 коэффициент). Для удобства записи таких циклов большинство языков программирования предоставляет конструкцию арифметического цикла. В нем используется так называемая переменная цикла, т.е. целочисленная переменная, которая последовательно принимает значения в указанных пределах. Для каждого значения переменной цикла выполняется тело цикла, в котором эта переменная может использоваться.

цикл для i от a до b | . . . | тело цикла | . . . конец цикла

Здесь переменная цикла i последовательно принимает значения от a до b с шагом 1, где a и b - некоторые целочисленные выражения. Таким образом, всего тело цикла выполняется b-a+1 раз. Если b меньше, чем a, то цикл не выполняется ни разу. Возможна также конструкция арифметического цикла с шагом s, отличным от единицы:

цикл для i от a до b шаг s | . . . | тело цикла | . . . конец цикла

Переменная цикла последовательно принимает значения a, a+s, a+2s, ... до тех пор, пока ее значение содержится в отрезке [a,b]. Для каждого значения переменной цикла выполняется тело цикла. Шаг может быть и отрицательным, в этом случае b должно быть не больше, чем a, иначе цикл не выполняется ни разу.

В принципе, без конструкции арифметического цикла можно обойтись, поскольку ее можно смоделировать с помощью цикла "пока". А именно, конструкция

цикл для i от a до b | . . . | тело цикла | . . . конец цикла

эквивалентна конструкции

i := a цикл пока i <= b | . . . | тело цикла | . . . | i := i + 1 конец цикла

Однако традиционно арифметический цикл включается в большинство языков высокого уровня. С использованием арифметического цикла схема Горнера переписывается следующим образом:

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

Индуктивные функции на последовательностях и индуктивные расширения

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

Sn = {a0, a1, ..., an-1}

длины n. С помощью знака & обозначим операцию приписывания нового элемента справа к последовательности (ее называют также конкатенацией):

Sn+1 = Sn&an = {a0, a1, ..., an-1, an}

Пусть f(S) - некоторая функция на множестве последовательностей, например, сумма элементов последовательности. Функция называется индуктивной, если при добавлении нового элемента к последовательности новое значение функции можно вычислить, зная только старое значение функции и добавленный элемент. На математическом языке функция

f:W

где W - множество всех последовательностей, составленных из элементов некоторого множества X, индуктивна, если существует функция G от двух аргументов

G:Y*X

такая, что для любой последовательности S из W и любого элемента a из X значение функции f на последовательности S, к которой добавлен элемент a, вычисляется с помощью функции G:

f(S&a) = G(f(S), a).

Функция G по паре (y, a), где y - старое значение функции f на последовательности S и a - элемент, добавленный к последовательности, вычисляет новое значение y, равное значению функции f на новой последовательности.

В примере с суммой элементов последовательности функция G равна сумме элементов y и a:

G(y, a) = y+a.

В примере с максимальным элементом последовательности функция G равна максимуму:

G(y, a) = max(y,a).

В примере со схемой Горнера вычисления значения многочлена в точке t, где коэффициенты многочлена заданы в последовательности по убыванию степеней, функция G равна

G(y, a) = yt+a.

Во всех трех случаях рассматриваемая функция на последовательности индуктивна.

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

Таким образом, для каждой конкретной индуктивной функции надо лишь правильно задать ее значение на пустой последовательности (инициализация) и определить, как новое значение функции вычисляется через старое при добавлении к последовательности очередного элемента, т.е. задать функцию G(y,x). Схема вычисления для всех индуктивных функций одна и та же.

Однако не все функции на последовательностях являются индуктивными. Рассмотрим следующий пример. Пусть коэффициенты многочлена заданы в последовательности по убыванию степеней. Надо вычислить значение производной многочлена в точке x = 2. Обозначим через

S = {a0, a1, ..., an}

последовательность коэффициентов многочлена

p(x) = a0xn+a1xn-1+...+an

и через f(S) значение производной многочлена p'(x) в точке x =2:

f(S) = p'(2)

Покажем, что функция f не индуктивна. Достаточно указать две последовательности S1 и S2, такие, что значения функции f на них совпадают, но при добавлении к последовательностям S1 и S2 одного и того же элемента a новые значения функции уже не равны:

f(S1) = f(S2), f(S1&a)

f(S2&a)

Возьмем последовательности

S1 = {1}, S2 = {1, -4,1}.

Им соответствуют многочлены

p1(x) = 1, p2(x) = x2-4x+1

Производные многочленов равны

p'(x) = 0, p'2(x)= 2x-4

Значения обеих производных в точке x=2 равны нулю, т.е.

f(S1) = p'1(2) = 0, f(S2) = p'2(2) = 2*2-4 = 0

Припишем теперь к обеим последовательностям элемент a = 1:

S1&1 = {1,1}, S2&1 = {1, -4,1,1}.

Новым последовательностям соответствуют многочлены

g1(x) = x+1, g2(x) = x3-4x2+x+1

Их производные равны

g1(x) = 1, g2(x) = 3x2-8x+1

Значения производных в точке x=2 равны соответственно

f(S1&1) = g'1(2) = 1 f(S2&1) = g'2(2) = 12-16+1 = -3

Мы видим, что значения f(S1) и f(S2) совпадают, но значения f(S1&1) и f(S2&1) не совпадают. Следовательно, функция f не индуктивна.

Как поступать в случае, когда функция f не индуктивна? Общий рецепт следующий: надо придумать индуктивную функцию F, такую, что, зная значение F, легко можно вычислить исходную функцию f. Функция F называется индуктивным расширением функции f.

Приведем формальные определения. Пусть исходная функция на множестве W всех последовательностей

f:W

не индуктивна. Индуктивная функция

F:W

называется индуктивным расширением функции f, если существует отображение

P:Z

такое, что для всякой последовательности S, принадлежащей W, выполняется равенство

f(S) = P(F(S))

(т.е. функция f равна композиции отображений F и P, f = P?F.) Отображение P обычно называют проекцией множества Z на Y.

Как построить индуктивное расширение функции f? Это творческий момент, готового рецепта на все случаи не существует. Неформальный рецепт следующий: надо понять, какой информации не хватает для того, чтобы уметь вычислять новое значение функции на последовательности при добавлении к последовательности нового элемента. Эту информацию надо хранить дополнительно к значению функции. Отсюда и появился термин расширение: вычисляется более сложная, расширенная, функция, чтобы по ней затем восстановить исходную. Как правило, значением индуктивного расширения F является пара (y, h), где y - значение исходной функции f, а h - некоторая дополнительная информация, позволяющая перевычислять значение y при добавлении нового элемента к последовательности. Таким образом, множество Z значений индуктивного расширения

F:W

чаще всего является множеством пар (y, h), т.е. декартовым произведением:

Z = Y*H

Отображение P на практике должно легко вычисляться. Так оно и есть в случае декартово произведения - это просто проекция на первый аргумент.

P(y, h) = y

Рассмотрим пример с вычислением производной многочлена в точке; коэффициенты многочлена заданы в последовательности по убыванию степеней. При добавлении к последовательности

Sk = {a0, a1, ...,ak}

нового коэффициента ak+1 получаем последовательность

Sk+1 = S&ak+1 = {a0, a1, ...,ak, ak+1}

Пусть этим двум последовательностям соответствуют многочлены pk(x) и pk+1(x). Тогда

pk+1(x) = pk(x)*x + ak+1.

Дифференцируя это равенство, получим:

p'k+1(x) = p'k(x)*x + pk(x).

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

F:S

(p'(t), p(t))

Новое значение производной вычисляется по приведенной выше формуле через старое значение производной и старое значение многочлена. После этого вычисляется новое значение многочлена по схеме Горнера.

Выпишем алгоритм вычисления производной многочлена.

Другой пример неиндуктивной функции - это среднее арифметическое значение элементов последовательности. Индуктивным расширением является пара (сумма элементов последовательности, длина последовательности):

F(S) = (сумма(S), длина(S)).

Легко видеть, что функция F индуктивна. При известном значении функции F не составляет труда вычислить исходную функцию:

среднее арифметическое(S) = сумма(S)/длина(S).

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

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

Схема Горнера

Рассмотрим еще один важный пример функции на последовательности. Пусть дана последовательность коэффициентов многочлена p(x) по убыванию степеней:

p(x) = a0xn +a 1xn-1 + ... + an

Нужно вычислить значение многочлена в точке x = t. Алгоритм, основанный на просмотре последовательности коэффициентов в направлении от старшего к младшему, называется схемой Горнера. Проиллюстрируем его идею на примере многочлена третьей степени:

p(x) = ax3+bx2+cx+d

Его можно представить в виде

p(x) = ((ax+b)x+c)x+d

Для вычисления значения многочлена достаточно трех умножений и трех сложений. В общем случае, многочлен представляется в следующем виде:

p(x) = (...((a0x+a1)x+a2)x+...+an-1)x+an.

Обозначим через pk(x) многочлен k-ой степени, вычисленный по коэффициентам a0, a1, ..., ak:

pk(x) = a0xk + a1xk-1 + ... + ak.

Тогда

pk+1(x) = pk(x)x + ak+1

т.е. при считывании нового коэффициента многочлена надо старое значение многочлена умножить на значение x, а затем прибавить к нему новый коэффициент.

Выпишем алгоритм:

Значения "минус" и "плюс бесконечность"

Как реализовать воображаемые элементы "минус бесконечность" и "плюс бесконечность" при программировании на конкретных алгоритмических языках, а не на псевдокоде? Вспомним, что компьютер может представлять не все возможные числа, а только их ограниченное подмножество. Поэтому для компьютера существует минимальное и максимальное целое и вещественное числа. В языке Си эти константы записаны в стандартных заголовочных файлах "limits.h" для целочисленных типов и "float.h" для вещественных типов. Для типа int эти константы называются INT_MIN и INT_MAX.

INT_MIN = (-2147483647 - 1) INT_MAX = 2147483647

Для вещественных типов максимальное и минимальное числа равны по абсолютной величине и отличаются лишь знаками, поэтому специального названия для максимальной по абсолютной величине отрицательной константы не существует. Максимальное число типа float называется FLT_MAX, типа double - DBL_MAX.

FLT_MAX = 3.402823466e+38 DBL_MAX = 1.7976931348623158e+308

Стоит отметить, что через FLT_MIN и DBL_MIN обозначены минимальные положительные числа, а вовсе не максимальные по абсолютной величине отрицательные!

FLT_MIN = 1.175494351e-38 DBL_MIN = 2.2250738585072014e-308 Константа DBL_MAX является нормальным числом, она не равна специальному бесконечно большому значению, см. с. 1.4.2. Использовать бесконечно большое значение опасно, т.к. операции с ним могут приводить к ошибкам.

Итак, в качестве значений "минус бесконечность" и "плюс бесконечность" можно использовать константы INT_MIN и INT_MAX для типа int. Для типа double в качестве значений "минус бесконечность" и "плюс бесконечность" можно использовать выражения (-DBL_MAX) и DBL_MAX. Не забудьте только при программировании на Си подключить стандартные заголовочные файлы:

#include <limits.h>

для целых типов и

#include <float.h>

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

1.0e+30

т.е. десять в тридцатой степени. (Можно даже использовать 1.0e+7, т.е. десять миллионов, но не стоит мелочиться.)

Алгоритм Евклида вычисления наибольшего общего делителя

Пусть даны два целых числа m и n, хотя бы одно из которых не равно нулю. Требуется найти их наибольший общий делитель. Напомним, что наибольшим общим делителем двух чисел m и n называется такой их общий делитель d, который делится на любые другие общие делители d'. Такое определение НОД подходит не только для чисел, но и для многочленов, поскольку в нем не используется сравнение по величине. Наибольший общий делитель определен с точностью до обратимого множителя; в частности, поскольку в кольце чисел обратимы только элементы ±1, НОД целых чисел определен с точностью до знака.

В качестве пространства X рассматривается множество пар целых чисел

X = {(a,b) | a, b

Z, a

0 или b

Надо вычислить НОД для заданной пары чисел (m,n). В качестве инварианта используем утверждение, что НОД текущей пары чисел равен НОД исходной пары:

I(a,b): НОД(a,b) = НОД(m,n).

Следовательно, цикл надо строить таким образом, чтобы при изменении переменных a, b наибольший общий делитель пары (a,b) оставался неизменным. В качестве начальной точки x0 используется пара (m,n).

Обозначим через r остаток от деления a на b:

a = gb+r, где |r| < |b|.

Тогда нетрудно доказать, что НОД(b,r) = НОД(a,b). Достаточно показать, что множества общих делителей пары (b,r) и пары (a,b) совпадают. Пусть d делит b и r. Тогда из равенства a = gb+r вытекает, что d делит a. Обратно, пусть d делит a и b. Из определения остатка имеем:

r = a-gb.

Так как правая часть равенства делится на d, то r тоже делится на d.

Итак, при замене пары (a,b) на пару (b,r) НОД не меняется. Обозначим через T отображение

T:(a,b)

(b,r)

Условие I(a,b) является инвариантным для отображения T.

Осталось только определить условие завершения цикла Q(a,b). Выполнение этого условия должно обеспечивать решение задачи, т.е. нахождение HOД чисел a, b. Для какой пары чисел их НОД можно сразу вычислить? Проще всего, когда одно из чисел равно нулю. В этом случае

НОД(a,0) = a

Итак, в качестве условия завершения цикла используем условие, что вторая компонента пары (a, b) нулевая:

Q(a,b): b = 0

Теперь можно выписать алгоритм нахождения наибольшего общего делителя:

цел алгоритм НОД(вх: цел m, цел n) | дано: целые числа m, n, хотя бы одно отлично от нуля | надо: вычислить наибольший общий делитель пары (m, n) начало алгоритма | цел a, b, r; | // инициализация | a := m; b := n; | утверждение: НОД(a, b) == НОД(m, n); | | цикл пока b != 0 | | инвариант: НОД(a, b) == НОД(m, n) | | r := a % b; // находим остаток от деления a на b | | a := b; b := r; // заменяем пару (a, b) на (b, r) | конец цикла | | утверждение: b == 0 и НОД(a, b) == НОД(m, n); | ответ := a; конец алгоритма

Алгоритм Евклида - один из самых замечательных алгоритмов теории чисел и программирования. Работает он исключительно быстро, за время, линейно зависящее от длины записи входных чисел. (Действительно, легко показать, что за два выполнения тела цикла число b уменьшается не менее, чем в четыре раза. Следовательно, число выполнений тела цикла в худшем случае равно длине двоичной записи максимального из чисел a, b.) Это позволяет применять алгоритм Евклида к очень большим целым числам - например, к двухсотзначным десятичным. Алгоритм Евклида (более точно, расширенный алгоритм Евклида, который будет рассмотрен ниже) применяется для таких больших чисел в схеме кодирования с открытым ключом RSA, которая в настоящее время широко используется на практике для защиты информации.

Быстрое возведение в степень

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

Пусть требуется возвести элемент a в целую неотрицательную степень n. В качестве a может фигурировать целое или вещественное число, квадратная матрица, элемент кольца вычетов по модулю m и т.п. - требуется только, чтобы элемент a принадлежал алгебраической структуре, в которой определена ассоциативная операция умножения (т.е. в общем случае, a - элемент полугруппы).

Идея алгоритма состоит в том, чтобы возвести a в произвольную степень, применяя элементарные операции возведения в квадрат и умножения.

В качестве фазового пространства X этой задачи рассмотрим множество троек

X = {(b,k,p)}.

Здесь b выступает в роли текущего основания степени, k - в роли текущего показателя степени, p - это уже вычисленная часть степени. Ключевым моментом всегда является формулировка инварианта цикла:

I(b,k,p): bk*p = an = const,

т.е. величина bk*p постоянна и равна an. Легко подобрать начальные значения так, чтобы инвариант выполнялся:

b0 = a; k0 = n; p0 = 1. I(b0,k0,p0) = I(a,n,1): an*1 = an

Условие завершения совместно с выполнением инварианта должно обеспечить легкое решение требуемой задачи, т.е. вычисление an. Действительно, если k = 0, то из инварианта следует, что

b0*p = p = an,

т.е. искомая величина содержится в переменной p. Итак, условие завершения состоит в равенстве нулю числа k:

Q(b,k,p): k = 0

Осталось написать преобразование T точки x = (b,k,p), которое сохраняет инвариант и одновременно уменьшает k. Определим преобразование T следующим образом:

T(b,k,p) = (b*b, k/2, p), если k четное T(b,k,p) = (b, k-1, p*b), если k нечетное

Легко видеть, что инвариант сохраняется и k монотонно убывает. Итак, выпишем алгоритм быстрого возведения в степень для случая вещественного основания:

Нахождение корня функции методом деления отрезка пополам

Рассмотрим еще один пример использования схемы построения цикла с помощью инварианта, часто встречающийся в реальных программах. Пусть y = f(x) - непрерывная функция от вещественного аргумента, принимающая вещественные значения. Пусть известно, что на заданном отрезке [a,b] она принимает значения разных знаков. Из непрерывности функции f следует, что она имеет по крайней мере один корень на этом отрезке. Требуется вычислить корень функции f с заданной точностью ?.

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

Пусть концы текущего отрезка хранятся в переменных x0, x1. Инвариантом цикла является утверждение о том, что функция принимает значения разных знаков в точках x0, x1:

I(x0, x1): f(x0)*f(x1)

Начальные значения:

x0 = a, x1 = b

Условием завершения цикла является утверждение о том, что длина отрезка меньше ?:

Q(x0, x1): |x1-x0| < ?

(знак модуля используется потому, что в условии задачи не требуется выполнения неравенства a < b).

Выпишем алгоритм вычисления корня функции с заданной точностью:

Общая схема

Обозначим через X множество всевозможных наборов значений всех переменных, меняющихся в ходе выполнения цикла. Множество X иногда называют фазовым, или конфигурационным, пространством задачи. Инвариант - это некоторое условие I(x), зависящее от точки x из множества X и принимающее значение "истина" или "ложь". (Математики называют такие условия предикатами.) В процессе инициализации точке x присваивается такое значение x0, что условие I(x0) истинно.

Обозначим условие завершения цикла через Q(x). Условия I(x) и Q(x) должны быть подобраны таким образом, чтобы одновременная истинность I(x) и Q(x) обеспечивала решение требуемой задачи: нахождение точки x с требуемыми свойствами.

Тело цикла можно трактовать как отображение точки x в новую точку T(x) из того же множества X:

T:X

Условие I(x) является инвариантом для отображения T: если I(x), то I(T(x)) также истинно.

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

x := x0; // x0 выбирается так, чтобы условие // I(x0) было истинным утверждение: I(x);

цикл пока не Q(x) | инвариант: I(x); | x := T(x); // точка x преобразуется в T(x) конец цикла

утверждение: Q(x) и I(x); ответ := x;

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

Расширенный алгоритм Евклида

Один из важнейших результатов элементарной теории чисел утверждает, что наибольший общий делитель двух целых чисел выражается в виде их линейной комбинации с целыми коэффициентами. Пусть m и n - два целых числа, хотя бы одно из которых не равно нулю. Тогда их наибольший общий делитель d = НОД(m,n) выражается в виде

d = um+vn,

где u и v - некоторые целые числа. Результат этот очень важен для практики, т.к. позволяет вычислить обратный элемент к n в кольце вычетов по модулю m. Действительно, пусть числа m и n взаимно просты, т.е. НОД(m,n) = 1. Тогда

1 = um+vn,

откуда следует

vn = 1-um

1(mod m)

Нахождение обратного элемента в кольце вычетов Zm применяется во многих дискретных алгоритмах, например, в схеме кодирования с открытым ключом.

Для вычисления наибольшего общего делителя d и одновременно чисел u и v используется так называемый расширенный алгоритм Евклида. В обычном алгоритме Евклида пара чисел (a,b) в цикле заменяется на пару (b,r), где r - остаток от деления a на b, при этом наибольший общий делитель у обеих пар одинаковый. Начальные значения переменных a и b равны m и n соответственно. Алгоритм заканчивается, когда b становится равным нулю, при этом a будет содержать наибольший общий делитель.

Идея расширенного алгоритма Евклида заключается в том, что на любом шаге алгоритма хранятся коэффициенты, выражающие текущие числа a и b через исходные числа m и n. При замене пары (a,b) на пару (b,r) эти коэффициенты перевычисляются.

Итак, в алгоритме участвуют переменные a, b, u1, v1, u2, v2, для которых выполняется следующий инвариант цикла:

I(a, b, u1, v1, u2, v2): НОД(a,b) = НОД(m,n) a = u1m+v1n b = u2m+v2n

Начальные значения этих переменных обеспечивают выполнение инварианта:

a = m, b = n, u1 = 1, v1 = 0, u2 = 0, v2 = 1.

Условием завершения цикла, как и в обычном алгоритме Евклида, является равенство нулю переменной b:

Q(a, b, u1, v1, u2, v2): b = 0.

Осталось написать тело цикла, сохраняющее инвариант и уменьшающее абсолютную величину переменной b.
Это нетрудно сделать, исходя из инварианта цикла. В обычном алгоритме Евклида пара (a,b) заменяется на (b,r), где r - остаток от деления a на b.

a = gb+r, |r| < |b|.

Здесь g равняется целой части частного от деления a на b. Заметим, что в программировании, в отличие от школьной математики, операция взятия целой части перестановочна с операцией изменения знака:

целая часть(-x) = - целая часть(x)

Например, целая часть(-3.7) = -3. Это позволяет работать с отрицательными числами так же, как и с положительными, т.е. вообще не следить за знаком! Отметим также, что в большинстве языков программирования считается, что результат любой операции с целыми числами является целым числом, например, 8/3 = 2.

Переменная g вычисляется как целая часть частного от деления a на b:

g = целая часть (a/b)

Выразим остаток r в виде линейной комбинации a и b:

r = a-gb

Используя инвариант цикла, можно выразить r через исходные числа m и n:

r = a-gb = (u1m+v1n)-g(u2m+v2n) = = (u1-gu2)m+(v1-gv2)n.

Через u'1, v'1, u'2, v'2 обозначаются новые значения переменных u1, v1, u2, v2. При замене (a,b)

Вычисление логарифма без использования разложения в ряд

Схема построения цикла с помощью инварианта позволяет легко написать алгоритм вычисления логарифма заданного числа без использования разложения в ряд.

Пусть задано вещественное число x. Требуется вычислить логарифм числа x по основанию a c точностью ?, где ? - некоторое положительное очень маленькое число. Для определенности, пусть a>1 (для a<1 можно воспользоваться тождеством log1/ax = -logax).

Из определения логарифма следует, что надо найти число y такое, что

ay = x.

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

ayzt = x = const.

Таким образом, в цикле будут меняться три переменные

(y,z,t),

и инвариант записывается в виде

I(y,z,t): ayzt = x

Начальные значения переменных y, z, t выбираются так, чтобы выполнялся инвариант:

y0 = 0, z0 = x, t0 = 1.

Определим условие завершения цикла Q(y,z,t). Необходимо, чтобы искомая величина по окончанию цикла содержалась в переменной y. Следовательно, величина zt должна быть близка к единице: тогда приблизительно выполняется равенство

ayzt = x

т.е. y приближенно равен искомому логарифму. Для того, чтобы величина zt была близка к единице, нужно, чтобы показатель степени t был близок к нулю, а основание z было не очень велико и не очень мало. Для этого достаточно выполнения трех неравенств

|t| < ?, 1/a < z < a

Можно доказать строго, что при выполнении этих неравенств, а также условия ayzt = x, величина y отличается от logax не больше чем на ?.

Выполнение этих трех неравенств и являются условием завершения цикла:

Q(y,z,t): |t| < ? и 1/a < z и z < a

Наконец, тело цикла должно преобразовывать переменные (y,z,t) так, чтобы абсолютная величина t монотонно убывала, а переменная z рано или поздно попадала бы в интервал (1/a,a), и при этом сохранялся инвариант. Такое преобразование T легко выписывается по инварианту цикла:

T(y,z,t) = (y+t, z/a, t), если z

a T(y,z,t) = (y-t, z*a, t), если z

1/a T(y,z,t) = (y, z*z, t/2), если 1/a < z < a

Заметим, что при применении преобразования T некоторая величина как бы перетекает из одних переменных в другие, при этом равенство ayzt = x остается неизменным.

Теперь можно выписать алгоритм вычисления логарифма:

Алгоритм работы компьютера

Среди всех регистров процессора в любой архитектуре всегда имеется два выделенных регистра: это регистр PC, что означает Program Counter, по-русски его называют счетчиком команд, и регистр SP — Stack Pointer, т.е. указатель стека. Иногда регистр PC обозначают как IP, что означает Instruction Pointer, указатель инструкции. (Команды процессора часто называют инструкциями.)

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

цикл до бесконечности выполнять | прочесть команду с адресом PC из оперативной памяти; | увеличить содержимое PC на длину прочитанной команды; | выполнить прочитанную команду; конец цикла

В простейшем случае, когда выполняется линейный участок программы, команды выбираются из памяти и выполняются последовательно, а содержимое регистра PC монотонно возрастает. Выполнение команды, однако, может приводить к изменению регистра PC. Таким образом организуются безусловные и условные переходы в программе, нарушающие последовательный порядок выполнения команд. С помощью команд условных и безусловных переходов реализуются конструкции ветвления и цикла. Команда перехода представляет собой либо прибавление константы к содержимому PC (константа может быть положительной или отрицательной), либо загрузку в PC адреса элемента памяти со всеми возможными режимами адресации. Первый способ используется для реализации переходов внутри подпрограммы (внутри функции в терминах языка Си), второй -- для перехода к подпрограмме. Впрочем, гораздо чаще в последнем случае используется команда call вызова подпрограммы, которая дополнительно запоминает точку возврата в регистре или в аппаратном стеке.

Аппаратный стек

Стек - это запоминающее устройство, из которого элементы извлекаются в порядке, обратном их помещению в стек. Стек можно представить как стопку листов бумаги, на каждом из которых записан один из сохраняемых элементов. На вершине стека находится последний запомненный элемент.

Стек можно представить в виде трубки с подпружиненым дном, расположеной вертикально. Верхний конец трубки открыт, в него можно добавлять, или, как говорят, заталкивать элементы. Общепринятые английские термины в этом плане очень красочны, операция добавления элемента в стек обозначается push, в переводе "затолкнуть, запихнуть". Новый добавляемый элемент проталкивает элементы, помещеные в стек ранее, на одну позицию вниз. При извлечении элементов из стека они как бы выталкиваются вверх, по-английски pop ("выстреливают").

Аппаратный стек реализуется на базе оперативной памяти. Элементы стека расположены в оперативной памяти, каждый из них занимает одно слово. Регистр SP в любой момент времени хранит адрес элемента в вершине стека. Стек растет в сторону уменьшения адресов: элемент, расположенный непосредственно под вершиной стека, имеет адрес SP + 4 (при условии, что размер слова равен четырем байтам), следующий SP + 8 и т.д.

Оперативная память

адрес	содержимое
0
4
8
...	...
SP	элементы	<=вершина стека
SP+4	стека
SP+8
...	...
232-4

Поскольку регистр SP содержит адрес машинного слова, его значение всегда кратно четырем. При помещении элемента x в стек значение SP сначала уменьшается на 4, затем x записывается в слово оперативной памяти с адресом SP. При извлечении элемента из стека сначала слово с адресом SP копируется в выходную переменную x, затем значение SP, т.е. адрес вершины стека, увеличивается на 4. Обычно команда добавления в стек обозначается словом push, команда извлечения из стека — словом pop:

push X ~ SP := SP ? 4; m [SP] := X; pop X ~ X := m [SP] ; SP := SP + 4;

Здесь через m[SP] обозначается содержимое слова памяти с адресом SP (m - сокращение от memory).

Аппаратный стек и локальные переменные подпрограммы

Поскольку аппаратный стек располагается в оперативной памяти, в нем можно размещать обычные переменные программы. Размещение локальных переменных в стеке обладает рядом преимуществ по сравнению со статическим размещением переменных в фиксированных ячейках оперативной памяти. Как уже говорилось выше, это позволяет организовывать рекурсию. Кроме того, в современных архитектурах принципиальное значение имеет поддержка параллельных процессов, работающих над общими статическими переменными. Это так называемые легковесные процессы, или нити (Thread), работающие параллельно в рамках одной программы. На использовании нитей, например, основана работа всех графических приложений в системе Microsoft Windows 32: одна нить обрабатывает сообщения графической системы (нажатия на клавиатуру и кнопки мыши, перерисовка окон, выборка команд из меню и т.п.), другие нити занимаются вычислениями, сетевым обменом, анимацией и т.п.

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

Рассмотрим более подробно, как размещаются локальные переменные подпрограммы в стеке, на примере языка Си. В Си подпрограммы называются функциями. Функция может иметь аргументы и локальные переменные, т.е.
переменные, существующие только в процессе выполнения функции. Рассмотрим для примера функцию ?, зависящую от двух входных аргументов x и y целого типа, в которой используются три локальные переменные a, b и c также целого типа. Функция возвращает целое значение.

int f(int x, int y) { int a, b, c; ... }

Пусть в некотором месте программы вызывается функция ? с аргументами x = 222, y = 333:

z = f(222, 333);

Вызывающая программа помещает фактические значения аргументов x и y функции ? в стек, при этом на вершине стека лежит первый аргумент функции, под ним — второй аргумент. Вызов функции транслируется в следующие команды:

push 333 push 222 call ?

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

В момент начала работы функции ? cтек имеет следующий вид:

адрес возврата	<=SP
222
333
....

На вершине стека лежит адрес возврата, под ним — фактическое значение аргумента x, затем фактическое значение аргумента y.

Перед началом работы функция ? должна захватить в стеке область памяти под свои локальные переменные a, b, c. В языке Си принято следующее соглашение: адрес блока локальных переменных функции в момент ее работы помещается в специальный регистр процессора, который называется FP, от англ. Frame Pointer — указатель кадра. (В процессоре Intel 80386 роль указателя кадра выполняет регистр EBP.) В первую очередь функция ? сохраняет в стеке предыдущее значение регистра FP. Затем значение указателя стека копируется в регистр FP. После этого функция ? захватывает в стеке область памяти размером в 3 машинных слова под свои локальные переменные a, b, c. Для этого функция ? просто уменьшает значение регистра SP на 12 (три машинных слова равны двенадцати байтам). Таким образом, начало функции ? состоит из следующих команд:

push FP FP := SP SP := SP ? 12

После захвата кадра локальных переменных стек выглядит следующим образом.

c	<=SP
b
a
старое значение FP	<=FP
адрес возврата
x=222
y=333
...

Аргументы и локальные переменные функции ? адресуются относительно регистра FP. Так, аргумент x имеет адрес FP+8, аргумент y - адрес FP+12. Переменная a имеет адрес FP-4, переменная b - адрес FP-8, переменная c - адрес FP-12.

По окончании работы функция ? сначала увеличивает указатель стека на 12, удаляя таким образом из стека свои локальные переменные a, b, c. Затем старое значение FP извлекается из стека и помещается в FP (таким образом, регистр FP восстанавливает свое значение до вызова функции ?). После этого осуществляется возврат в вызывающую программу: адрес возврата снимается со стека и управление передается по адресу возврата. Результат функции ? передается через нулевой регистр.

R0 := результат функции SP := SP +12 pop FP return

Вызывающая программа удаляет из стека фактические значения аргументов x и y, помещенные в стек перед вызовом функции ?.

CISC и RISC-процессоры

Существует два подхода к конструированию процессоров. Первый состоит в том, чтобы придумать как можно больше разных команд и предусмотреть как можно больше разных режимов адресации. Процессоры такого типа называются CISC-процессорами, от слов Сomplex Instruction Set Computers. Это, в частности, Intel 80x86 и Motorola 68000. Противоположный подход состоит в том, чтобы реализовать лишь минимальное множество команд и режимов адресации, процессоры такого типа называются RISC-процессорами, от слов Reduced Instruction Set Computers. Примеры RISC-процессоров: DEC Alpha, Power PC, Intel Itanium.

Казалось бы, CISC-процессоры должны иметь преимущество перед RISC-процессорами, но на самом деле все обстоит строго наоборот. Дело в том, что простота набора команд процессора облегчает его конструирование, в результате чего удается достичь следующих целей:

все команды выполняются исключительно быстро, причем за одинаковое время, т.е. за фиксированное число тактов работы процессора; значительно поднимается тактовая частота процессора; намного увеличивается количество регистров процессора и объем кеш-памяти; удается добиться ортогональности режимов адресации, набора команд и набора регистров. Это означает, что нет каких-либо выделенных регистров или режимов адресации: в любых (или почти любых) командах можно использовать произвольные регистры и режимы адресации независимо друг от друга. Следует отметить, что к памяти могут обращаться лишь команды загрузки слова из памяти в регистр и записи из регистра в память, а все арифметические команды работают только с регистрами; простота команд позволяет эффективно организовать их выполнение в конвейере (pipeline), что значительно ускоряет работу программы.

Пункты 3 и 4 по достоинству оценят те, кому пришлось программировать на Ассемблере Intel 80x86, имеющем ряд ограничений на использование регистров и режимы адресации, к тому же и регистров в нем очень мало.

RISC-архитектуры обладают неоспоримыми преимуществами по сравнению с CISC-архитектурами — быстродействием, низкой стоимостью, удобством программирования и т.д. — и практически не имеют недостатков. Существование CISC-процессоров в большинстве случаев объясняется лишь традицией и требованием совместимости со старым программным обеспечением. Впрочем, существует и третий вариант — процессоры, которые по сути являются RISC-процессорами, но эмулируют внешнюю систему команд устаревших процессоров, например, современные процессоры Intel Pentium.

Команды вызова подпрограммы call и возврата return

Одно из главных назначений аппаратного стека — поддержка вызовов подпрограмм. При вызове подпрограммы надо сохранить адрес возврата, чтобы подпрограмма могла по окончанию своей работы вернуть управление вызвавшей ее программе. В старых архитектурах, в которых аппаратный стек отсутствовал (например, в компьютерах IBM 360/370), точки возврата сохранялись в фиксированных ячейках памяти для каждой подпрограммы. Это делало невозможной рекурсию, т.е. повторный вызов той же подпрограммы непосредственно из ее текста или через цепочку промежуточных вызовов, поскольку при повторном вызове старое содержимое ячейки, хранившей адрес возврата, терялось

Во всех современных архитектурах точка возврата сохраняется в аппаратном стеке, что делает возможным рекурсию, а также параллельное выполнение нескольких легковесных процессов (нитей). Для вызова подпрограммы ? служит команда call, которая осуществляет переход к подпрограмме ? (т.е. присваивает регистру PC адрес ?) и одновременно помещает старое содержимое регистра PC в стек:

call ? ~ push PC; PC:= ?;

В момент выполнения любой команды регистр PC содержит адрес следующей команды, т.е. фактически адрес возврата из подпрограммы ?. Таким образом, команда call сохраняет в стеке точку возврата и осуществляет переход к подпрограмме ?.

Для возврата из подпрограммы используется команда return. Она извлекает из стека адрес возврата и помещает его в регистр PC:

return ~ pop PC;

Оперативная память

Элементарной единицей памяти всех современных компьютеров является байт, состоящий из восьми двоичных разрядов. Каждый байт имеет свой адрес. В наиболее распространенной 32-разрядной архитектуре адреса байтов изменяются от 0 до 232 - 1 с шагом 1. Память, с логической точки зрения, можно рассматривать как массив байтов: можно прочесть или записать байт с заданным адресом. Содержимое байта трактуется либо как неотрицательное целое число в диапазоне от 0 до 255, либо как число со знаком в диапазоне от -128 до 127. (На самом деле байт — это элемент кольца вычетов по модулю 256)

Однако физически при работе с памятью по шине передаются не отдельные байты, а машинные слова. В 32-разрядной архитектуре машинное слово — это четыре подряд идущих байта, при этом адрес младшего байта кратен четырем. (В 64-разрядной архитектуре машинное слово состоит из восьми байтов.) Машинное слово — это наиболее естественный элемент данных для процессора. Машинное слово содержит целое число, которое можно рассматривать либо как беззнаковое в диапазоне от 0 до 232 - 1, либо как знаковое в диапазоне от -2 31 до 231 - 1. Адрес памяти также представляет собой машинное слово.

Принято нумеровать биты внутри машинного слова (как и внутри байта) справа налево, начиная с нуля и кончая 31. Младший бит имеет нулевой номер, старший, или знаковый, бит — номер 31 . Младшие биты числа находятся в младших битах машинного слова.

Существуют два способа нумеровать байты внутри машинного слова. В соответствии с этим все процессоры разделяются на два типа:

Big Endian - байты внутри машинного слова нумеруются слева направо. Таковы процессоры Motorola, Power PC. Байты в архитектуре Big Endian удобно представлять записанными слева направо. При этом старшие биты целого числа располагаются в байте с младшим адресом. Little Endian - байты внутри машинного слова нумеруются справа налево. Таковы процессоры Intel 80x86, Alpha, VAX и др. Байты в архитектуре Little Endian следует представлять записанными справа налево.
При этом старшие биты целого числа располагаются в байте со старшим адресом.

Архитектура Big Endian была популярна в середине XX века. К концу 70-х годов программисты осознали, что Little Endian-архитектура гораздо удобнее. Например, один из аргументов в пользу Little Endian заключается в том, что целое число, занимающее машинное слово с адресом n, и байт с тем же адресом содержат одно и то же значение (конечно, если оно не превышает 255). В случае Big Endian это не так: например, если целое число с адресом n содержит число 17, то байт с адресом n содержит 0; или если целое число содержит отрицательное значение -77, то байт с адресом n содержит отрицательное значение -1. При небрежном программировании это порождает массу ошибок. Поэтому большинство современных процессоров построены по архитектуре Little Endian.

Тем не менее многие компьютерные протоколы ориентируются на Big Endian, поскольку они были приняты достаточно давно. Например, все протоколы сети Internet передают данные в формате Big Endian, т.к. они были разработаны в 70-х годах XX века. На машинах с архитектурой Little Endian приходится переставлять байты внутри слова перед отправкой IP-пакета в сеть или при получении IP-пакета из сети.

Процессор

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

Рассмотрим лишь самые общие принципы построения и работы процессора, которые одинаковы как для примитивных, так и для самых современных процессоров.

Любой процессор имеет устройство, выполняющее команды, и собственную внутреннюю память, реализованную внутри микросхемы процессора. Она называется регистрами процессора. Имеется 3 типа регистров:

общие регистры хранят целые числа или адреса. Размер общего регистра совпадает с размером машинного слова и в 32-разрядной архитектуре равен четырем байтам. Число общих регистров и их назначение зависит от конкретного процессора. В большинстве Ассемблеров к ним можно обращаться по именам R0, R1, R2, ...Среди общих регистров имеются регистры специального назначения: указатель стека SP (Stack Pointer), счетчик команд PC (Program Counter) и др.;

регистр флагов содержит биты, которые устанавливаются в единицу или в ноль в зависимости от результата выполнения последней команды. Так, бит Z устанавливается в единицу, если результат равен нулю (Zero), бит N — если результат отрицательный (Negative), бит V — если произошло переполнение (oVerflow), бит С - если произошел перенос единицы из старшего или младшего разряда (Carry), например, при сложении двух целых чисел или при сдвиге. Значения битов в регистре флагов используются в командах условных переходов;

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

Команды, или инструкции, процессора состоят из кода операции и операндов. Команда может вообще не иметь операндов или иметь один, два, три операнда. Команды с числом операндов большим трех встречаются лишь в процессорах специального назначения (служащих, например, для обработки сигналов) и в обычных архитектурах не используются. Чаще всего применяются двухадресные и трехадресные архитектуры: к двухадресным относятся, к примеру, все процессоры серии Intel 80x86, к трехадресным — серии Motorola 68000. В двухадресной архитектуре команда сложения выглядит следующим образом:

add X, Y

что означает

X := X + Y,

т.е. один из аргументов команды является одновременно и ее результатом. Этот аргумент называется получателем (destination). Аргумент, который не меняется в результате выполнения команды, называется источником (source). Среди программистов нет единого мнения о том, в каком порядке записывать аргументы при использовании Ассемблера, т.е. в символической записи машинных команд. Например, в Ассемблере "masm" фирмы IBM для процессоров Intel 80x86 получатель всегда записывается первым, а источник вторым. Ассемблер "masm" используется в операционных системах MS DOS и Windows. В Ассемблере "as", который входит в состав компилятора "gcc" и используется в системах типа Unix (Linux и т.п.), получатель всегда является последним аргументом. Та же команда сложения записывается в "as" как

add Y, X

что означает сложить Y и X и результат записать в X.

В трехадресной архитектуре команда сложения имеет 3 операнда:

add X, Y, Z

Получателем в трехадресной архитектуре обычно является третий аргумент, т.е. в данном случае сумма X+Y записывается в Z.

Операндами команды могут быть регистры или элементы памяти. В действительности, конечно, процессор всегда сначала копирует слово из памяти в регистр, который может быть либо явно указан в команде, либо использоваться неявно.

Операция всегда выполняется с содержимым регистров. После этого результат может быть записан в память либо оставлен в регистре. Например, при выполнении команды увеличения целого числа на единицу

inc X

в случае, когда операнд X является словом оперативной памяти, содержимое слова X сначала неявно копируется во внутренний регистр процессора, затем выполняется его увеличение на единицу, и после этого увеличенное значение записывается обратно в память.

Имеется несколько способов задания операнда, находящегося в оперативной памяти, они называются режимами адресации. Это

абсолютная адресация - когда в команде указывается константа, равная адресу аргумента;

косвенная адресация - когда в команде указывается регистр, содержащий адрес аргумента;

относительная адресация - адрес аргумента равен сумме содержимого регистра и константы, задающей смещение;

индексная адресация с масштабированием - адрес аргумента равен сумме содержимого базового регистра, константы, задающей смещение, а также содержимого индексного регистра, умноженного на масштабирующий множитель. Масштабирующий множитель может принимать значения 1, 2, 4, 8. Этот режим удобен для обращения к элементу массива.

Бывают и другие, более изощренные, режимы адресации, когда, например, адрес аргумента содержится в слове, адрес которого содержится в регистре (так называемая двойная косвенность).

Устройство компьютера

Компьютер - это универсальный исполнитель, который умеет управлять другими исполнителями и обладает собственной внутренней памятью. Запись алгоритма для компьютера называется программой. Все современные компьютеры построены по так называемой фон-Неймановской архитектуре: программа хранится в памяти компьютера, так же как и данные.

Компьютер построен из следующих составных частей:

процессор - это основа любого компьютера, его мозг. Процессор производит все вычисления и отдает команды всем остальным компонентам компьютера;оперативная память также является обязательной составной частью любого компьютера. Оперативная память (RAM - Random Access Memory) хранит как программу, так и данные (т.е. значения переменных). Часть памяти может быть защищена от записи и хранится в специальной микросхеме (ПЗУ - постоянное запоминающее устройство или ROM - Read Only Memory). Обычно в ПЗУ лежит программа первоначальной загрузки и базовая система ввода-вывода (BIOS);шина - это канал передачи команд и данных между всеми составными частями компьютера. В компьютере могут быть одна или несколько шин. Все устройства подключаются к шине параллельно, т.е. порядок подключения не важен, а количество проводов не зависит от количества подключенных устройств. Порядок передачи команд и данных определяется протоколом работы шины, т.е. четко описанным набором соглашений, принятым, как правило, в виде международного стандарта. Каждое устройство подключается к шине с помощью контроллера, который осуществляет перевод с языка сигналов, передаваемых по шине, на язык команд конкретного устройства;внешние устройства подключаются к шине компьютера. Наиболее распространенные внешние устройства - это жесткий диск, клавиатура, монитор, сетевая карта, модем и т.п. Ни одно из них не является обязательным, как показывает пример компьютера, управляющего автомобильным двигателем со впрыском топлива. Но какие-то внешние устройства всегда присутствуют, поскольку через них осуществляется связь компьютера с внешним миром.

Рассмотрим каждую из составляющих частей компьютера более подробно.

Переключение между процессами и нитями

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

В современных операционных системах различают понятия процесса и нити (thread). В рамках одного процесса могут существовать несколько нитей. Все нити одного процесса разделяют одно и то же виртуальное адресное пространство, соответствующее статическим и глобальным переменным программы. Однако стек, стековая (локальная) память и наборы значений регистров у каждой нити свои.

Каждая нить выполняется по отдельности, поэтому нити иногда называют легковесными процессами (light-weight process). Переключение между нитями происходит аналогично переключению между процессами. Нити очень удобны в программировании, поскольку разные нити параллельно выполняют совместную работу над одними и теми же глобальными переменными, расположенными в статической памяти процесса. Это позволяет избежать сложных механизмов передачи данных между различными процессами, которые приходилось использовать в старых операционных системах до изобретения нитей. На использовании нитей основано, например, программирование графических задач в операционных системах типа Windows. Здесь одна нить отвечает за обработку действий пользователя и поддержку оконного интерфейса (нажатий на мышь, клавиатуру, перерисовку окон и т.п.). Другие нити могут выполнять вычислительную работу и сетевой обмен, поддерживать анимацию и т.п. Выполнять вычислительную работу внутри нити, отвечающей за графический интерфейс, нельзя, потому что длительные вычисления приводят к визуальному подвисанию программы и к замедленным реакциям на действия пользователя.

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

Для защиты критических данных используется объект синхронизации типа мьютекс, от англ. MUTual EXclusive -- взаимно исключающий. Нить перед обращением к критическим данным пытается захватить мьютекс, соответствующий этим данным. Если он уже захвачен, то операционная система приостанавливает нить до тех пор, пока объект не будет освобожден. После этого мьютекс передается нити, нить пробуждается и выполняет необходимые действия. По завершении критических действий нить сама должна освободить мьютекс, подобно тому как машинист поезда должен сам оставить маркерное кольцо на станции после проезда участка пути, ``защищенного'' этим кольцом.

Рассмотрим несколько простых примеров программ

Рассмотрим несколько простых примеров программ на "виртуальном Ассемблере" RTL и на конкретном Ассемблере для процессора Intel 80x86.

RTL: машинно-независимый Ассемблер

Каждый процессор имеет свои специфические команды, наборы регистров и режимы адресации, поэтому программу на Ассемблере невозможно перенести с одной аппаратной платформы на другую. Для того чтобы не зависеть от конкретного процессора, часто используют язык описания команд RTL, от англ. Register Transfer Language — язык перемещения регистров. Фактически RTL представляет собой Ассемблер, не зависящий от конкретного процессора. Многие компиляторы, например, gcc, не переводят программу с языка высокого уровня сразу на язык машинных команд, а сначала транслируют ее на язык RTL. Затем на уровне RTL выполняется оптимизация кода, которая составляет 99% работы компилятора. И лишь на последнем этапе программа c языка RTL переводится на язык команд конкретного процессора. Поскольку RTL максимально приближен к Ассемблеру, трансляция из RTL в конкретный Ассемблер не представляет никакого труда.

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

Мы будем использовать RTL для записи примеров несложных программ в кодах вместо какого-либо конкретного Ассемблера.

В RTL имеется неограниченное число регистров общего назначения

R0, R1, R2, R3, ...

и несколько выделенных регистров:

счетчик команд PC; указатель стека SP; регистр флагов CC0 (от слов Conditional Codes), иногда добавляют также дополнительные регистры флагов CC1, CC2, ...; указатель кадра FP.

Слово памяти с адресом a обозначается в RTL через m[a]. Выражение a может быть константой, регистром или суммой регистра и константы, что соответствует абсолютному, косвенному и относительному режимам адресации. Примеры:

m[1000]; m[R0]; m[FP ? 4].

Байт с адресом a обозначается через mb[a], короткое (двухбайтовое) слово — через ms[a].

Арифметические команды, такие, как сложение или умножение, записываются в RTL в естественном виде, например, команда сложения двух регистров R0 и R1, помещающая результат в R2, записывается в RTL в виде

R2 := R0 +R1

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

L: . . . goto L;

Ветвление в RTL реализуется с помощью команд условного перехода, которые в зависимости от состояния различных битов или их комбинаций в регистре флагов CC0 либо осуществляют переход на указанную метку, либо ничего на делают. Например, команда

if (eq) goto L;

осуществляет переход на метку L в случае, когда результат предыдущей команды равен нулю (eq — от слова equal), т.е. в регистре CC0 установлен бит z (от слова zero). Большинство арифметических команд автоматически устанавливают биты-признаки результата в регистре флагов CC0. Очень часто требуется просто сравнить два числа, никуда не записывая результат. Команда сравнения присутствуют в системе команд любого процессора, чаще всего она называется cmp (от слова compare). Логически команду сравнения следует понимать как вычитание двух чисел, при этом результат как бы помещается в регистр флагов. На самом деле, в регистре флагов от результата остаются лишь биты-признаки (равен ли он нулю, больше нуля и т.п.). В RTL команда сравнения двух регистров R0 и R1 записывается следующим образом:

CC0 := R0 ? R1;

Результат как бы помещается в регистр флагов CC0.

В командах условного перехода, таких как

if (eq) goto L;

можно использовать следующие условия:

eq результат равен нулю (equal) ne результат не равен нулю (not equal) g результат больше нуля (greater) l результат меньше нуля (less) ge результат больше или равен нулю (greater or equal) le результат меньше или равен нулю (less or equal)

Перечисленные сравнения используются для чисел со знаком. Для неотрицательных чисел (например, в случае сравнения адресов памяти) вместо слов "больше" и "меньше" используются слова "выше" и "ниже" (above и below):

a первое число выше второго (above) b первое число ниже второго (below) ae первое число выше или равно второму (above or equal) be первое число ниже или равно второму (below or equal)

Приведем простой пример реализации конструкции "если":

если R0 == R1 l то R2 := 77; конец если

На RTL этот фрагмент реализуется так:

СС0 := R0 - R1; if (ne) goto L; R2 := 77; L:

Отметим, что в команде условного перехода используется отрицание условия после слова "если", т.е. фактически условие обхода фрагмента кода после слова "то".

Страничная организация памяти

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

Для отображения виртуальной памяти на физическую используется механизм страничной организации памяти. Вся физическая память делится на страницы, обычный размер страницы -- 4096 байтов (4 килобайта). Для каждой задачи выделяется специальная область памяти, в которой записаны адреса физических страниц, соответствующих виртуальным страницам. Адрес этой области содержится в специальном регистре процессора. Когда программа обращается к некоторому виртуальному адресу, то он делится на 4096, таким образом определяется номер виртуальной страницы. Затем адрес физической страницы, соответствующий данному номеру, извлекается из специальной области памяти, хранящей физические адреса виртуальных страниц. После этого к вычисленному таким образом адресу физической страницы прибавляется смещение внутри страницы, т.е. остаток от деления виртуального адреса на 4096 (на размер страницы).

Таким образом, разные задачи работают с одними и теми же виртуальными адресами, но с разными физическими адресами, не мешая друг другу.

Отметим еще один очень важный аспект виртуальной памяти. Объем физической памяти может быть меньше, чем объем виртуальной памяти. В этом случае используется механизм своппинга, т.е. вытеснения страниц физической памяти на диск. Считается, что объем пространства на диске компьютера практически бесконечен. Поэтому при нехватке физической памяти страницу виртуальной памяти можно разместить на диске. При обращении к этой странице операционная система сначала загружает ее с диска в физическую память. При этом, возможно, какая-то другая страница вытесняется на диск, чтобы освободить место. Отсюда и слово своппинг (swapping), что в переводе означает ``обмен''. Загрузка виртуальной страницы с диска происходит в результате синхронного прерывания в связи с отсутствием физической страницы в памяти.

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

Суммирование массива

Рассмотрим еще один простой пример программы на Ассемблере. Требуется вычислить сумму элементов целочисленного массива заданной длины. Прототип этой функции на языке Си выглядит следующим образом:

int sum(int a[], int n);

Функции передается (как обычно, через аппаратный стек) адрес начала целочисленного массива a и его длина n. На RTL функция sum записывается следующим образом:

// Вход в функцию: push FP; // сохраним старое значение FP; FP := SP; // определим новое значение FP; push R1; // сохраним значения регистров R1, push R2; // R2 push R3; // и R3. // R0 := 0; // обнулим сумму R1 := m[FP+8]; // R1 := a (адрес начала массива) R2 := m[FP+12]; // R2 := n (число эл-тов массива) L1: // метка начала цикла CC0 := R2 - 0; // сравнить R2 с нулем if (le) goto L2; // если результат ‹ = 0, // то перейти на метку L2 R3 := m[R1]; // R3 := очередной элемент массива R0 := R0 + R3; // прибавим очередной эл-т к сумме R1 := R1 + 4; // увеличим адрес очер. эл-та на 4 R2 := R2 - 1; // уменьшим счетчик необр. эл-тов goto L1 // перейти на метку L1 L2: // метка конца цикла // ответ уже содержится в R0 // выход из функции: pop R3; // восстановим значения R3, pop R2; // R2 pop R1; // и R1 pop FP; // восстановим старое значение FP return; // вернемся в вызывающую программу

В этой программе адрес очередного элемента массива содержится в регистре R1. Сумма просмотренных элементов массива накапливается в регистре R0. Регистр R2 содержит число еще не обработанных элементов массива. В начале программы в регистр R1 записывается адрес начала массива, а в R2—число элементов массива. В теле цикла очередной элемент массива читается из памяти и помещается в регистр R3, затем содержимое R3 прибавляется к сумме R0. После каждого выполнения тела цикла адрес очередного элемента увеличивается на 4 (т.к. целое число занимает 4 байта), а количество необработанных элементов уменьшается на единицу. Цикл продолжается, пока содержимое регистра R2 (т.е. число необработанных элементов) больше нуля.

Для переписывания программы на Ассемблер Intel 80386 зафиксируем следующее распределение виртуальных регистров:

R0 — EAX R1 — EBX R2 — ECX R3 — EDX FP — EBP SP — ESP

Программа переписывается таким образом:

.386 .model flat, stdcall .code

sum: ; Вход в функцию: push EBP ; сохраним старое значение EBP mov EBP, ESP ; определим новое значение EBP push EBX ; сохраним значения регистров EBX, push ECX ; ECX push EDX ; и EDX. ; mov EAX, 0 ; EAX := 0 mov EBX, [EBP+8] ; EAX := a mov ECX, [EBP+12]; ECX := n L1: ; метка начала цикла cmp ECX, 0 ; сравнить ECX с нулем jle L2 ; если результат ‹ = 0, ; то перейти на метку L2 mov EDX, [EBX] ; EDX := очередной эл-т массива add EAX, EDX ; EAX := EAX+EDX add EBX, 4 ; EBX := EBX+4 (адрес след. эл-та) dec ECX ; ECX := ECX-1 (счетчик) jmp L1 ; перейти на метку L1 L2: ; метка конца цикла ; ответ содержится в регистре EAX ; выход из функции: pop EDX ; восстановим значения EDX, pop ECX ; ECX pop EBX ; и EBX. pop EBP ; восстановим значение EBP ret ; вернемся в вызывающую программу

public sum end

Отметим, что мы использовали команду уменьшения значения регистра на единицу dec (от слова decrement) для реализации следующей строки RTL:

R2 := R2 - 1; // уменьшим счетчик необр. эл-тов

В Ассемблере Intel 80386 она записывается как

dec ECX; ECX := ECX-1

Команда увеличения регистра на единицу обычно записывается как inc (от слова increment). Эти команды, как правило, присутствуют в наборе инструкций любого процессора.

Виртуальная память и поддержка параллельных задач

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

Внешние устройства и аппаратные прерывания

Согласно рассмотренному ранее алгоритму работы компьютера, процессор в любой момент времени выполняет команду, адрес которой находится в регистре PC. После чтения команды из оперативной памяти содержимое PC увеличивается на длину прочитанной команды. Затем команда выполняется, читается следующая команда, и все это повторяется в бесконечном цикле. Однако предусмотрена возможность нарушения этого бесконечного цикла. Она продиктована необходимостью реагировать на события, связанные с внешними устройствами компьютера.

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

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

Получив по шине сигнал прерывания, процессор прерывает текущую работу и переключается на обработку прерывания.

Вычисление наибольшего общего делителя

Реализуем функцию, вычисляющую наибольший общий делитель двух целых чисел. Мы уже записывали алгоритм вычисления НОД на псевдокоде. На языке Си эта функция выглядит следующим образом:

int gcd(int x, int y) { // цел алг. gcd(цел x, цел y) int a, b, r; // | цел a, b, r; a = x; b = y; // | a := x; b := y; while (b != 0) { // | цикл пока b != 0 r = a % b; // | | r := a % b; a = b; // | | a := b; b = r; // | | b := r; } // | конец цикла return a; // | ответ := a; } // конец алгоритма

Вместо НОД мы назвали функцию "gcd" (от слов greatest common divizor), поскольку в языке Си русские буквы в именах функций и переменных использовать нельзя. Запишем эту программу на языке RTL. Переменные a, b, r мы будем хранить в регистрах R0, R1, R2.

// Вход в функцию: push FP; // сохраним значение FP в стеке; FP := SP; // определим новое значение FP; push R1; // сохраним значения регистров R1 push R2; // и R2 // R0 := m[FP+8]; // a := x; R1 := m[FP+12]; // b := y; L1: // метка начала цикла CC0 := R1 - 0; // сравнить b с нулем if (eq) goto L2; // если результат равен нулю, // то перейти на метку L2 R2 := R0 % R1; // r := a % b; R0 := R1; // a := b; R1 := R2; // b := r; goto L1 // перейти на метку L1 L2: // метка конца цикла // ответ уже содержится в R0 // выход из функции: pop R2; // восстановим значения R2 pop R1; // и R1 pop FP; // восстановим значение FP return; // вернемся в вызывающую программу

Эту программу можно переписать на конкретный Ассемблер, например, на Ассемблер "Masm" фирмы Microsoft для процессоров Intel 80x86. Первое, что надо сделать при переводе с RTL на Ассемблер — это распределить регистры, т.е. задать отображение виртуальных регистров R0, R1, ... на конкретные регистры данного процессора. У процессоров серии Intel 80x86 есть всего 8 общих регистров: это регистры

EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP.

Процессор Intel сконструирован таким образом, что каждый регистр выполняет в определенных командах свою особую роль (Intel 80x86 — это CISC-процессор; в RISC-процессорах все регистры равноправны).
В частности, команда деления всегда использует в качестве делимого длинное восьмибайтовое целое число, содержащееся в паре регистров (EDX, EAX), где старшие байты в регистре EDX. В результате выполнения команды деления вычисляется как частное, так и остаток от деления: частное помещается в регистр EAX, остаток — в регистр EDX.

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

R0 — EAX R1 — EBX R2 — EDX FP — EBP SP — ESP

После того как распределены регистры, остается только переписать каждую строку RTL программы на конкретный Ассемблер. Для этого необходимо знать ограниченный набор команд, реализующих операции языка RTL в конкретном Ассемблере. Например, в нашем случае операция пересылки из одного регистра в другой или из памяти в регистр реализуется командой mov, операция деления реализуется командой div и т.д. Программа на языке Ассемблера Intel 80386 записывается следующим образом:

.386 .model flat, stdcall .code

gcd: ; Вход в функцию: push EBP ; сохраним старое значение EBP mov EBP, ESP ; определим новое значение EBP push EBX ; сохраним значения EBX push EDX ; и EDX. ; mov EAX, [EBP+8] ; EAX := x mov EBX, [EBP+12] ; EBX := y L1: ; метка начала цикла cmp EBX, 0 ; сравнить EBX с нулем je L2 ; если результат равен нулю, ; то перейти на метку L2 mov EDX, 0 ; div EBX ; EDX := EAX % EBX mov EAX, EBX ; EAX := EBX mov EBX, EDX ; EBX := EDX jmp L1 ; перейти на метку L1 L2: ; метка конца цикла ; ответ уже содержится в EAX ; выход из функции: pop EDX ; восстановим значения EDX pop EBX ; и EBX pop EBP ; восстановим значение EBP ret ; возврат из функции

public gcd end

Арифметические операции

К четырем обычным арифметическим операциям сложения +, вычитания -, умножения * и деления / в Си добавлена операция нахождения остатка от деления первого целого числа на второе, которая обозначается символом процента %. Приоритет у операции вычисления остатка % такой же, как и у деления или умножения. Отметим, что операция % перестановочна с операцией изменения знака (унарным минусом), например, в результате выполнения двух строк

x = -(5 % 3); y = (-5) % 3;

обеим переменным x и y присваивается отрицательное значение -2.

Арифметика указателей

С указателями можно выполнять следующие операции:

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

Прибавление к указателю p целого числа n означает увеличение адреса, который содержится в переменной p, на суммарный размер n элементов того типа, на который ссылается указатель. Указатель как бы сдвигается на n элементов вправо, если считать, что индексы элементов массива возрастают слева направо. Аналогично вычитание целого числа n из указателя означает сдвиг указателя влево на n элементов. Пример:

int *p, *q; int a[100]; p = &(a[5]); // записываем в p адрес 5-го // элемента массива a p += 7; // p будет содержать адрес 12-го эл-та q = &(a[10]); --q; // q содержит адрес элемента a[9]

Значение указателя при прибавлении к нему целого числа n увеличивается на произведение n на количество байтов, занимаемое одним элементом того типа, на который ссылается указатель. В программировании это называют масштабированием.

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

int *p, *q; int a[100]; int n; p = &(a[5]); q = &(a[12]); n = q - p; // n == 7 q = p + n; // q == &(a[12])

Подчеркнем, что указатели нельзя складывать! В отличие от разности указателей, операция сложения указателей (т.е. сложения адресов памяти) абсолютно бессмысленна.

int *p, *q, *r; int a[100]; p = &(a[5]); q = &(a[12]); r = p + q; // Ошибка! Указатели нельзя складывать.

Базовые типы

В языке Си используются всего два базовых типа: целые и вещественные числа. Кроме того, имеется фиктивный тип void ("пустота"), который применяется либо для функции, не возвращающей никакого значения, либо для описания указателя общего типа (когда неизвестна информации о типе объекта, на который ссылается указатель).

В C++ добавлен логический тип.

Целочисленные типы

Целочисленные типы различаются по длине в байтах и по наличию знака. Их четыре - char, short, int и long. Кроме того, к описанию можно добавлять модификаторы unsigned или signed для беззнаковых (неотрицательных) или знаковых целых чисел.

Функции

Функция является основной структурной единицей языка Си. В других языках функции иногда называют подпрограммами. Функция - это фрагмент программы, который может вызываться из других программ. Функция обычно выполняет алгоритм, который описывается и реализуется отдельно от других алгоритмов. При вызове функции передаются аргументы, которые могут быть использованы в теле функции. В результате своей работы функция возвращает значение некоторого типа. Например, функция sin, прототип которой задается строкой

double sin(double x);

имеет один аргумент x типа double (вещественное число). Результат функции также имеет тип double. При вызове фукция sin вычисляет синус числа, переданного ей в качестве фактического аргумента, и возвращает вычисленное значение в вызывающую программу.

Вызов функции происходит в результате использования ее имени в выражении. За именем функции следуют круглые скобки, внутри которых перечисляются фактические значения ее аргументов. Даже если аргументов нет, круглые скобки с пустым списком аргументов обязательно должны присутствовать!

После вызова функции значение, возвращенное в результате ее выполнения, используется в выражении (имя функции как бы заменяется возвращенным значением). Примеры:

x = sin(1.0);

Здесь в результата вызова функции sin вычисляется синус числа 1.0, затем вычисленное значение записывается в переменную x при выполнении оператора присваивания "=". Другой пример:

f();

Вызывается функция f, не имеющая параметров. Значение, возвращенное в результате выполнения функции f, не используется. Программа на Си состоит из функций. Работа программы всегда начинается с функции с именем main. Рассмотрим минимальный пример Си-программы

Конструирование новых типов

Для создания новых типов в Си можно использовать конструкции массива, указателя и структуры.

Логические операции

Логические операции и выражения были подробно рассмотрены в разделе 1.4.4. В Си используются следующие обозначения для логических операций:

|| логическое "или" (логическое сложение) && логическое "и" (логическое умножение) ! логическое "не" (логическое отрицание)

Логические константы "истина" и "ложь" обозначаются через true и false (это ключевые слова языка). Примеры логических выражений:

bool a, b, c, d; int x, y;

a = b || c; // логическое "или" d = b && c; // логическое "и" a = !b; // логическое "не" a = (x == y); // сравнение в правой части a = false; // ложь b = true; // истина c = (x > 0 && y != 1); // c истинно, когда // оба сравнения истинны

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

Чрезвычайно важной особенностью операций логического сложения и умножения является так называемое "сокращенное вычисление" результата. А именно, при вычислении результата операции логического сложения или умножения всегда сначала вычисляется значение первого аргумента. Если оно истинно в случае логического сложения или ложно в случае логического умножения, то второй аргумент операции не вычисляется вовсе! Результат операции полагается истинным в случае логического сложения или ложным в случае логического умножения. Подробно это рассмотрено в разделе 1.4.4.

Логический тип

В языке Си специального логического типа нет, вместо него используются переменные целого типа. Значению "истина" соответствует любое ненулевое целое число, значению "ложь" - ноль. Например, в Си допустим такой фрагмент программы:

int b; double s; . . . if (b) { s = 1.0; }

Здесь целочисленная переменная b используется в качестве условного выражения в операторе if ("если"). Если значение b отлично от нуля, то выполняется тело оператора if, т.е. переменной s присваивается значение 1.0; если значение b равно нулю, то тело оператора if не выполняется.

На самом деле, приведенный пример представляет собой дурной стиль программирования. Гораздо яснее выглядит следующий фрагмент, эквивалентный приведенному выше:

if (b != 0) { s = 1.0; }

В более строгом языке Java второй фрагмент корректен, а первый нет.

Язык C++ вводит логический тип bool в явном виде (отметим, что этот тип появился в C++ далеко не сразу!). Переменные типа bool принимают два значения: false и true (истина и ложь). Слова false и true являются ключевыми словами языка C++.

Примеры описания логических переменных в C++:

bool a, b; bool c = false, d = true;

Массивы

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

int a[10]; char c[256]; double d[1000];

В первой строке описан массив целых чисел из 10 элементов. Подчеркнем, что нумерация в Си всегда начинается с нуля, так что индексы элементов массива изменяются в пределах от 0 до 9. Во второй строке описан массив символов из 256 элементов (индексы в пределах 0...255), в третьей - массив вещественных чисел из 1000 элементов (индексы в пределах 0...999). Для доступа к элементу массива указывается имя массива и индекс элемента в квадратных скобках, например,

a[10], c[255], d[123].

Оператор sizeof возвращает размер всего массива в байтах, а не в элементах массива. В данном примере

sizeof(a) = 10*sizeof(int) = 40, sizeof(c) = 256*sizeof(char) = 256, sizeof(d) = 1000*sizeof(double) = 8000.

Модификатор const

Константы в Си можно задавать двумя способами:

с помощью директивы #define препроцессора. Например, строка #define MILLENIUM 1000

задает символическое имя MILLENIUM для константы 1000. Препроцессор всюду в тексте заменяет это имя на константу 1000, используя текстовую подстановку. Это не очень хороший способ, поскольку при таком задании отсутствует контроль типов; с помощью модификатора const. При описании любой переменной можно добавить модификатор типа const. Например, вместо #define можно использовать следующее описание: const int MILLENIUM = 1000;

Модификатор const означает, что переменная MILLENIUM является константой, т.е. менять ее значение нельзя. Попытка присвоить новое значение константе приведет к ошибке компиляции: MILLENIUM = 100; // Ошибка: константу // нельзя изменять

При описании указателя модификатор const, записанный до звездочки, означает, что описан указатель на константный объект, т.е. на объект, менять который нельзя или запрещено. Например, в строке

const char *p;

описан указатель на константную строку (массив символов, менять который запрещено).

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

Константный указатель ссылается на константный объект, однако, содержимое самого указателя может изменяться. Например, следующий фрагмент вполне корректен:

const char *str = "e2e4"; . . . str = "c7c5";

Здесь константный указатель str сначала содержит адрес константной строки "e2e4". Затем в него записывается адрес другой константной строки "c7c5".

В Си можно также описать указатель, значение которого не может быть изменено; для этого модификатор const указывается после звездочки. Например, фрагмент кода

int i; int * const p = &i;

навечно записывает в указатель p адрес переменной i, перенаправить указатель p на другую переменную уже нельзя. Строка

p = &n;

является ошибкой, т.к. указатель p - константа, а константе нельзя присвоить новое значение. Указатели, значения которых изменять нельзя, используются в Си значительно реже, в основном при заполнении константных таблиц.

Модификатор unsigned

Типы int, short и long представляют целые числа со знаком. Для типа char стандарт Си не устанавливает явно наличие знака, однако большинство компиляторов трактуют элементы типа char как целые числа со знаком в диапазоне от -128 до 127. Если необходимо трактовать целые числа как неотрицательные, или беззнаковые, следует добавить модификатор unsigned при описании переменных. Примеры:

unsigned char c = 255; unsigned short s = 65535; unsigned int i = 1000000000; unsigned j = 1;

При описании типа "unsigned int" слово "int" можно опускать, что и сделано в последнем примере.

Следует по возможности избегать беззнаковых типов, поскольку арифметика беззнаковых чисел не на всех компьютерах реализована одинаково и из-за этого при переносе программы с одной платформы на другую могут возникнуть проблемы. По этой причине в языке Java беззнаковые числа запрещены.

Имеется также модификатор signed (знаковый). Его имеет смысл использовать на тех платформах, в которых тип char является беззнаковым. Пример описания:

signed char d = (-1);

Модификатор volatile

Слово volatile в переводе означает "изменчивый, непостоянный". В Си к описанию переменной следует добавлять слово volatile, если ее значение может изменяться не в результате выполнения программы, а из-за каких-либо внешних событий. Например, переменная может измениться при выполнении программы-обработчика аппаратного прерывания (см. раздел 2.5). Другой причиной "внезапного" изменения значения переменной может быть переключение между нитями при параллельном программировании (см. 2.6.2) и модификация переменной в параллельной нити.

Необходимо обязательно сообщать компилятору о таких изменчивых переменных. Дело в том, что процессор выполняет все действия с регистрами, а не с элементами памяти. Оптимизирующий компилятор держит значения большинства переменных в регистрах, сводя к минимуму обращения к памяти. Непостоянная переменная может изменить свое значение в памяти, но программа будет по-прежнему использовать значение в регистре, которое осталось прежним. Из-за этого выполнение программы нарушится. Модификатор volatile запрещает даже временно помещать переменную в регистр процессора.

Пример описания переменной:

volatile int inputPort;

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

Операции сдвига

Операции сдвига применяются к целочисленным переменным: двоичный код числа сдвигается вправо или влево на указанное количество позиций. Сдвиг вправо обозначается двумя символами "больше" >>, сдвиг влево - двумя символами "меньше" <<. Примеры:

int x, y; . . . x = (y >> 3); // Сдвиг на 3 позиции вправо y = (y << 2); // Сдвиг на 2 позиции влево

При сдвиге влево на k позиций младшие k разрядов результата устанавливаются в ноль. Сдвиг влево на k позиций эквивалентен умножению на число 2k. Сдвиг вправо более сложен, он по-разному определяется для беззнаковых и знаковых чисел. При сдвиге вправо беззнакового числа на k позиций освободившиеся k старших разрядов устанавливаются в ноль. Например, в двоичной записи имеем:

unsigned x; x = 110111000...10110011 x >> 3 = 000110111000...10110

Сдвиг вправо на k позиций соответствует целочисленному делению на число 2k.

При сдвиге вправо чисел со знаком происходит так называемое "расширение знакового разряда". Именно, если число неотрицательно, т.е. старший, или знаковый, разряд числа равен нулю, то происходит обычный сдвиг, как и в случае беззнаковых чисел. Если же число отрицательное, т.е. его старший разряд равен единице, то освободившиеся в результате сдвига k старших разрядов устанавливаются в единицу. Число, таким образом, остается отрицательным. При k = 1 это соответствует делению на 2 только для отрицательных чисел, не равных -1. Для числа -1, все биты двоичного кода которого равны единице, сдвиг вправо не приводит к его изменению. Пример (используется двоичная запись):

int x; x = 110111000...10110011 x >> 3 = 111110111000...10110

В программах лучше не полагаться на эту особенность сдвига вправо для знаковых чисел и использовать конструкции, которые заведомо одинаково работают для знаковых и беззнаковых чисел. Например, следующий фрагмент кода выделяет из целого числа составляющие его байты и записывает их в целочисленные переменные x0, x1, x2, x3, младший байт в x0, старший в x3. При этом байты трактуются как неотрицательные числа. Фрагмент выполняется одинаково для знаковых и беззнаковых чисел:

int x; int x0, x1, x2, x3; . . . x0 = (x & 255); x1 = ((x >> 8) & 255); x2 = ((x >> 16) & 255); x3 = ((x >> 24) & 255);

Здесь число 255 играет роль маски, см. раздел 3.4.7. При побитовом умножении на эту маску из целого числа вырезается его младший байт, поскольку маска 255 содержит единицы в младших восьми разрядах. Чтобы получить байт числа x с номером n, n = 0,1,2,3, мы сначала сдвигаем двоичный код x вправо на 8n разрядов, таким образом, байт с номером n становится младшим. Затем с помощью побитового умножения вырезается младший байт.

Операции сравнения

Операция сравнения сравнивает два выражения. В результате вырабатывается логическое значение - true или false (истина или ложь) в зависимости от значений выражений. Примеры:

bool res; int x, y; res = (x == y); // true, если x равно y, иначе false res = (x == x); // всегда true res = (2 < 1); // всегда false

Операции сравнения в Си обозначаются следующим образом:

== равно, != не равно, > больше, >= больше или равно, < меньше, <= меньше или равно.

Операции увеличения и уменьшения

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

++i; эквивалентно i = i+1

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

double x; . . . ++x; // Ошибка! Операция ++ неприменима // к вещ. переменной

Операция ++ увеличивает значение переменной на "минимальный атом". Так как для вещественных переменных такого "атомарного" значения нет, операции увеличения и уменьшения для них запрещены.

Для указателей операция ++ увеличивает значение переменной на размер одного элемента того типа, на который ссылается указатель. Для указателя "атомом" является один элемент заданного типа, поэтому размер одного элемента и является шагом изменения значения указателя. Это очень естественно, т.к. после увеличения указатель будет содержать адрес следующего элемента данного типа, а после уменьшения - адрес предыдущего элемента. Пример:

double a[100]; double *p = &(a[15]); // в p записывается адрес // элемента массива a[15] ++p; // в p будет адрес элемента a[16] // (адрес увеличивается на sizeof(double) == 8)

Описаны массив a вещественных чисел типа double и указатель p на элементы типа double. При описании указателя p в него заносится начальное значение, равное адресу элемента a[15] массива a. После выполнения операции увеличения ++ в переменной p будет содержаться адрес следующего элемента a[16]. Физически содержимое переменной p увеличивается на размер одного элемента типа double, т.е. на 8.

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

++x; // Префиксная форма x--; // Суффиксная форма

Разница между префиксной и суффиксной формами проявляется только при вычислении сложных выражений. Если используется префиксная форма операции ++, то сначала переменная увеличивается, и только после этого ее новое значение используется в выражении. При использовании суффиксной формы значение переменной сначала используется в выражении и только затем увеличивается. Примеры:

int x = 5, y = 5, a, b; a = (++x) + 2; // переменной a присваивается значение 8 b = (y++) + 2; // переменной b присваивается значение 7

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

Дадим два совета (возможно, не бесспорные) по использованию операций ++ и --:

никогда не применяйте эти операции в сложных выражениях! Ничего, кроме путаницы, это не дает. Например, вместо фрагмента

double *p, x, y; . . . y = *p++ + x;

лучше использовать фрагмент double *p, x, y; . . . y = *p + x; ++p;

С точки зрения компилятора, они абсолютно эквивалентны, но второй фрагмент проще и понятнее (и, значит, вероятность ошибки программирования меньше); всегда отдавайте предпочтение префиксной форме операций ++ и --. Например, вместо фрагмента

int x, y; . . . x++; y--; // Используется суффиксная форма

лучше использовать фрагмент

int x, y; . . . ++x; --y; // Лучше применять префиксную форму

Операции "увеличить на", "домножить на" и т.п.

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

x = x + y;

Здесь складываются значения двух переменных x и y, результат помещается в первую переменную x. Таким образом, значение переменной x увеличивается на значение y. Подобные фрагменты встречаются в программах гораздо чаще, чем фрагменты вида

x = y + z;

где аргументы и результат различны. Рассмотрим, например, фрагмент программы, вычисляющий сумму элементов массива вещественных чисел (забегая вперед, мы используем в нем конструкцию цикла "пока"):

double a[100]; double s; int i; . . . s = 0.0; i = 0; while (i < 100) { s = s + a[i]; ++i; }

Здесь сумма элементов массива накапливается в переменной s. В строке

s = s + a[i];

к сумме s прибавляется очередной элемент массива a[i], т.е. значение s увеличивается на a[i]. В Си существует сокращенная запись операции увеличения:

s += a[i];

Оператор += читается как "увеличить на". Строка

x += y; // Увеличить значение x на y

эквивалентна в Си строке

x = x + y; // x присвоить значение x + y,

но короче и нагляднее.

Оператор вида ?= существует для любой операции ?, допустимой в Си. Например, для арифметических операций +, -, *, /, % можно использовать операции

+= увеличить на -= уменьшить на *= домножить на /= поделить на %= поделить с остатком на

к примеру, строка

x *= 2.0;

удваивает значение вещественной переменной x.

Операторы вида ?= можно использовать даже для операций ?, которые записываются двумя символами. Например, операции логического умножения и сложения (см. раздел 1.4.4) записываются в Си как && (двойной амперсенд) и || (двойная вертикальная черта). Соответственно, логические операторы "домножить на" и "увеличить на" записываются в виде &&= и ||=, например,

bool x, y; x &&= y; // эквивалентно x = x && y; x ||= y; // эквивалентно x = x || y;

Операция приведения типа

Операция приведения типа (type cast) является одной из самых важных в Си. Без знакомства с синтаксисом этой операции (весьма непривычного для начинающих) и сознательного ее использования написать на Си что-нибудь более или менее полезное невозможно.

Операция приведения типа используется, когда значение одного типа преобразуется к другому типу, в том случае, если существует некоторый разумный способ такого преобразования. Операция обозначается именем типа, заключенным в круглые скобки; она записывается перед ее единственным аргументом. Рассмотрим два примера. Пусть требуется преобразовать целое число к вещественному типу. Как известно, целые и вещественные числа по-разному представляются в компьютере, см. раздел 3.3.1. Тем не менее, существует однозначный способ преобразования целого числа типа int к вещественному типу double. В первом примере значение целой переменной n приводится к вещественному типу и присваивается вещественной переменной x:

double x; int n; . . . x = (double) n; // Операция приведения к типу double

В данном случае никакой потери информации не происходит, поэтому такое приведение допустимо и по умолчанию:

x = n; // Эквивалентно x = (double) n;

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

double x, y; int n, k; . . . x = 3.7; y = (-1.5); n = (int) x; // n присваивается значение 3 k = (int) y; // k присваивается значение -1

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

double x; int n; . . . n = x; // неявное приведение вещественного к целому

то компилятор обязательно выдаст предупреждение (или даже ошибку, если компилятор строгий). Поэтому так писать ни в коем случае нельзя! Когда используется явное приведение типа, компилятору сообщается, что это не случайная ошибка, а намеренное приведение вещественного значения к целому типу, при котором дробная часть отбрасывается. При этом компилятор никаких предупреждений не выдает.

Операция приведения типа чаще всего используется для преобразования указателей. Например, стандартная функция захвата динамической памяти malloc возвращает указатель общего типа void* (см. раздел 3.7.3). Значение указателя обобщенного типа нельзя присвоить указателю на конкретный тип (язык C++ запрещает такие присвоения, Си-компиляторы иногда разрешают преобразования указателей по умолчанию, выдавая предупреждения, - но в любом случае это дурной стиль!). Для преобразования указателей разного типа нужно использовать операцию приведения типа в явном виде. В следующем примере в динамической памяти захватывается участок размером в 400 байт, его адрес присваивается указателю на массив из 100 целых чисел:

int *a; // Описываем указатель на массив типа int . . . // Захватываем участок памяти размером в 400 байт // (поскольку sizeof(int) == 4), приводим указатель // на него от типа void* к типу int* и присваиваем // приведенное значение указателю a: a = (int*) malloc(100 * sizeof(int));

Отметим, что допустимо неявное преобразование любого указателя к указателю обобщенного типа void*. Обратное, как указано выше, считается грубой ошибкой в C++ и дурным стилем (возможно, сопровождаемым предупреждением компилятора) в Си:

int *a; // Указатель на целое число void *p; // Указатель обобщенного типа . . . a = p; // Ошибка! В C++ запрещено неявное // приведение типа от void* к int* a = (int*) p; // Корректно: явное приведение типа

p = a; // Корректно: любой указатель можно // неявно привести к обобщенному

Оператор присваивания

Оператор присваивания является основой любого алгоритмического языка (см. лекцию 3). В Си он записывается с помощью символа равенства, например, строка

x = 100;

означает присвоение переменной x значения 100. Для сравнения двух значений используется двойное равенство ==, например, строка

bool f = (2 + 2 == 5);

присваивает логической переменной f значение false (поскольку 2+2 не равно пяти, логическое выражение в скобках ложно).

Непривычным для начинающих может быть то, что оператор присваивания "=" в Си - бинарная операция, такая же, как, например, сложение или умножение. Значением операции присваивания = является значение, которое присваивается переменной, стоящей в левой части. Это позволяет использовать знак присваивания внутри выражения, например,

x = (y = sin(z)) + 1.0;

Здесь в скобках стоит выражение y = sin(z), в результате вычисления которого переменной y присваивается значение sin z. Значением этого выражения является значение, присвоенное переменной y, т.е. sin z. К этому значению затем прибавляется единица, т.е. в результате переменной x присваивается значение sin z+1.

Выражения, подобные приведенному в этом примере, иногда используются, когда необходимо запомнить значение подвыражения (в данном случае sin (z)) в некоторой переменной (в данном случае y), чтобы затем не вычислять его повторно. Еще один пример:

n = (k = 3) + 2;

В результате переменной k присваивается значение 3, а переменной n - значение 5. Конечно, в нормальных программах такие выражения не встречаются.

Оператор sizeof

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

int i; char c; short s; long l; double d; float f; bool b;

Тогда приведенные ниже выражения в 32-разрядной архитектуре имеют следующие значения:

размер переменнойразмер типазначение

sizeof(i)	sizeof(int)	4
sizeof(c)	sizeof(char)	1
sizeof(s)	sizeof(short)	2
sizeof(l)	sizeof(long)	4
sizeof(d)	sizeof(double)	8
sizeof(f)	sizeof(float)	4
sizeof(b)	sizeof(bool)	1

Оператор typedef

В языке Си можно задать имя типа, если его описание достаточно громоздко и его не хочется повторять много раз. В дальнейшем можно использовать имя типа при описании переменных. Для определения типа применяется оператор typedef. Синтаксически оператор typedef аналогичен обычному описанию переменной, к которому в самом начале добавлено слово typedef. При этом вместо переменной определяется имя нового типа. Сравните следующее описание переменной "real" и определение нового типа "Real":

double real; // Описание переменной real typedef double Real; // Определение нового типа Real, // эквивалентного типу double.

Мы как бы описываем переменную, добавляя к описанию слово typedef. При этом описываемое имя становится именем нового типа. Его можно использовать затем для задания переменных:

Real x, y, z;

Чаще всего определение типов с помощью typedef используют, когда описание типа достаточно громоздко. Оператор typedef позволяет задать его только один раз, что облегчает исправление программы при необходимости. Например, следующая строка определяет тип callback как указатель на функцию с одним целым параметром, возвращающую значение логического типа:

typedef bool (*callback)(int);

Строка, описывающая три переменные p, g, r,

callback p, q, r;

эквивалентна строке

bool (*p)(int), (*q)(int), (*r)(int);

но первая строка, конечно, понятнее и нагляднее.

Еще одна цель использования оператора typedef состоит в том, чтобы сделать текст программы менее зависимым от особенностей конкретной архитектуры (разрядности процессора, конкретного Си-компилятора и т.п.). Например, в старых Си-компиляторах, которые использовались для 16-разрядных процессоров Intel 80286, существовали так называемые близкие (near) и далекие (far) указатели. В эталонном языке Си ключевых слов near и far нет, они использовались лишь в Си-компиляторах для Intel 80286 как расширение языка. Поэтому, чтобы тексты программ не зависели от компилятора, в системных h-файлах с помощью оператора typedef определялись имена для типов указателей, а в текстах программ использовались не типы эталонного языка Си, а введенные имена типов. Например, тип "далекий указатель на константную строку" в соответствии с соглашениями фирмы Microsoft называется LPCTSTR (Long Pointer to Constant Text STRing). При использовании 16-разрядного компилятора он определяется в системных h-файлах как

typedef const char far *LPCTSTR;

в 32-разрядной архитектуре он определяется без ключевого слова far (поскольку в ней все указатели "далекие"):

typedef const char *LPCTSTR;

Во всех программах указатели на константные строки описываются как имеющие тип LPCTSTR:

LPCTSTR s;

благодаря этому программы Microsoft можно использовать как в 16-разрядной, так и в 32-разрядной архитектуре.

Основы языка Си

В настоящее время язык Си и объектно-ориентированные языки его группы (прежде всего C++, а также Java и C#) являются основными в практическом программировании. Достоинство языка Си - это, прежде всего, его простота и лаконичность. Язык Си легко учится. Главные понятия языка Си, такие, как статические и локальные переменные, массивы, указатели, функции и т.д., максимально приближены к архитектуре реальных компьютеров. Так, указатель - это просто адрес памяти, массив - непрерывная область памяти, локальные переменные - это переменные, расположенные в аппаратном стеке, статические - в статической памяти. Программист, пишущий на Си, всегда достаточно точно представляет себе, как созданная им программа будет работать на любой конкретной архитектуре. Другими словами, язык Си предоставляет программисту полный контроль над компьютером.

Первоначально язык Си задумывался как заменитель Ассемблера для написания операционных систем. Поскольку Си - это язык высокого уровня, не зависящий от конкретной архитектуры, текст операционной системы оказывался легко переносимым с одной платформы на другую. Первой операционной системой, написанной практически целиком на Си, была система Unix. В настоящее время почти все используемые операционные системы написаны на Си. Кро- ме того, средства программирования, которые операционная система предоставляет разработчикам прикладных программ (так называемый API - Application Program Interface), - это наборы системных функций на языке Си.

Тем не менее, область применения языка Си не ограничилась разработкой операционных систем. Язык Си оказался очень удобен в программах обработки текстов и изображений, в научных и инженерных расчетах. Объектно-ориентированные языки на основе Си отлично подходят для программирования в оконных средах.

В данном разделе будут приведены лишь основные понятия языка Си (и частично C++). Это не заменяет чтения полного учебника по Си или C++, например, книг [6] и [8].

Мы будем использовать компилятор C++ вместо Cи. Дело в том, что язык Си почти целиком входит в C++, т.е. нормальная программа, написанная на Си, является корректной C++ программой. Слово "нормальная" означает, что она не содержит неудачных конструкций, оставшихся от ранних версий Си и не используемых в настоящее время. Компилятор C++ предпочтительнее, чем компилятор Си, т.к. он имеет более строгий контроль ошибок. Кроме того, некоторые конструкции C++, не связанные с объектно-ориентированным программированием, очень удобны и фактически являются улучшением языка Си. Это, прежде всего, комментарии //, возможность описывать локальные переменные в любой точке программы, а не только в начале блока, и также задание констант без использования оператора #define препроцесора. Мы будем использовать эти возможности C++, оставаясь по существу в рамках языка Си.

Побитовые логические операции

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

& побитовое логическое сложение ("и") | побитовое логическое умножение ("или") ~ побитовое логическое отрицание ("не") ^ побитовое сложение по модулю 2 (исключающее "или")

(Необходимо помнить, что логические операции умножения и сложения записываются с помощью двойных знаков && или ||, а побитовые - с помощью одинарных.)

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

В основном побитовые операции применяются для манипуляций с битовыми масками. Например, пусть целое число x описывает набор признаков некоторого объекта, состоящий из четырех признаков. Назовем их условно A, B, C, D. Пусть за признак A отвечает нулевой бит слова x (биты в двоичном представлении числа нумеруются справа налево, начиная с нуля). Если бит равен единице (программисты говорят бит установлен), то считается, что объект обладает признаком A. За признаки B, C, D отвечают биты с номерами 1, 2, 3. Общепринятая практика состоит в том, чтобы определить константы, отвечающие за соответствующие признаки (их обычно называют масками):

const int MASK_A = 1; const int MASK_B = 2; const int MASK_C = 4; const int MASK_D = 8;

Эти константы содержат единицу в соответствующем бите и нули в остальных битах. Для того чтобы проверить, установлен ли в слове x бит, соответствующий, к примеру, признаку D, используется операция побитового логического умножения. Число x умножается на константу MASK_D; если результат отличен от нуля, то бит установлен, т.е. объект обладает признаком D, если нет, то не обладает. Такая проверка реализуется следующим фрагментом:

if ((x & MASK_D) != 0) { // Бит D установлен в слове x, т.е. // объект обладает признаком D . . . } else { // Объект не обладает признаком D . . . }

При побитовом логическом умножении константа MASK_D обнуляет все биты слова x, кроме бита D, т.е. как бы вырезает бит D из x. В двоичном представлении это выглядит примерно так:

x: 0101110110...10*101 MASK_D: 0000000000...001000 x & MASK_D: 0000000000...00*000

Звездочкой здесь обозначено произвольное значение бита D слова x.

Для установки бита D в слове x используется операция побитового логического сложения:

x = (x | MASK_D); // Установить бит D в слове x

Чаще это записывается с использованием операции |= типа "увеличить на" (см. раздел 3.4.4):

x |= MASK_D; // Установить бит D в слове x

В двоичном виде это выглядит так:

x: 0101110110...10*101 MASK_D: 0000000000...001000 x | MASK_D: 0101110110...101101

Операция побитового отрицания "~" инвертирует биты слова:

x: 0101110110...101101 ~x: 1010001001...010010

Для очистки (т.е. установки в ноль) бита D используется комбинация операций побитового отрицания и побитового логического умножения:

x = (x & ~MASK_D); // Очистить бит D в слове x

или, применяя операцию "&=" типа "домножить на":

x &= ~MASK_D; // Очистить бит D в слове x

Здесь сначала инвертируется маска, соответствующая биту D,

MASK_D: 0000000000...001000 ~MASK_D: 1111111111...110111

в результате получаются единицы во всех битах, кроме бита D. Затем слово x побитно домножается на инвертированную маску:

x: 0101110110...10*101 ~MASK_D: 1111111111...110111 x & ~MASK_D: 0101110110...100101

В результате в слове x бит D обнуляется, а остальные биты остаются неизменными.

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

if (x & MASK_D != 0) {

эквивалентна строке

if ((x & 1) != 0) {

т.е. проверяется бит A, а вовсе не D! Дело в том, что приоритет операции сравнения != выше, чем операции побитового умножения &, т.е.

в приведенной строке скобки неявно расставлены так:

if (x & (MASK_D != 0)) {

Выражение (MASK_D != 0) истинно и, таким образом, равно единице, поэтому строка эквивалентна

if (x & 1) {

что, в свою очередь, эквивалентно более канонической записи:

if ((x & 1) != 0) {

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

Побитовую операцию ^ называют сложением по модулю 2, а также "исключающим или". Часто для нее используется аббревиатура XOR, от eXclusive OR. "Таблица сложения" для этой операции выглядит следующим образом:

0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0.

Пусть x - произвольное целое число, m - маска, т.е. число, в котором интересующие программиста биты установлены в единицу, остальные в ноль. В результате выполнения операции XOR

x = (x ^ m);

или, в более удобной записи,

x ^= m;

биты в слове x, соответствующие установленным в единицу битам маски m, изменяются на противоположные (инвертируются). Биты слова x, соответствующие нулевым битам маски, не меняют своих значений. Пример:

x: 101101...1001011110 m: 000000...0011111100 x ^ m: 101101...1010100010

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

((x ^ m) ^ m) == x

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

Программа "Hello, World!"

Приведенная ниже программа печатает фразу "Hello, World!" на экране терминала.

#include <stdio.h>

int main() { printf("Hello, World\n"); return 0; }

Первая строка подключает заголовочный файл с описаниями стандартных функций ввода-вывода Си-библиотеки. В частности, в этом файле описан прототип функции printf (печать по формату), используемой для вывода информации в стандартный поток вывода (по умолчанию он назначен на терминал). Выполнение программы начинается с функции main. Функция main возвращает по окончании работы целое число, которое трактуется операционной системой как код завершения задания. Число ноль обычно означает успешное выполнение задачи, но вообще-то программист волен по своему усмотрению определять коды завершения. Во многих книгах приводятся примеры функций main, которые ничего не возвращают, - строго говоря, это ошибка (на которую, к сожалению, многие компиляторы никак не реагируют).

Тело любой функции заключается в фигурные скобки. В теле функции main вызывается функция printf. В данном случае ее единственным аргументом является строка, которая выводится в стандартный поток вывода. Строковые константы в Си заключаются в двойные апострофы. Строка заканчивается символом перевода курсора в начало следующей строки \n (читается как "new line", новая строка). Желательно любую печать завершать этим символом, иначе при следующей печати новая строка будет дописана в конец предыдущей.

Строка

return 0;

завершает выполнение функции main и возвращает нулевой результат ее выполнения. Операционная система трактует нулевой результат как признак успешного завершения программы.

Для выполнения данной программы надо сначала ввести ее текст в файл "hello.cpp", используя любой текстовый редактор. Затем надо скомпилировать и собрать готовую программу. Конкретные команды зависят от операционной системы и установленного Си-компилятора. В системе Unix с компилятором gcc из пакета GNU это делается с помощью команды

g++ hello.cpp

В результате создается выполняемый файл с именем "a.out". Для запуска программы следует выполнить команду

./a.out

Если необходимо, чтобы в результате компиляции и сборки создавался выполняемый файл с именем "hello", то надо выполнить следующую команду:

g++ -o hello hello.cpp

Здесь в командной строке используется ключ "-o hello" (от слова "output"), задающий имя "hello" для выходного файла. В этом случае программа запускается с помощью команды

./hello

Заметим, что в системе Unix имена выполняемых файлов обычно не имеют никакого расширения. В системах MS DOS и MS Windows выполняемые файлы имеют расширение ".exe".

Сложные описания

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

для группировки можно использовать круглые скобки, например, описание

int *(x[10]);

означает "массив из 10 элементов типа указатель на int";

при отсутствии скобок приоритеты конструкций описания распределены следующим образом: - операция * определения указателя имеет самый низкий приоритет. Например, описание

int *x[10];

означает "массив из 10 элементов типа указатель на int". Здесь к имени переменной x сначала применяется операция определения массива [] (квадратные скобки), поскольку она имеет более высокий приоритет, чем звездочка. Затем к полученному массиву применяется операция определения указателя. В результате получается "массив указателей", а не указатель на массив! Если нам нужно определить указатель на массив, то следует использовать круглые скобки при описании:

int (*x)[10];

Здесь к имени x сначала применяется операция * определения указателя; операции определения массива [] (квадратные скобки после имени) и определения функции (круглые скобки после имени) имеют одинаковый приоритет, более высокий, чем звездочка. Примеры:

int f();

Описан прототип функции f без аргументов, возвращающей значение типа int.

int (*f())[10];

Описан прототип функции f без аргументов, возвращающей значение типа указатель на массив из 10 элементов типа int; последний пример уже не является очевидным. Общий алгоритм разбора сложного описания можно охарактеризовать как чтение изнутри. Сначала находим описываемое имя. Затем определяем, какая операция применяется к имени первой. Если нет круглых скобок для группировки, то это либо определение указателя (звездочка слева от имени), либо определение массива (квадратные скобки справа от имени), либо определение функции (круглые скобки справа от имени). Таким образом получается первый шаг сложного описания. Затем находим следующую операцию описания, которая применяется к уже выделенной части сложного описания, и повторяем это до тех пор, пока не исчерпаем все описание. Проиллюстрируем этот алгоритм на примере:

void (*a[100])(int x);

Описывается переменная a. К ней сначала применяется операция описания массива из 100 элементов, далее - определение указателя, далее - функция от одного целочисленного аргумента x типа int, наконец - определение возвращаемого типа void. Описание читается следующим образом: a - это массив из 100 элементов типа указатель на функцию с одним аргументом x типа int, возвращающую значение типа void.

Ниже расставлены номера операций в порядке их применения в описании переменной a:

void (* a [100])(int x); 5) 3) 1) 2) 4)

Строки

Специального типа данных строка в Си нет. Строки представляются массивами символов (а символы - их числовыми кодами, см. раздел 1.4.3). Последним символом массива, представляющего строку, должен быть символ с нулевым кодом. Пример:

char str[10]; str[0] = 'e'; str[1] = '2'; str[2] = 'e'; str[3] = '4'; str[4] = 0;

Описан массив str из 10 символов, который может представлять строку длиной не более 9, поскольку один элемент должен быть зарезервирован для терминирующего нуля. Далее в массив str записывается строка "e2e4". Строка терминируется нулевым символом. Всего запись строки использует 5 первых элементов массива str с индексами 0...4. Последние 5 элементов массива не используются. Массив можно инициализировать непосредственно при описании, например

char t[] = "abc";

Здесь мы не указываем в квадратных скобках размер массива t, компилятор его вычисляет сам. После операции присваивания записана строковая константа "abc", которая заносится в массив t. В результате компилятор создает массив t из четырех элементов, поскольку на строку отводится 4 байта, включая терминирующий ноль.

Строковые константы заключаются в Си в двойные апострофы, в отличие от символьных, которые заключаются в одинарные. Значением строковой константы является адрес ее первого символа. Когда компилятор встречает строковую константу в программе, он записывает ее текст в область статической памяти, обычно защищенную от изменения, и использует этот адрес. Например, в результате следующего описания

const char *s = "abcd";

создается указатель s, а также строка символов "abcd", строка помещается в область статической памяти, защищенную от изменения, а в указатель s помещается адрес начала строки. Строка содержит 5 элементов: коды символов abcd и терминирующий нулевой байт.

Структура Си-программы

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

В языке Си исходные файлы бывают двух типов:

заголовочные, или h-файлы; файлы реализации, или Cи-файлы.

Имена заголовочных файлов имеют расширение ".h". Имена файлов реализации имеют расширения ".c" для языка Си и ".cpp", ".cxx" или ".cc" для языка C++.

К сожалению, в отличие от языка Си, программисты не сумели договориться о едином расширении имен для файлов, содержащих программы на C++. Мы будем использовать расширение ".h" для заголовочных файлов и расширение ".cpp" для файлов реализации.

Заголовочные файлы содержат только описания. Прежде всего, это прототипы функций. Прототип функции описывает имя функции, тип возвращаемого значения, число и типы ее аргументов. Сам текст функции в h-файле не содержится. Также в h-файлах описываются имена и типы внешних переменных, константы, новые типы, структуры и т.п. В общем, h-файлы содержат лишь интерфейсы, т.е. информацию, необходимую для использования программ, уже написанных другими программистами (или тем же программистом раньше). Заголовочные файлы лишь сообщают информацию о других программах. При трансляции заголовочных файлов, как правило, никакие объекты не создаются. Например, в заголовочном файле нельзя определить глобальную переменную. Строка описания

int x;

определяющая целочисленную переменную x, является ошибкой. Вместо этого следует использовать описание

extern int x;

означающее, что переменная x определена где-то в файле реализации (в каком - неизвестно). Слово extern (внешняя) лишь сообщает информацию о внешней переменной, но не определяет эту переменную.

Файлы реализации, или Cи-файлы, содержат тексты функций и определения глобальных переменных.
Говоря упрощенно, Си-файлы содержат сами программы, а h-файлы - лишь информацию о программах.

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

Файлы реализации могут подключать описания, содержащиеся в заголовочных файлах. Сами заголовочные файлы также могут использовать другие заголовочные файлы. Заголовочный файл подключается с помощью директивы препроцессора #include. Например, описания стандартых функций ввода-вывода включаются с помощью строки

#include <stdio.h>

(stdio - от слов standard input/output). Имя h-файла записывается в угловых скобках, если этот h-файл является частью стандартной Си-библиотеки и расположен в одном из системных каталогов. Имена h-файлов, созданных самим программистом в рамках разрабатываемого проекта и расположенных в текущем каталоге, указываются в двойных кавычках, например,

#include "abcd.h"

Препроцессор - это программа предварительной обработки текста непосредственно перед трансляцией. Команды препроцессора называются директивами. Директивы препроцессора содержат символ диез # в начале строки. Препроцессор используется в основном для подключения h-файлов. В Си также очень часто используется директива #define для задания символических имен констант. Так, строка

#define PI 3.14159265

задает символическое имя PI для константы 3.14159265. После этого имя PI можно использовать вместо числового значения. Препроцессор находит все вхождения слова PI в текст и заменяет их на константу. Таким образом, препроцессор осуществляет подмену одного текста другим. Необходимость использования препроцессора всегда свидетельствует о недостаточной выразительности языка. Так, в любом Ассемблере средства препроцессирования используются довольно интенсивно.В Си по возможности следует избегать чрезмерного увлечения командами препроцессора - это затрудняет понимание текста программы и зачастую ведет к трудно исправляемым ошибкам. В C++ можно обойтись без использования директив #define для задания констант. Например, в C++ константу PI можно задать с помощью нормального описания

const double PI = 3.14159265;

Это является одним из аргументов в пользу применения компилятора C++ вместо Си даже при трансляции программ, не содержащих конструкции класса.

Связь между указателями и массивами

В языке Си имя массива a является указателем на его первый элемент, т.е. выражения a и &(a[0]) эквивалентны. Учитывая арифметику указателей, получаем эквивалентность следующих выражений:

a[i] ~ *(a+i)

Действительно, при прибавлении к a целого числа i происходит сдвиг на i элементов вправо. Поскольку имя массива является адресом его начального элемента, получается адрес i-го элемента массива a. Применяя операцию звездочка *, получаем сам элемент a[i]. Точно так же эквивалентны выражения

&(a[i]) ~ a+i (адрес эл-та a[i]).

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

Обратно, пусть p - указатель. Синтаксис языка Си позволяет трактовать его как адрес начала массива и применять к нему операцию доступа к элементу массива с заданным индексом. Эквивалентны следующие выражения:

p[i] ~ *(p+i)

Таким образом, выбор между массивами и указателями - это выбор между двумя эквивалентными способами записи программ. Указатели, возможно, нравятся системным программистам, которые привыкли к работе с адресами объектов. Массивы больше отвечают традиционному стилю. В объектно-ориентированных языках, таких как Java или C#, указателей либо нет вовсе, либо их разрешено использовать лишь в специфических ситуациях. Массивы же присутствуют в подавляющем большинстве алгоритмических языков.

Для иллюстрации работы с массивами и с указателями приведем два фрагмента программы, суммирующие элементы массива.

double a[100], s; int i; ... s = 0.0; i = 0

while (i < 100) { s += a[i]; ++i; }

double a[100], s; double *p, *g; ... s = 0.0; p = a; // адрес начала массива g = a+100; // адрес за концом while (p < g) { s += *p; ++p; }

Тип char

Тип char представляет целые числа в диапазоне от -128 до 127. Элементы типа char занимают один байт памяти. Слово "char" является сокращением от character, что в переводе означает "символ". Действительно, традиционно символы представляются их целочисленными кодами, а код символа занимает один байт (см. раздел ). Тем не менее, подчеркнем, что элементы типа char - это именно целые числа, с ними можно выполнять все арифметические операции. С математической точки зрения, элементы типа char - это элементы кольца вычетов m = Z256. Стандарт Си не устанавливает, трактуются ли элементы типа char как знаковые или беззнаковые числа, но большинство Си-компиляторов считают char знаковым типом. Примеры описаний переменных типа char:

char c; char eof = (-1); char letterA = 'A';

В последнем случае значение переменной "letterA" инициализируется кодом латинской буквы 'A', т.е. целым числом 65. В Си символьные константы записываются в одинарных апострофах и означают коды соответствующих символов в кодировке ASCII. Рассмотрим следующий пример:

char c = 0; char d = '0';

Здесь переменная c инициализируется нулевым значением, а переменная d - значением 48, поскольку символ '0' имеет код 48.

Тип int

Самый естественный целочисленный тип - это тип int, от слова integer - целое число. Тип int всегда соответствует размеру машинного слова или адреса. Все действия с элементами типа int производятся максимально быстро. Всегда следует выбирать именно тип int, если использование других целочисленных типов не диктуется явно спецификой решаемой задачи. Параметры большинства стандартных функций, работающих с целыми числами или символами, имеют тип int. Целочисленные типы были подробно рассмотрены в лекции 2. Подчеркнем еще раз, что целочисленные переменные хранят на самом деле не целые числа, а элементы кольца вычетов по модулю m, где m - степень двойки.

В современных архитектурах элемент типа int занимает 4 байта, т.е. m = 232. Элементы типа int трактуются в Си как числа со знаком. Минимальное отрицательное число равно -231 = -2147483648, максимальное положительное равно 231-1 = 2147483647.

При описании переменной сначала указывается базовый тип, затем - имя переменной или список имен, разделенных запятыми, например,

int x; int y, z, t;

При описании переменных можно присваивать им начальные значения:

int maxind = 1000; int a = 5, b = 7;

Кроме типа int, существуют еще три целочисленных типа: char, short и long.

Тип void

Слово void означает "пустота". Тип void в Си обозначает отсутствие чего-либо там, где обычно предполагается описание типа. Например, функция, не возвращающая никакого значения, в Си описывается как возвращающая значение типа void:

void f(int x);

Другое применение ключевого слова void состоит в описании указателя общего типа, когда заранее не известен тип объекта, на который он будет ссылаться.

Типы переменных

При рассмотрении типов переменных в Си и C++ следует различать понятия базового типа и конструкции, позволяющей строить новые типы на основе уже построенных. Базовых типов совсем немного - это целые и вещественные числа, которые могут различаться по диапазону возможных значений (или по длине в байтах) и, в случае языка C++, логический тип. К конструкциям относятся массив, указатель и структура, а также класс в C++.

Типы short и long

Слова short и long означают в Си короткое и длинное целое число со знаком. Стандарт Си не устанавливает конкретных размеров для типов short и long. В самой распространенной в настоящее время 32-разрядной архитектуре переменная типа short занимает 2 байта (диапазон значений - от -32768 до 32767), а тип long совпадает с типом int, размер его равен четырем байтам. Примеры описаний:

short s = 30000; long x = 100000; int y = 100000;

В 32-разрядной архитектуре переменные x и y имеют один и тот же тип.

Указатели

Указатели - это переменные, которые хранят адреса объектов. Указатели - фамильная принадлежность языка Си. В неявном виде указатели присутствовали и в других языках программирования, но в Си они используются гораздо чаще, а работа с указателями организована максимально просто.

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

int *a, *b, c, d; char *e; void *f;

В первой строке описаны указатели a и b на тип int и простые переменныe c и d типа int (c и d - не указатели!).

С указателями возможны следующие два действия:

присвоить указателю адрес некоторой переменной. Для этого используется операция взятия адреса, которая обозначается амперсендом &. Например, строка

a = &c;

указателю a присваивает значение адреса переменной c; получить объект, адрес которого содержится в указателе; для этого используется операция звездочка '*', которая записывается перед указателем. (Заметим, что звездочкой обозначается также операция умножения.) Например, строка

d = *a;

присваивает переменной d значение целочисленной переменной, адрес которой содержится в a. Так как ранее указателю a был присвоен адрес переменной c, то в результате переменной d присваивается значение c, т.е. данная строка эквивалентна следующей:

d = c;

Ниже будут рассмотрены также арифметические операции с указателями, которые в языке Си чрезвычайно важны.

Вещественные типы

Вещественных типов два: длинное вещественное число double (переводится как "двойная точность") и короткое вещественное число float (переводится как "плавающее"). Вещественные типы были подробно рассмотрены в разделе 1.4.2. Вещественное число типа double занимает 8 байтов, типа float - 4 байта.

Тип double является основным для компьютера. Тип float - это, скорее, атавизм, оставшийся от ранних версий языка Си. Компьютер умеет производить арифметические действия только с элементами типа double, элементы типа float приходится сначала преобразовывать к double. Точность, которую обеспечивает тип float, низка и не достаточна для большинства практических задач. Все стандартные функции математической библиотеки работают только с типом double. Рекомендуем вам никогда не использовать тип float!

Примеры описаний вещественных переменных:

double x, y, z; double a = 1.5, b = 1e+6, c = 1.5e-3;

В последних двух случаях использовалось задание вещественных констант в экспоненциальной форме (см. раздел 1.4.2).

Выражения

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

Отметим, что, помимо обычных операций, таких, как сложение или умножение, в Си существует ряд операций, несколько непривычных для начинающих. Например, запятая и знак равенства (оператор присваивания) являются операциями в Си; помимо операции сложения +, есть еще операция увеличить на += и операция увеличения на единицу ++. Зачастую они позволяют писать эстетически красивые, но не очень понятные для начинающих программы.

Впрочем, эти непривычные операции можно не использовать, заменяя их традиционными.