2. comp
  3. Глава 2. Типы, операторы и выражения

Глава 2. Типы, операторы и выражения

Date Редакция Категория comp Теги C / K&R

Начнем со справочных данных, которые пригодятся нам при решении задач.

Полный набор эскейп-последовательностей:

последовательность значение
\а сигнал-звонок
\b возврат-на-шаг (забой)
\f перевод-страницы
\n новая-строка
\r возврат-каретки
\t горизонтальная-табуляция
\v вертикальная-табуляция
\ обратная наклонная черта
\? знак вопроса
\' одиночная кавычка
\" двойная кавычка
\ooo восьмеричный код
\xhh шестнадцатеричный код

Таблица 2.1. Приоритеты и очередность вычислений операторов

операторы выполняются
(), [], ->, . слева направо
!, ~, ++, --, +, -, *, &, (type), sizeof справа налево
*, /, % слева направо
+, - слева направо
<<, >> слева направо
<, <=, >, >= слева направо
==, != слева направо
& слева направо
^ слева направо
| слева направо
&& слева направо
|| слева направо
? : справа налево
=, +=, -=, *=, /=, %=, &=, ^=, |=, <<=, >>= справа налево
, слева направо

Упражнение 2.1. Напишите программу, которая будет выдавать диапазоны значений типов char, short, int и long, описанных как signed и как unsigned, с помощью печати соответствующих значений из стандартных заголовочных файлов и путем прямого вычисления. Определите диапазоны чисел с плавающей точкой различных типов. Вычислить эти диапазоны сложнее.

Начнем с целых чисел и использования значений из заголовочных файлов, а конкретно из limits.h:

  #include <stdio.h>
  #include <limits.h>

  int main()
  {
      printf("Integer datatypes:\n");
      printf("%d <= char <= %d\n", CHAR_MIN, CHAR_MAX);
      printf("%d <= int <= %d\n", INT_MIN, INT_MAX);
      printf("%ld <= long <= %ld\n", LONG_MIN, LONG_MAX);
      printf("%d <= signed char <= %d\n", SCHAR_MIN, SCHAR_MAX);
      printf("%d <= short <= %d\n", SHRT_MIN, SHRT_MAX);
      printf("0 <= unsigned char <= %d\n", UCHAR_MAX);
      printf("0 <= unsigned int <= %u\n", UINT_MAX);
      printf("0 <= unsigned long <= %lu\n", ULONG_MAX);
      printf("0 <= unsigned short <= %d\n", USHRT_MAX);
      return 0;
  }

Все так просто, что нечего и комментировать. У меня получилось вот что:

timespan0.png

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

Идея такая: будем увеличивать переменную x заданного типа до тех пор, пока она не станет бесконечностью, т. е. для нее перестанут выполняться элементарные арифметические правила, например, x > x - 1.

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

Ну что ж, нам это не помешает:

  #include <stdio.h>

  int main()
  {
      short x;

      for (x = 1; x > x-1; ++x) {
          if (x < 0)
              break;
          printf("%d\n", x); // печатаем для отладки программы
      }
      printf("MIN: %d\n", x);
      printf("MAX: %d\n", --x);
      return 0;
  }

В результате получим:

timespan10.png

Перейдем к вещественным типам. Начнем с использования констант из float.h:

  #include <stdio.h>
  #include <float.h>

  int main()
  {
      printf("Float datatypes:\n");
      printf("%e <= float <= %e\n", FLT_MIN, FLT_MAX);
      printf("%e <= double <= %e\n", DBL_MIN, DBL_MAX);
      return 0;
  }

timespan20.png

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

  #include <stdio.h>

  int main()
  {
      float x;

      for (x = 1; x > x/2; x *= 2 ) {
          printf("%e\n", x);
      }
      return 0;
  }

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

Вот что мы получаем:

timespan30.png

Мы можем заменить шаг x = 2 на меньший (например, x = 1.01): точность расчета границы будет выше, но сам расчте будет длиться дольше.

Упражнение 2.2. Напишите цикл, эквивалентный приведенному выше for-циклу, не пользуясь операторами && и ||.

Цикл, о котором идет речь, выглядит так:

  for (i = 0; i < lim-1 && (с = getchar()) != EOF && с != '\n'; ++i)
      s[i] = c;

