Язык программирования Си Брайан Керниган, Деннис Ритчи 3е издание Версия 1 Table of Contents
 Скачать 2.33 Mb.
|
, которая удаляет из s1 все символы, встречающиеся в строке s2 Упражнение 2.5. Напишите функцию any(s1, s2) , которая возвращает либо ту позицию в s1 , где стоит первый символ, совпавший с любым из символов в s2 , либо -1 (если ни один символ из s1 не совпадает с символами из s2 ). (Стандартная библиотечная функция strpbrk делает то же самое, но выдает не номер позиции символа, а указатель на символ.) 2.9. Побитовые операторы В Си имеются шесть операторов для манипулирования с битами. Их можно применять только к целочисленным операндам, т. е. к операндам типов char , short , int и long , знаковым и беззнаковым. & — побитовое И. | — побитовое ИЛИ. ^ — побитовое исключающее ИЛИ. << — сдвиг влево. >> — сдвиг вправо. — побитовое отрицание (унарный). Оператор & (побитовое И) часто используется для обнуления некоторой группы разрядов. Например n = n & 0177; обнуляет в n все разряды, кроме младших семи. Оператор | (побитовое ИЛИ) применяют для установки разрядов; так, х = х | SET_ON; устанавливает единицы в тех разрядах х , которым соответствуют единицы в SET_ON Оператор ^ (побитовое исключающее ИЛИ) в каждом разряде установит 1, если соответствующие разряды операндов имеют различные значения, и 0, когда они совпадают. Поразрядные операторы & и | следует отличать от логических операторов && и || , которые при вычислении слева направо дают значение истинности. Например, если x равно 1, а y равно 2, то x & y даст нуль, а x && у единицу. Операторы << и >> сдвигают влево или вправо свой левый операнд на число битовых позиций, задаваемое правым операндом, который должен быть неотрицательным. Так, х << 2 сдвигает значение х влево на 2 позиции, заполняя освобождающиеся биты нулями, что эквивалентно умножению х на 4. Сдвиг вправо беззнаковой величины всегда сопровождается заполнением освобождающихся разрядов нулями. Сдвиг вправо знаковой величины на одних машинах происходит с распространением знака ("арифметический сдвиг"), на других — с заполнением освобождающихся разрядов нулями ("логический сдвиг"). Унарный оператор поразрядно "обращает" целое т. е. превращает каждый единичный бит в нулевой и наоборот. Например х = х & 077 обнуляет в х последние 6 разрядов. Заметим, что запись х & 077 не зависит от длины слова, и, следовательно, она лучше, чем х & 0177700 , поскольку последняя подразумевает, что х занимает 16 битов. Не зависимая от машины форма записи 077 не потребует дополнительных затрат при счете, так как 077 — константное выражение, которое будет вычислено во время компиляции. Для иллюстрации некоторых побитовых операций рассмотрим функцию getbits(x, p, n) , которая формирует поле в n битов, вырезанных из х , начиная с позиции p , прижимая его к правому краю. Предполагается, что 0-й бит — крайний правый бит, а n и p — осмысленные положительные числа. Например, getbits(x, 4, 3) вернет в качестве результата 4, 3 и 2-й биты значения х , прижимая их к правому краю. Вот эта функция: /* getbits: получает п бит, начиная с р-й позиции */ unsigned getbits(unsigned х, int p, int n) { return (x >> (p+1-n)) & (0 << n); } Выражение х >> (p+1-n) сдвигает нужное нам поле к правому краю. Константа 0 состоит из одних единиц, и ее сдвиг влево на n бит (0 << n) приведет к тому, что правый край этой константы займут n нулевых разрядов. Еще одна операция побитовой инверсии позволяет получить справа n единиц. Упражнение 2.6. Напишите функцию setbits(x, p, n, y) , возвращающую значение x , в котором n битов, начиная с p -й позиции, заменены на n правых разрядов из y (остальные биты не изменяются). Упражнение 2.7. Напишите функцию invert(х, р, n) , возвращающую значение x с инвертированными n битами, начиная с позиции p (остальные биты не изменяются). Упражнение 2.8. Напишите функцию rightrot(х, n) , которая циклически сдвигает x вправо на n разрядов. 2.10. Операторы и выражения присваивания Выражение i = i + 2 в котором стоящая слева переменная повторяется и справа, можно написать в сжатом виде: i += 2 Оператор += , как и = , называется оператором присваивания. Большинству бинарных операторов (аналогичных + и имеющих левый и правый операнды) соответствуют операторы присваивания ор= , где ор — один из операторов + * / % << >> & ^ | Если выр 1 и выр 2 — выражения, то выр 1 ор= выр 2 эквивалентно выр 1 = (выр 1 ) ор (выр 2 ) с той лишь разницей, что выр 1 вычисляется только один раз. Обратите внимание на скобки вокруг выр 2 : x *= y + 1 эквивалентно x = x * (y + 1) но не x = x * y + 1 В качестве примера приведем функцию bitcount , подсчитывающую число единичных битов в своем аргументе целочисленного типа. /* bitcount: подсчет единиц в х */ int bitcount (unsigned x) { int b; for (b = 0; x != 0; x >>= 1) if (x & 01) b++; return b; } Независимо от машины, на которой будет работать эта программа, объявление аргумента x как unsigned гарантирует, что при правом сдвиге освобождающиеся биты будут заполняться нулями, а не знаковым битом. Помимо краткости операторы присваивания обладают тем преимуществом, что они более соответствуют тому, как человек мыслит. Мы говорим "прибавить 2 к i" или "увеличить i на 2", а не "взять i, добавить 2 и затем вернуть результат в i", так что выражение i += 2 лучше, чем i = i + 2 . Кроме того, в сложных выражениях вроде yyval[yypv[p3+p4] + yypv[p1+p2]] += 2 благодаря оператору присваивания += запись становится более легкой для понимания, так как читателю при такой записи не потребуется старательно сравнивать два длинных выражения, совпадают ли они, или выяснять, почему они не совпадают. Следует иметь в виду и то, что подобные операторы присваивания могут помочь компилятору сгенерировать более эффективный код. Мы уже видели, что присваивание вырабатывает значение и может применяться внутри выражения; вот самый расхожий пример: while ((с = getchar()) != EOF) … В выражениях встречаются и другие операторы присваивания ( += , -= и т.д.), хотя и реже. Типом и значением любого выражения присваивания являются тип и значение его левого операнда после завершения присваивания. Упражнение 2.9. Применительно к числам, в представлении которых использован дополнительный код, выражение х &= (х-1) уничтожает самую правую 1 в х . Объясните, почему. Используйте это наблюдение при написании более быстрого варианта функции bitcount 2.11. Условные выражения Инструкции if (а > b) z = a; else z = b; пересылают в z большее из двух значений a и b . Условное выражение, написанное с помощью тернарного (т.е. имеющего три операнда) оператора ?: , представляет собой другой способ записи этой и подобных ей конструкций. В выражении выр 1 ? выр 2 : выр 3 первым вычисляется выражение выр 1 . Если его значение не нуль (истина), то вычисляется выражение выр 2 и значение этого выражения становится значением всего условного выражения. В противном случае вычисляется выражение выр 3 и его значение становится значением условного выражения. Следует отметить, что из выражений выр 2 и выр 3 вычисляется только одно из них. Таким образом, чтобы установить в z большее из a и b , можно написать z = (a > b) ? а : b; /* z = max(a, b) */ Следует заметить, что условное выражение и в самом деле является выражением, и его можно использовать в любом месте, где допускается выражение. Если выр 2 и выр 3 принадлежат разным типам, то тип результата определяется правилами преобразования, о которых шла речь в этой главе ранее. Например, если f имеет тип float , a n — тип int , то типом выражения (n > 0) ? f : n будет float вне зависимости от того, положительно значение n или нет. Заключать в скобки первое выражение в условном выражении не обязательно, так как приоритет ?: очень низкий (более низкий приоритет имеет только присваивание), однако мы рекомендуем всегда это делать, поскольку благодаря обрамляющим скобкам условие в выражении лучше воспринимается. Условное выражение часто позволяет сократить программу. В качестве примера приведем цикл, обеспечивающий печать n элементов массива по 10 на каждой строке с одним пробелом между колонками; каждая строка цикла, включая последнюю, заканчивается символом новой строки: for (i = 0; i < n; i++) printf("%6d%c", a[i], (i%10 == 9 || i == n-1) ? 'n' : ' '); Символ новой строки посылается после каждого десятого и после n -го элемента. За всеми другими элементами следует пробел. Эта программа выглядит довольно замысловато, зато она более компактна, чем эквивалентная программа с использованием if - else . Вот еще один хороший пример 6 : printf("Вы имеете %d элемент%s.\n", n, (n%10==1 && n%100 ! = 11) ? " " : ((n%100 < 10 || n%100 > 20) && n%10 >= 2 && n%10 <= 4) ? "а" : "ов"); Упражнение 2.10. Напишите функцию lower , которая переводит большие буквы в малые, используя условное выражение (а не конструкцию if - else ). 2.12. Приоритет и очередность вычислений В таблице 2.1 показаны приоритеты и очередность вычислений всех операторов, включая и те, которые мы еще не рассматривали. Операторы, перечисленные на одной строке, имеют одинаковый приоритет; строки упорядочены по убыванию приоритетов; так, например, * , / и % имеют одинаковый приоритет, который выше, чем приоритет бинарных + и - . "Оператор" () относится к вызову функции. Операторы -> и (точка) обеспечивают доступ к элементам структур; о них пойдет речь в главе 6, там же будет рассмотрен и оператор sizeof (размер объекта). Операторы * (косвенное обращение по указателю) и & (получение адреса объекта) обсуждаются в главе 5. Оператор "запятая" будет рассмотрен в главе 3. Операторы Выполняются () [] -> слева направо ! ++ -- + - * & (тип) sizeof справа налево * / % слева направо + - слева направо << >> слева направо 6 Этот пример, учитывающий русскую грамматику, отличается от авторского оригинала. — Примеч. ред. < <= > >= слева направо == != слева направо & слева направо ^ слева направо | слева направо && слева направо || слева направо ?: справа налево = += -= *= /= %= &= ^= |= <<= >>= справа налево , слева направо Примечание. Унарные операторы + , - , * и & имеют более высокий приоритет, чем те же бинарные операторы. Заметим, что приоритеты побитовых операторов & , ^ и | ниже, чем приоритет == и != , из-за чего в побитовых проверках, таких как if ((х & MASK) == 0) … чтобы получить правильный результат, приходится использовать скобки. Си подобно многим языкам не фиксирует очередность вычисления операндов оператора (за исключением & & , || , ?: и , ). Например, в инструкции вида х = f() + g(); f может быть вычислена раньше g или наоборот. Из этого следует, что если одна из функций изменяет значение переменной, от которой зависит другая функция, то помещаемый в x результат может зависеть от очередности вычислений. Чтобы обеспечить нужную последовательность вычислений, промежуточные результаты можно запоминать во временных переменных. Очередность вычисления аргументов функции также не определена, поэтому на разных компиляторах printf("%d %d\n", ++n, power(2, n)); /* НЕВЕРНО */ может давать несовпадающие результаты. Результат вызова функции зависит от того, когда компилятор сгенерирует команды увеличения n — до или после обращения к power . Чтобы обезопасить себя от возможного побочного эффекта, достаточно написать ++n; printf("%d %d\n", n, power(2, n)); Обращения к функциям, вложенные присвоения, инкрементные и декрементные операторы дают "побочный эффект", проявляющийся в том, что при вычислении выражения значения некоторых переменных изменяются. В любом выражении с побочным эффектом может быть скрыта трудно просматриваемая зависимость результата выражения от очередности изменения значений переменных, входящих в выражение. В такой, например, типично неприятной ситуации a[i] = i++; возникает вопрос: массив a индексируется старым или измененным значением i ? Компиляторы могут по- разному генерировать программу, что проявится в интерпретации данной записи. Стандарт сознательно устроен так, что большинство подобных вопросов оставлено на усмотрение компиляторов, так как лучший порядок вычислений определяется архитектурой машины. Стандартом только гарантируется, что все побочные эффекты при вычислении аргументов проявятся перед входом в функцию. Правда, в примере с printf это нам не поможет. Мораль такова: писать программы, зависящие от очередности вычислений, — плохая практика, какой бы язык вы ни использовали. Естественно, надо знать, чего следует избегать, но если вы не знаете, как образуются побочные эффекты на разных машинах, то лучше и не рассчитывать выиграть на особенностях частной реализации. 3. Управление Порядок, в котором выполняются вычисления, определяется инструкциями управления. Мы уже встречались с наиболее распространенными управляющими конструкциями такого рода в предыдущих примерах; здесьмы завершим их список и более точно определим рассмотренные ранее. 3.1. Инструкции и блоки Выражение, скажем х = 0 , или i++ , или printf (…) , становится инструкцией, если в конце его поставить точку с запятой, например: х = 0; i++; printf (…); В Си точка с запятой является заключающим символом инструкции, а не разделителем, как в языке Паскаль. Фигурные скобки { и } используются для объединения объявлений и инструкций в составную инструкцию, или блок, чтобы с точки зрения синтаксиса эта новая конструкция воспринималась как одна инструкция. Фигурные скобки, обрамляющие группу инструкций, образующих тело функции, — это один пример; второй пример — это скобки, объединяющие инструкции, помещенные после if , else , while или for (Переменные могут быть объявлены внутри любого блока, об этом разговор пойдет в главе 4.) После правой закрывающей фигурной скобки в конце блока точка с запятой не ставится. 3.2. Конструкция if-else Инструкция if - else используется для принятия решения. Формально ее синтаксисом является: if (выражение) инструкция 1 else инструкция 2 причем else -часть может и отсутствовать. Сначала вычисляется выражение, и, если оно истинно (т. е. отлично от нуля), выполняется инструкция1. Если выражение ложно (т. е. его значение равно нулю) и существует else-часть, то выполняется инструкция2. Так как if просто проверяет числовое значение выражения, условие иногда можно записывать в сокращенном виде. Так, запись if (выражение) короче, чем if (выражение ! = 0) Иногда такие сокращения естественны и ясны, в других случаях, наоборот, затрудняют понимание программы. Отсутствие else -части в одной из вложенных друг в друга if -конструкций может привести к неоднозначному толкованию записи. Эту неоднозначность разрешают тем, что else связывают с ближайшим if , у которого нет своего else . Например, в if (n > 0) if (а > Ь) z = а; else z = b; else относится к внутреннему if , что мы и показали с помощью отступов. Если нам требуется иная интерпретация, необходимо должным образом расставить фигурные скобки: if (n > 0) { if (a > b) z = а; } else z = b; Ниже приводится пример ситуации, когда неоднозначность особенно опасна: if (n >= 0) for (i = 0; i < n; i++) if (s[i] > 0) { printf ( " . . . " ) ; return i; } else /* НЕВЕРНО */ printf("ошибка - отрицательное n\n"); С помощью отступов мы недвусмысленно показали, что нам нужно, однако компилятор не воспримет эту информацию и отнесет else к внутреннему if . Искать такого рода ошибки особенно тяжело. Здесь уместен следующий совет: вложенные if обрамляйте фигурными скобками. Кстати, обратите внимание на точку с запятой после z = а в if (a > b) z = а; else z = b; Здесь она обязательна, поскольку по правилам грамматики за if должна следовать инструкция, а выражение-инструкция вроде z = а; всегда заканчивается точкой с запятой. 3.3. Конструкция else-if Конструкция if (выражение) инструкция else if (выражение) инструкция else if (выражение) инструкция else if (выражение) инструкция else инструкция встречается так часто, что о ней стоит поговорить особо. Приведенная последовательность инструкций if — самый общий способ описания многоступенчатого принятия решения. Выражения вычисляются по порядку; как только встречается выражение со значением "истина", выполняется соответствующая ему инструкция; на этом последовательность проверок завершается. Здесь под словом инструкция имеется в виду либо одна инструкция, либо группа инструкций в фигурных скобках. Последняя else -часть срабатывает, если не выполняются все предыдущие условия. Иногда в последней части не требуется производить никаких действий, в этом случае фрагмент else инструкция можно опустить или использовать для фиксации ошибочной ("невозможной") ситуации. В качестве иллюстрации трехпутевого ветвления рассмотрим функцию бинарного поиска значения x в массиве v . Предполагается, что элементы v упорядочены по возрастанию. Функция выдает положение x в v (число в пределах от 0 до n -1 ), если x там встречается, и -1 , если его нет. При бинарном поиске значение x сначала сравнивается с элементом, занимающим серединное положение в массиве v . Если x меньше, чем это значение, то областью поиска становится "верхняя" половина массива v , в противном случае — "нижняя". В любом случае следующий шаг — это сравнение с серединным элементом отобранной половины. Процесс "уполовинивания" диапазона продолжается до тех пор, пока либо не будет найдено значение, либо не станет пустым диапазон поиска. Запишем функцию бинарного поиска: /* binsearch: найти х в v[0] <= v[1] <= … <= v[n-1] */ int binsearch(int x, int v[], int n) { int low, high, mid; low = 0; high = n - 1 ; while (low <= high) { mid = (low + high) / 2; if (x < v[mid]) high = mid - 1; else if (x > v[mid]) low = mid + 1 ; else /* совпадение найдено */ return mid; } return -1; /* совпадения нет */ } Основное действие, выполняемое на каждом шаге поиска, — сравнение значения x (меньше, больше или равно) с элементом v[mid] ; это сравнение естественно поручить конструкции else - if |