Кроме функций "abs", "rem" и прочих, в книге используется множество других функций, которые будут определены позже.

При вычислении выражения х < у < z в языке С сначала вычисляется вьфажение х< у, (результат равен 1, если выражение истинно, и О, если выражение ложно), затем полученный результат сравнивается с z. Выражение л:<у<г с операторами сравнения "<" вычисляется как {x<y)&.(y<z).

В языке С есть три оператора цикла: while, do и for. Цикл while имеет вид:

vhilB {выражение) оператор

Перед выполнением цикла вычисляется выражение. Если выражение истинно (не нуль), выполняется оператор. Затем снова вычисляется выражение. Цикл while завершается, когда выражение становится ложным (равным нулю).

Цикл do аналогичен циклу while, однако проверочное условие стоит после оператора цикла, а именно:

do оператор vhile {выражение)

В этом цикле сначала выполняется оператор, затем вычисляется выражение. Если выражение истинно, операторы цикла выполняются еще раз, если выражение ложно, цикл завершается.

Оператор for имеет вид

f or (е/; 2 < 3) оператор

Сначала вычисляется выражение ei - как правило, это оператор присваивания (аналог выражения-инициализации). Затем вычисляется вг - оператор сравнения (или условное выражение). Если значение условного выражения равно нулю (условие ложно), цикл завершается, если не равно нулю (условие истинно), выполняется оператор. Затем вычисляется (тоже, как правило, оператор присваивания), и вновь вычисляется условное выражение ez- Таким образом, знакомый всем цикл "do i=l to n" загшшется как for (i=i; i<=n; i++) (это один из контекстов использования оператора постинкремента).

1.2. Система команд и модель оценки времени выполнения команд

Чтобы можно было хотя бы грубо сравнивать алгоритмы, представим, что они кодируются для работы на машине с набором команд, подобных современным RISC-компьютерам общего назначения (типа Compaq Alpha, SGI MIPS и IBM RS/6000). Это трехадресная машина, имеющая достаточно большое количество регистров общего назначения - не менее 16. Если не оговорено иное, все регистры 32-разрядные. Регистр общего назначения с номером О всегда содержит нули, все другие регистры равноправны и могут использоваться для любых целей.

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

Б книге описаны два типа RISC: "базовый RISC", команды которого перечислены в табл. 1.2, и "RISC с полным набором команд", в который кроме основных RISC-команд входят дополнительные команды, перечисленные в табл. 1.3.

Таблица 1.2. Базовый набор RISC-команд

Везде в описаниях команд исходные операнды RA и RB представляют собой содержимое регистров.

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

Краткое описание некоторых дополнительных команд, которые может иметь RISC-компьютер, приведено в табл. 1.3.

Таблица 1.3. Дополнительные команды полного набора RISC-команд