Главная · Поиск книг · Поступления книг · Top 40 · Форумы · Ссылки · Читатели

Настройка текста
Перенос строк


    Прохождения игр    
Roman legionnaire vs Knight Artorias
Ghost-Skeleton in DSR
Expedition SCP-432-4
Expedition SCP-432-3 DATA EXPUNGED

Другие игры...


liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня
Rambler's Top100
Образование - Богатырев А. Весь текст 1009.15 Kb

Хрестоматия по программированию на Си в Unix

Предыдущая страница Следующая страница
1 2 3 4 5 6  7 8 9 10 11 12 13 14 ... 87

Может быть напечатано либо 16, либо 8 в зависимости от  поведения  компилятора,  т.е.
данный оператор немобилен.  Следует написать

            y = 4;  x = y * y;

1.84.  Законен ли оператор

            f(x++, x++);   или  f(x, x++);

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

            f( c = getchar(), c );

а должны писать

            c = getchar();  f(c, c);

(если мы именно это имели в виду). Вот еще пример:

            ...
            case '+':
                    push(pop()+pop()); break;
            case '-':
                    push(pop()-pop()); break;
            ...

А. Богатырев, 1992-95                  - 37 -                               Си в UNIX

следует заменить на

            ...
            case '+':
                    push(pop()+pop()); break;
            case '-':
                    { int x = pop(); int y = pop();
                      push(y - x); break;
                    }
            ...

И еще пример:

      int x = 0;
      printf( "%d %d\n", x = 2, x );   /* 2 0 либо 2 2 */

Нельзя также

      struct pnt{ int x; int y; }arr[20]; int i=0;
      ...
      scanf( "%d%d", & arr[i].x, & arr[i++].y );

поскольку i++ может сделаться раньше, чем чтение в x.  Еще пример:

            main(){
               int i = 3;
               printf( "%d %d %d\n", i += 7, i++, i++ );
            }

который показывает, что на IBM PC [*] и PDP-11 [**] аргументы функций  вычисляются  справа
налево  (пример  печатает  12  4  3).  Впрочем, другие компиляторы могут вычислять их
слева направо (как и подсказывает нам здравый смысл).

1.85.  Программа печатает либо x=1 либо x=0 в зависимости от КОМПИЛЯТОРА  -  вычисля-
ется ли раньше правая или левая часть оператора вычитания:

    #include 
    void main(){
            int c = 1;
            int x = c - c++;

            printf( "x=%d c=%d\n", x, c );
            exit(0);
    }

Что вы имели в виду ?

    left = c; right = c++; x = left - right;
            или
    right = c++; left = c; x = left - right;

А если компилятор еще и распараллелит вычисление left и right - то одна  программа  в
разные моменты времени сможет давать разные результаты.

____________________
   [*] IBM ("Ай-би-эм") - International Buisiness Machines  Corporation.   Персональные
компьютеры IBM PC построены на базе микропроцессоров фирмы Intel.
     [**] PDP-11 - (Programmed Data Processor) - компьютер фирмы DEC (Digital  Equipment
Corporation), у нас известный как СМ-1420.  Эта же фирма выпускает машину VAX.

А. Богатырев, 1992-95                  - 38 -                               Си в UNIX

     Вот еще достойная задачка:

    x = c-- - --c;  /* c-----c */

1.86.  Напишите программу, которая устанавливает в 1 бит 3 и сбрасывает в  0  бит  6.
Биты в слове нумеруются с нуля справа налево.  Ответ:

            int x = 0xF0;

            x |=  (1 << 3);
            x &= ~(1 << 6);

В программах часто используют битовые маски как флаги некоторых параметров (признак -
есть или нет). Например:

    #define A  0x08             /* вход свободен  */
    #define B  0x40             /* выход свободен */
    установка флагов            : x |=    A|B;
    сброс флагов                : x &=  ~(A|B);
    проверка флага A            : if( x & A ) ...;
    проверка, что оба флага есть: if((x & (A|B)) == (A|B))...;
    проверка, что обоих нет     : if((x & (A|B)) == 0 )...;
    проверка, что есть хоть один: if( x & (A|B))...;
    проверка, что есть только A : if((x & (A|B)) == A)...;
    проверка, в каких флагах
      различаются x и y         : diff = x ^ y;