Он уже знаком нам по функции getl() (или getline()) из главы 1.

Исходный вариант, с &&:

  #include <stdio.h>

  int lim = 10;

  int main()
  {
      int i, c;
      char s[lim];

      for (i = 0; i < lim-1 && (c = getchar()) != EOF && c != '\n'; ++i)
          s[i] = c;

      s[i] = '\0';

      printf("%s", s);
      return 0;
  }

Удобнее использовать while:

  #include <stdio.h>

  int lim = 10;

  int main()
  {
      int i, c;
      char s[lim];

      i = 0;
      while (i < lim-1) {
          c = getchar();
          if (c == EOF)
              break;
          if (c == '\n')
              break;
          s[i++] = c;
      }
      s[i] = '\0';

      printf("%s", s);

      return 0;
  }

Не удалось обойтись без break'ов, которых мы к этому месту книги еще не знаем. У меня были и другие варианты решения, но они также требовали "незнакомых" конструкций. Приведенный вариант -- самый прямолинейный.

Упражнение 2.3. Напишите функцию htoi(s), которая преобразует последовательность шестнадцатеричных цифр, начинающуюся с 0x или 0X, в соответствующее целое. Шестнадцатеричными цифрами являются символы 0...9, a...f, А...F.

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

Разобьем задачу на части. Пусть вначале шестнадцатиричное число в строковой форме состоит лишь из чисел 0...9. В этом случае разрабатываемая функция будет похожа на имеющуюся в учебнике atoi(). Кроме того нам надо проверить корректность задания 16-ричного числа (оно должно начинаться с 0x или 0X, внутри числа этих символов быть не может) и позаботиться о его выводе.

  #include <stdio.h>

  int htoi(char m[]);

  int main()
  {
      int n;
      char s[] = "0x20\0";

      n = htoi(s);
      printf("%x", n);

      return 0;
  }

  /* htoi: преобразование hex в целое */
  int htoi(char s[])
  {   
      int i = 0;
      int answer = 0;
      int valid = 1;

      if(s[i] == '0') {
          ++i;
          if(s[i] == 'x' || s[i] == 'X') {
              ++i;
          }
          else
              valid = 0;
      }    
      else
          valid = 0;

      while(valid && s[i] != '\0') {
          answer = answer * 16;
          if(s[i] >= '0' && s[i] <= '9') {
              answer = answer + (s[i] - '0');
          }
          ++i;
      }

      if(!valid) {
          printf("The string isn't valid hex numbern");
          answer = 0;
      }

      return answer;
  }

Для корректно заданного числа valid=1, иначе выдается сообщение об ошибке. Вывод 16-ричного числа оргазован с помощью форматного спецификатора %x.

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

  #include <stdio.h>

  int htoi(char m[]);
  int lower(int c);
  int hex_a_f_to_int(int c);

  int main()
  {
      int n;
      char s[] = "0xb1A\0";

      n = htoi(s);
      printf("%x", n);

      return 0;
  }

  /* htoi: преобразование hex в целое */
  int htoi(char s[])
  {   
      int i = 0;
      int answer = 0;
      int valid = 1;
      int hex_a_f;

      if(s[i] == '0') {
          ++i;
          if(s[i] == 'x' || s[i] == 'X') {
              ++i;
          }
          else
              valid = 0;
      }    
      else
          valid = 0;

      while(valid && s[i] != '\0') {
          answer = answer * 16;
          if(s[i] >= '0' && s[i] <= '9') {
              answer = answer + (s[i] - '0');
          }
          else {
              s[i] = lower(s[i]);
              hex_a_f = hex_a_f_to_int(s[i]);
              if (hex_a_f == 0) {
                  valid = 0;
              }
              else {
                  answer = answer + hex_a_f;
              }
          }
          ++i;
      }

      if(!valid) {
          printf("The string isn't valid hex numbern");
          answer = 0;
      }

      return answer;
  }

  /* lower: преобразование прописных c в строчные, только для ASCII */
  int lower(int c)
  {
      if (c >= 'A' && c <='Z')
          return c +'a'-'A';
      else
          return c;
  }

  /* hex_a_f_to_int: преобразование a-f в соответствующие целые числа */
  int hex_a_f_to_int(int c)
  {
      char hex_a_f[] = "abcdef";
      int i;
      int answer = 0;

      for(i = 0; answer == 0 && hex_a_f[i] != '\0'; i++) {
          if(hex_a_f[i] == c) {
              answer = 10 + i;
          }
      }

      return answer;
  }