1.87.  В программах иногда требуется использовать "множество": каждый допустимый эле-
мент  множества  имеет номер и может либо присутствовать в множестве, либо отсутство-
вать.  Число вхождений не учитывается.  Множества  принято  моделировать  при  помощи
битовых шкал:

    #define   SET(n,a) (a[(n)/BITS] |=  (1L <<((n)%BITS)))
    #define   CLR(n,a) (a[(n)/BITS] &= ~(1L <<((n)%BITS)))
    #define ISSET(n,a) (a[(n)/BITS] &   (1L <<((n)%BITS)))
    #define BITS 8 /* bits per char (битов в байте) */
    /* Перечислимый тип */
    enum fruit { APPLE, PEAR, ORANGE=113,
                 GRAPES, RAPE=125, CHERRY};
    /* шкала:   n из интервала 0..(25*BITS)-1 */
    static char fr[25];
    main(){
      SET(GRAPES, fr);  /* добавить в множество */
      if(ISSET(GRAPES, fr)) printf("here\n");
      CLR(GRAPES, fr);  /* удалить из множества */
    }

1.88.  Напишите программу, распечатывающую все возможные перестановки  массива  из  N
элементов.  Алгоритм  будет  рекурсивным, например таким: в качестве первого элемента
перестановки взять i-ый элемент массива. Из оставшихся элементов массива (если  такие
есть)  составить  все  перестановки  порядка N-1.  Выдать все перестановки порядка N,
получающиеся склейкой i-ого элемента и всех (по очереди)  перестановок  порядка  N-1.
Взять следующее i и все повторить.
     Главная проблема здесь - организовать оставшиеся после извлечения i-ого элемента
элементы  массива  в удобную структуру данных (чтобы постоянно не копировать массив).
Можно использовать, например, битовую шкалу уже выбранных  элементов.   Воспользуемся
для этого макросами из предыдущего параграфа:

А. Богатырев, 1992-95                  - 39 -                               Си в UNIX

    /* ГЕНЕРАТОР ПЕРЕСТАНОВОК ИЗ n ЭЛЕМЕНТОВ ПО m */

    extern void *calloc(unsigned nelem, unsigned elsize);
    /* Динамический выделитель памяти, зачищенной нулями.
     * Это стандартная библиотечная функция.
     * Обратная к ней - free();
     */
    extern void free(char *ptr);
    static int N, M, number;
    static char *scale;     /* шкала выбранных элементов */
           int  *res;       /* результат */

    /* ... текст определений SET, CLR, ISSET, BITS ... */

    static void choose(int ind){
      if(ind == M){ /* распечатать перестановку */
         register i;
         printf("Расстановка #%04d", ++number);
         for(i=0; i < M; i++) printf(" %2d", res[i]);
         putchar('\n'); return;
      } else
      /* Выбрать очередной ind-тый элемент перестановки
       * из числа еще не выбранных элементов.
       */
      for(res[ind] = 0; res[ind] < N; ++res[ind])
         if( !ISSET(res[ind], scale)) {
            /* элемент еще не был выбран */
            SET(res[ind], scale);      /* выбрать */
            choose(ind+1);
            CLR(res[ind], scale);      /* освободить */
         }
    }
    void arrange(int n, int m){
      res   = (int *)  calloc(m, sizeof(int));
      scale = (char *) calloc((n+BITS-1)/BITS, 1);
      M = m; N = n; number = 0;
      if( N >= M ) choose(0);
      free((char *) res); free((char *) scale);
    }
    void main(int ac, char **av){
       if(ac != 3){ printf("Arg count\n"); exit(1); }
       arrange(atoi(av[1]), atoi(av[2]));
    }

Программа должна выдать n!/(n-m)!  расстановок, где x! = 1*2*...*x - функция  "факто-
риал".   По  определению 0! = 1.  Попробуйте переделать эту программу так, чтобы оче-
редная перестановка печаталась по запросу:

    res = init_iterator(n, m);
    /* печатать варианты, пока они есть */
    while( next_arrangement (res))
           print_arrangement(res, m);
    clean_iterator(res);

1.89.  Напишите макроопределения циклического сдвига переменной типа unsigned int  на
skew бит влево и вправо (ROL и ROR).  Ответ:

    #define BITS 16     /* пусть целое состоит из 16 бит */
    #define ROL(x,skew) x=(x<<(skew))|(x>>(BITS-(skew)))
    #define ROR(x,skew) x=(x>>(skew))|(x<<(BITS-(skew)))

А. Богатырев, 1992-95                  - 40 -                               Си в UNIX

    Вот как работает ROL(x, 2) при BITS=6
            |abcdef|        исходно
           abcdef00          << 2
             0000abcdef      >> 4
             ------         операция |
             cdefab         результат