Упражнение 2.4. Напишите версию функции squeeze(s1,s2), которая удаляет из s1 все символы, встречающиеся в строке s2.

  #include <stdio.h>

  int len;

  void squeeze(char s1[], char s2[]);
  int strlen(char s[]);

  int main()
  {
      char s1[] = "BHiartpphdayy\0";
      printf("s1 = %s\n", s1);

      char s2[] = "Happy\0";
      printf("s2 = %s\n", s2);
      len = strlen(s2);

      squeeze(s1, s2);
      printf("new s1 = %s\n", s1);

      return 0;
  }

  /* squeeze: удаляет все символы s2 из s1*/
  void squeeze(char s1[], char s2[])
  {
      int i, j, k;
      for (i = j = 0; s1[i] != '\0'; i++) {
          for (k = 0; s2[k] != s1[i] && s2[k] != '\0'; k++);
          if (k == len)
              s1[j++] = s1[i];
      }
      s1[j] = '\0';
  }

  /* strlen: возвращает длину строки s */
  int strlen(char s[])
  {
      int i;
      i = 0;
      while (s[i] != '\0')
          ++i;
      return i;
  }

Для вычисление длины строки мы воспользовались strlen(), приведенной в п. 2.3

Результат:

squeeze0.png

Упражнение 2.5. Напишите функцию any(s1,s2), которая возвращает либо ту позицию в s1, где стоит первый символ, совпавший с любым из символов в s2, либо -1 (если ни один символ из s1 не совпадает с символами из s2). (Стандартная библиотечная функция strpbrk делает то же самое, но выдает не номер позиции символа, а указатель на символ.)

  #include <stdio.h>

  int any(char s1[], char s2[]);
  int strlen(char s[]);

  int main()
  {
      char s1[] = "test string\0";
      printf("s1 = %s\n\n", s1);   
      char s2[] = "ring\0";
      printf("s2 = %s\n", s2);
      printf("position of first occurrence = %d\n", any(s1, s2));

      return 0;
  }

  /* any: возвращает индекс первого вхождения символа из s2 в s1*/
  int any(char s1[], char s2[])
  {
      int i, j, k;
      int len = strlen(s1);
      int first = len;

      for (i = j = 0; s1[i] != '\0'; i++)
          for (k = 0; s2[k] != '\0'; k++)
              if (s2[k] == s1[i] && i < first)
                  first = i;
      if (first == len)
          first = -1;

      return first;
  }

strlen() осталась без изменений. Получаем:

any0.png

Упражнение 2.6. Напишите функцию setbits(x, p, n, y), возвращающую значение x, в котором n битов, начиная с p-й позиции, заменены на n правых разрядов из y (остальные биты не изменяются).

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

  /* printfbit: выводит число в двоичном представлении */
  void printfbit(unsigned n)
  {
      int i;
      for(i = 7; i >= 0; --i) {
          printf("%d", (n >> i) & 1);
      }
      printf("\n");
  }

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

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

К результату лучше идти по частям, выводя получившееся на экран. Здесь и пригодится printfbit(). Итак:

  1. Готовим маску из 1 для сохранения левой части x: (~0 << (p+1))
  2. Сохраняем биты из левой части x: (~0 << (p+1)) & x )
  3. Готовим маску для сохранения правой части x: ~(~0 << (p+1-n))
  4. Сохраняем биты из правой части x: ( ~(~0 << (p+1-n)) & x )
  5. Готовим маску для сохранения n правых битов из y: ~(~0 << n)
  6. Сохраняем n правых битов y: (~(~0 << n) & y)
  7. Сдвигаем сохраненные биты y так, чтобы они оказались "напротив" нулей (места рассматриваемой подстроки) x: (~(~0 << n) & y) << (p+1-n)