В случае signed int потребуется накладывать маску при сдвиге вправо из-за  того,  что
левые  биты при >>>> не заполняются нулями.  Приведем пример для сдвига переменной типа
signed char (по умолчанию все char - знаковые) на 1 бит влево:

    #define CHARBITS 8
    #define ROLCHAR1(x) x=(x<<1)|((x>>(CHARBITS-1)) & 01)
         соответственно для сдвига
    на 2 бита надо делать &  03
    на 3                  &  07
    на 4                  & 017
    на skew               & ~(~0 << skew)

1.90.  Напишите программу, которая инвертирует (т.е. заменяет 1 на 0  и  наоборот)  N
битов,  начинающихся  с  позиции  P,  оставляя  другие биты без изменения.  Возможный
ответ:

    unsigned x, mask;
    mask = ~(~0 << N) << P;
    x = (x & ~mask) | (~x & mask);
                 /*   xnew   */

Где маска получается так:

      ~0            = 11111....11111
      ~0 << N       = 11111....11000  /* N нулей */
    ~(~0 << N)      = 00000....00111  /* N единиц */
    ~(~0 << N) << P = 0...01110...00
    /* N единиц на местах P+N-1..P */

1.91.  Операции умножения * и деления / и % обычно достаточно медленны.  В  критичных
по  скорости  функциях  можно  предпринять  некоторые ручные оптимизации, связанные с
представлением чисел в двоичном коде (хороший компилятор делает это сам!) - пользуясь
тем, что операции +, &, >>>> и <<<< гораздо быстрее.  Пусть у нас есть

    unsigned int x;

(для signed операция >>>> может не заполнять освобождающиеся левые биты нулем!) и  2**n
означает 2 в степени n.  Тогда:

    x * (2**n)  = x << n
    x / (2**n)  = x >> n
    x % (2**n)  = x - ((x >> n) << n)
    x % (2**n)  = x & (2**n - 1)
                  это  11...111  n двоичных единиц

Например:

А. Богатырев, 1992-95                  - 41 -                               Си в UNIX

    x * 8   = x << 3;
    x / 8   = x >> 3; /* деление нацело     */
    x % 8   = x &  7; /* остаток от деления */
    x * 80  = x*64 + x*16  = (x << 6) + (x << 4);
    x * 320 = (x * 80) * 4 = (x * 80) << 2 =
                             (x << 8) + (x << 6);
    x * 21  = (x << 4) + (x << 2) + x;

    x & 1   = x % 2 = четное(x)? 0:1 = нечетное(x)? 1:0;

    x & (-2) = x & 0xFFFE = | если x = 2*k      то 2*k
                            | если x = 2*k + 1  то 2*k
                            | то есть округляет до четного

Или формула для вычисления количества дней в году (високосный/простой):

    days_in_year = (year % 4 == 0) ? 366 : 365;
            заменяем на
    days_in_year = ((year & 0x03) == 0) ? 366 : 365;

Вот еще одно полезное равенство:

    x = x & (a|~a) = (x & a) | (x & ~a) = (x&a) + (x&~a)
            из чего вытекает, например
    x - (x % 2**n) = x - (x &  (2**n - 1)) =
                   =      x & ~(2**n - 1)  = (x>>n) << n
    x - (x%8) = x-(x&7) = x & ~7

Последняя строка может быть использована в функции untab() в главе  "Текстовая  обра-
ботка".

1.92.  Обычно мы вычисляем min(a,b) так:

    #define min(a, b) (((a) < (b)) ? (a) : (b))

или более развернуто

    if(a < b) min = a;
    else      min = b;

Здесь есть операция сравнения и условный переход.  Однако, если (a < b)  эквивалентно
условию (a - b) < 0, то мы можем избежать сравнения.  Это предположение верно при

    (unsigned int)(a - b) <= 0x7fffffff.

что, например, верно если a и b - оба неотрицательные числа  между  0  и  0x7fffffff.
При этих условиях

    min(a, b) = b + ((a - b) & ((a - b) >> 31));

Как это работает?  Рассмотрим два случая:

А. Богатырев, 1992-95                  - 42 -                               Си в UNIX

    Случай 1: a < b

            Здесь (a - b) < 0, поэтому старший (левый, знаковый) бит
            разности (a - b) равен 1.
            Следовательно, (a - b) >> 31 == 0xffffffff,
            и мы имеем:

            min(a, b)       = b + ((a - b) & ((a - b) >> 31))
Предыдущая страница Следующая страница
1 2 3 4 5 6  7 8 9 10 11 12 13 14 ... 87
Ваша оценка:
Комментарий:
  Подпись:
(Чтобы комментарии всегда подписывались Вашим именем, можете зарегистрироваться в Клубе читателей)
  Сайт:
 

Реклама