А теперь -- все вместе:

  #include <stdio.h>

  unsigned setbits(unsigned x, int p, int n, unsigned y);
  void printfbit(unsigned n);

  int main()
  {
      printf("76543210\n\n");

      unsigned c1 = 'f';
      printfbit(c1);

      unsigned c2 = 'z';
      printfbit(c2);

      printfbit(setbits(c1, 5, 3, c2));

      return 0;
  }

  /* setbits: x получает n правых бит из y, начиная с p-й позиции */
  unsigned setbits(unsigned x, int p, int n, unsigned y)
  {
      return ( (~0 << (p+1)) & x ) | ( ~(~0 << (p+1-n)) & x ) | 
              (~(~0 << n) & y) << (p+1-n);
  }

Здесь '\' -- символ разрыва строки. У меня в коде вики он не отобразился, но у вас-то получится!

Получаем:

setbits0.png

Первая строка вывода -- номера битов, вторая -- строка x, третья -- y, четвертая -- результат замены.

Упражнение 2.7. Напишите функцию invert(x, p, n), возвращающую значение x с инвертированными n битами, начиная с позиции p (остальные биты не изменяются).

  #include <stdio.h>

  unsigned invert(unsigned x, int p, int n);
  void printfbit(unsigned n);

  int main()
  {
      printf("76543210\n\n");

      unsigned c = 'f';
      printfbit(c);

      printfbit(invert(c, 5, 3));

      return 0;
  }

  /* invert: инвертирует n бит из x, начиная с p-й позиции */
  unsigned invert(unsigned x, int p, int n)
  {
      return ( ((~x >> (p+1-n)) & ~(~0 << n)) << (p+1-n) ) | 
              (~( ((~0 >> (p+1-n)) & ~(~0 << n)) << (p+1-n) ) & x);
  }

Результат:

invert0.png

Упражнение 2.8. Напишите функцию rightrot (x, n), которая циклически сдвигает x вправо на n разрядов.

  #include <stdio.h>

  unsigned rightrot(unsigned x, int n);
  void printfbit(unsigned n);

  int main()
  {
      printf("76543210\n\n");

      unsigned c = 'f';
      printfbit(c);

      printfbit(rightrot(c, 3));

      return 0;
  }

  /* rightrot: сдвиг x на n вправо */
  unsigned rightrot(unsigned x, int n)
  {
      return ((~(~0 << n) & x) << (8-n)) | x >> n;
  }

В rightrot() явно вписано число бит (8), что не есть хорошо. В unsigned целом их больше, как видно хотя бы из упражнения 2.1. Но -- так проще ибо во всех рассмотренных задачах я работая только с одним битом.

Результат циклического сдвига на 3 бита вправо -- во второй строке:

rightrot0.png

Упражнение 2.9. Применительно к числам, в представлении которых использован дополнительный код, выражение x &= (x-1) уничтожает самую правую единицу в x. Объясните, почему. Используйте это наблюдение при написании более быстрого варианта функции bitcount.

Исходный bitcount() выглядит так:

  /* bitcount: подсчет единиц в х */
  int bitcount(unsigned x)
  {
      int b;
      for (b = 0; x != 0; x >>= 1)
          if (x & 01)
              b++; 
     return b;
  }

Объяснение. Если х нечетно, то (х-1) имеет такое же битовое представление как и х, за исключением того, что крайний правый бит в нем равен 0. В этом случае (х & (х-1)) == (х-1). Если же х четно, то в представлении (х-1) нули, стоявшие в х справа становятся единицами, а крайняя правая единица -- нулем. Конъюнкция х & (х-1) очищает эти позиции вплоть до того места, когда встретит единицы в представлениях обоих чисел (т.е. единицу, бывшую в x до этого шага второй справа).

Новая версия bitcount():

  int bitcount(unsigned x)
  {
      int b;
      for (b = 0; x != 0; x &= (x-1))
          b++;
      return b;
  }

bitcount0.png

Упражнение 2.10. Напишите функцию lower, которая переводит большие буквы в малые, используя условное выражение (а не конструкцию if-else).

  #include <stdio.h>

  int lower(int c);

  int main()
  {
      int i;

      char s[] = "ABRAKADABRA\0";
      printf("s = %s\n", s);

      printf("lower s = "); 
      for (i = 0; s[i] != '\0'; i++)
          printf("%c", lower(s[i]));
      printf("\n");

      return 0;
  }

  /* lower: преобразование прописных c в строчные, только для ASCII */
  int lower(int c)
  {
      return (c >= 'A' && c <='Z') ? c +'a'-'A' : c;
  }

lower0.png

Комментарии

comments powered by Disqus