Страница:
меньше 256. Следующим шагом выполняется ch++, и ch становится равно 0, ибо для char
А. Богатырев, 1992-95 - 32 - Си в UNIX
вычисления ведутся по модулю 256 (2 в 8 степени). То есть в данном случае 255+1=0
Решений существует два: первое - превратить unsigned char в int. Второе - вста-
вить явную проверку на последнее значение диапазона.
int main(int ac, char *av[]){
unsigned char ch;
for(ch=0; ; ch++){
printf("%d\n", ch);
if(ch == 255) break;
}
return 0;
}
1.73. Подумайте, почему для
unsigned a, b, c;
a < b + c не эквивалентно a - b < c
(первое - более корректно). Намек в виде примера (он выполнялся на 32-битной машине):
a = 1; b = 3; c = 2;
printf( "%u\n", a - b ); /* 4294967294, хотя в
нормальной арифметике 1 - 3 = -2 */
printf( "%d\n", a < b + c ); /* 1 */
printf( "%d\n", a - b < c ); /* 0 */
Могут ли unsigned числа быть отрицательными?
1.74. Дан текст:
short x = 40000;
printf("%d\n", x);
Печатается -25536. Объясните эффект. Указание: каково наибольшее представимое корот-
кое целое (16 битное)? Что на самом деле оказалось в x? (лишние слева биты - обруба-
ются).
1.75. Почему в примере
double x = 5 / 2;
printf( "%g\n", x );
значение x равно 2 а не 2.5 ?
Ответ: производится целочисленное деление, затем в присваивании целое число 2
приводится к типу double. Чтобы получился ответ 2.5, надо писать одним из следующих
способов:
double x = 5.0 / 2;
x = 5 / 2.0;
x = (double) 5 / 2;
x = 5 / (double) 2;
x = 5.0 / 2.0;
то есть в выражении должен быть хоть один операнд типа double.
Объясните, почему следующие три оператора выдают такие значения:
А. Богатырев, 1992-95 - 33 - Си в UNIX
double g = 9.0;
int t = 3;
double dist = g * t * t / 2; /* 40.5 */
dist = g * (t * t / 2); /* 36.0 */
dist = g * (t * t / 2.0); /* 40.5 */
В каких случаях деление целочисленное, в каких - вещественное? Почему?
1.76. Странслируйте пример на машине с длиной слова int равной 16 бит:
long n = 1024 * 1024;
long nn = 512 * 512;
printf( "%ld %ld\n", n, nn );
Почему печатается 0 0 а не 1048576 262144?
Ответ: результат умножения (2**20 и 2**18) - это целое число; однако оно слишком
велико для сохранения в 16 битах, поэтому старшие биты обрубаются. Получается 0.
Затем в присваивании это уже обрубленное значение приводится к типу long (32 бита) -
это все равно будет 0.
Чтобы получить корректный результат, надо чтобы выражение справа от = уже имело
тип long и сразу сохранялось в 32 битах. Для этого оно должно иметь хоть один операнд
типа long:
long n = (long) 1024 * 1024;
long nn = 512 * 512L;
1.77. Найдите ошибку в операторе:
x - = 4; /* вычесть из x число 4 */
Ответ: между `-' и `=' не должно быть пробела. Операция вида
x @= expr;
означает
x = x @ expr;
(где @ - одна из операций + - * / % ^ >> << & |), причем x здесь вычисляется единст-
венный раз (т.е. такая форма не только короче и понятнее, но и экономичнее).
Однако имеется тонкое отличие a=a+n от a+=n; оно заключается в том, сколько раз
вычисляется a. В случае a+=n единожды; в случае a=a+n два раза.
А. Богатырев, 1992-95 - 34 - Си в UNIX
#include <stdio.h>
static int x = 0;
int *iaddr(char *msg){
printf("iaddr(%s) for x=%d evaluated\n", msg, x);
return &x;
}
int main(){
static int a[4];
int *p, i;
printf( "1: "); x = 0; (*iaddr("a"))++;
printf( "2: "); x = 0; *iaddr("b") += 1;
printf( "3: "); x = 0; *iaddr("c") = *iaddr("d") + 1;
for(i=0, p = a; i < sizeof(a)/sizeof(*a); i++) a[i] = 0;
*p++ += 1;
for(i=0; i < sizeof(a)/sizeof(*a); i++)
printf("a[%d]=%d ", i, a[i]);
printf("offset=%d\n", p - a);
for(i=0, p = a; i < sizeof(a)/sizeof(*a); i++) a[i] = 0;
*p++ = *p++ + 1;
for(i=0; i < sizeof(a)/sizeof(*a); i++)
printf("a[%d]=%d ", i, a[i]);
printf("offset=%d\n", p - a);
return 0;
}
Выдача:
1: iaddr(a) for x=0 evaluated
2: iaddr(b) for x=0 evaluated
3: iaddr(d) for x=0 evaluated
iaddr(c) for x=0 evaluated
a[0]=1 a[1]=0 a[2]=0 a[3]=0 offset=1
a[0]=1 a[1]=0 a[2]=0 a[3]=0 offset=2
Заметьте также, что
a[i++] += z;
это
a[i] = a[i] + z; i++;
а вовсе не
a[i++] = a[i++] + z;
1.78. Операция y = ++x; эквивалентна
y = (x = x+1, x);
а операция y = x++; эквивалентна
y = (tmp = x, x = x+1, tmp);
или
y = (x += 1) - 1;
где tmp - временная псевдопеременная того же типа, что и x. Операция `,' выдает
А. Богатырев, 1992-95 - 35 - Си в UNIX
значение последнего выражения из перечисленных (подробнее см. ниже).
Пусть x=1. Какие значения будут присвоены x и y после выполнения оператора
y = ++x + ++x + ++x;
1.79. Пусть i=4. Какие значения будут присвоены x и i после выполнения оператора
x = --i + --i + --i;
1.80. Пусть x=1. Какие значения будут присвоены x и y после выполнения оператора
y = x++ + x++ + x++;
1.81. Пусть i=4. Какие значения будут присвоены i и y после выполнения оператора
y = i-- + i-- + i--;
1.82. Корректны ли операторы
char *p = "Jabberwocky"; char s[] = "0123456789?";
int i = 0;
s[i] = p[i++]; или *p = *++p;
или s[i] = i++;
или даже *p++ = f( *p );
Ответ: нет, стандарт не предусматривает, какая из частей присваивания вычисляется
первой: левая или правая. Поэтому все может работать так, как мы и подразумевали, но
может и иначе! Какое i используется в s[i]: 0 или уже 1 (++ уже сделан или нет), то
есть
int i = 0; s[i] = i++; это
s[0] = 0; или же s[1] = 0; ?
Какое p будет использовано в левой части *p: уже продвинутое или старое? Еще более
эта идея драматизирована в
s[i++] = p[i++];
Заметим еще, что в
int i=0, j=0;
s[i++] = p[j++];
такой проблемы не возникает, поскольку индексы обоих в частях присваивания незави-
симы. Зато аналогичная проблема встает в
if( a[i++] < b[i] )...;
Порядок вычисления операндов не определен, поэтому неясно, что будет сделано прежде:
взято значение b[i] или значение a[i++] (тогда будет взято b[i+1] ). Надо писать
так, чтобы не полагаться на особенности вашего компилятора:
if( a[i] < b[i+1] )...; или *p = *(p+1);
i++; ++p;
А. Богатырев, 1992-95 - 36 - Си в UNIX
Твердо усвойте, что i++ и ++i не только выдают значения i и i+1 соответственно,
но и изменяют значение i. Поэтому эти операторы НЕ НАДО использовать там, где по
смыслу требуется i+1, а не i=i+1. Так для сравнения соседних элементов массива
if( a[i] < a[i+1] ) ... ; /* верно */
if( a[i] < a[++i] ) ... ; /* неверно */
1.83. Порядок вычисления операндов в бинарных выражениях не определен (что раньше
вычисляется - левый операнд или же правый ?). Так пример
int f(x,s) int x; char *s;
{ printf( "%s:%d ", s, x ); return x; }
main(){
int x = 1;
int y = f(x++, "f1") + f(x+=2, "f2");
printf("%d\n", y);
}
может печатать либо
f1:1 f2:4 5
либо
f2:3 f1:3 6
в зависимости от особенностей поведения вашего компилятора (какая из двух f() выпол-
нится первой: левая или правая?). Еще пример:
int y = 2;
int x = ((y = 4) * y );
printf( "%d\n", x );
Может быть напечатано либо 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 <stdio.h>
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))
= b + ((a - b) & (0xffffffff))
= b + (a - b)
= a
что корректно.
Случай 2: a >= b
Здесь (a - b) >= 0, поэтому старший бит разности
(a - b) равен 0. Тогда (a - b) >> 31 == 0, и мы имеем:
min(a, b) = b + ((a - b) & ((a - b) >> 31))
= b + ((a - b) & (0x00000000))
= b + (0)
= b
что также корректно.
Статья предоставлена by Jeff Bonwick.
1.93. Есть ли быстрый способ определить, является ли X степенью двойки? Да, есть.
int X является степенью двойки
тогда и только тогда, когда
(X & (X - 1)) == 0
(в частности 2 здесь окажется степенью двойки). Как это работает? Пусть X != 0. Если
X - целое, то его двоичное представление таково:
X = bbbbbbbbbb10000...
где 'bbb' представляет некие биты, '1' - младший бит, и все остальные биты правее -
нули. Поэтому:
X = bbbbbbbbbb10000...
X - 1 = bbbbbbbbbb01111...
------------------------------------
X & (X - 1) = bbbbbbbbbb00000...
Другими словами, X & (X-1) имеет эффект обнуления последнего единичного бита. Если X
- степень двойки, то он содержит в двоичном представлении ровно ОДИН такой бит, поэ-
тому его гашение обращает результат в ноль. Если X - не степень двойки, то в слове
есть хотя бы ДВА единичных бита, поэтому X & (X-1) должно содержать хотя бы один из
оставшихся единичных битов - то есть не равняться нулю.
Следствием этого служит программа, вычисляющая число единичных битов в слове X:
int popc;
for (popc = 0; X != 0; X &= X - 1)
popc++;
При этом потребуется не 32 итерации (число бит в int), а ровно столько, сколько еди-
ничных битов есть в X. Статья предоставлена by Jeff Bonwick.
А. Богатырев, 1992-95 - 43 - Си в UNIX
1.94. Функция для поиска номера позиции старшего единичного бита в слове. Использу-
ется бинарный поиск: позиция находится максимум за 5 итераций (двоичный логарифм
32х), вместо 32 при линейном поиске.
int highbit (unsigned int x)
{
int i;
int h = 0;
for (i = 16; i >= 1; i >>= 1) {
if (x >> i) {
h += i;
x >>= i;
}
}
return (h);
}
Статья предоставлена by Jeff Bonwick.
1.95. Напишите функцию, округляющую свой аргумент вниз до степени двойки.
#include <stdio.h>
#define INT short
#define INFINITY (-999)
/* Функция, выдающая число, являющееся округлением вниз
* до степени двойки.
* Например:
* 0000100010111000110
* заменяется на
* 0000100000000000000
* то есть остается только старший бит.
* В параметр power2 возвращается номер бита,
* то есть показатель степени двойки. Если число == 0,
* то эта степень равна минус бесконечности.
*/
А. Богатырев, 1992-95 - 44 - Си в UNIX
unsigned INT round2(unsigned INT x, int *power2){
/* unsigned - чтобы число рассматривалось как
* битовая шкала, а сдвиг >> заполнял левые биты
* нулем, а не расширял вправо знаковый бит.
* Идея функции: сдвигать число >> пока не получится 1
* (можно было бы выбрать 0).
* Затем сдвинуть << на столько же разрядов, при этом все правые
* разряды заполнятся нулем, что и требовалось.
*/
int n = 0;
if(x == 0){
*power2 = -INFINITY; return 0;
}
if(x == 1){
*power2 = 0; return 1;
}
while(x != 1){
x >>= 1;
n++;
if(x == 0 || x == (unsigned INT)(-1)){
printf("Вижу %x: похоже, что >> расширяет знаковый бит.\n"
"Зациклились!!!\n", x);
return (-1);
}
}
x <<= n;
*power2 = n; return x;
}
int counter[ sizeof(unsigned INT) * 8];
int main(void){
unsigned INT i;
int n2;
for(i=0; ; i++){
round2(i, &n2);
if(n2 == -INFINITY) continue;
counter[n2]++;
/* Нельзя писать for(i=0; i < (unsigned INT)(-1); i++)
* потому что такой цикл бесконечен!
*/
if(i == (unsigned INT) (-1)) break;
}
for(i=0; i < sizeof counter/sizeof counter[0]; i++)
printf("counter[%u]=%d\n", i, counter[i]);
return 0;
}
1.96. Если некоторая вычислительная функция будет вызываться много раз, не следует
пренебрегать возможностью построить таблицу решений, где значение вычисляется один
раз для каждого входного значения, зато потом берется непосредственно из таблицы и не
вычисляется вообще. Пример: подсчет числа единичных бит в байте. Напоминаю: байт
состоит из 8 бит.
А. Богатырев, 1992-95 - 45 - Си в UNIX
#include <stdio.h>
int nbits_table[256];
int countBits(unsigned char c){
int nbits = 0;
int bit;
for(bit = 0; bit < 8; bit++){
if(c & (1 << bit))
nbits++;
}
return nbits;
}
void generateTable(){
int c;
for(c=0; c < 256; c++){
nbits_table[ (unsigned char) c ] = countBits(c);
/* printf("%u=%d\n", c, nbits_table[ c & 0377 ]); */
}
}
int main(void){
int c;
unsigned long bits = 0L;
unsigned long bytes = 0L;
generateTable();
while((c = getchar()) != EOF){
bytes++;
bits += nbits_table[ (unsigned char) c ];
}
printf("%lu байт\n", bytes);
printf("%lu единичных бит\n", bits);
printf("%lu нулевых бит\n", bytes*8 - bits);
return 0;
}
1.97. Напишите макрос swap(x, y), обменивающий значениями два своих аргумента типа
int.
#define swap(x,y) {int tmp=(x);(x)=(y);(y)=tmp;}
... swap(A, B); ...
Как можно обойтись без временной переменной? Ввиду некоторой курьезности последнего
способа, приводим ответ:
int x, y; /* A B */
x = x ^ y; /* A^B B */
y = x ^ y; /* A^B A */
x = x ^ y; /* B A */
Здесь используется тот факт, что A^A дает 0.
1.98. Напишите функцию swap(x, y) при помощи указателей. Заметьте, что в отличие от
макроса ее придется вызывать как
А. Богатырев, 1992-95 - 46 - Си в UNIX
... swap(&A, &B); ...
Почему?
1.99. Пример объясняет разницу между формальным и фактическим параметром. Термин
"формальный" означает, что имя параметра можно произвольно заменить другим (во всем
теле функции), т.е. само имя не существенно. Так
f(x,y) { return(x + y); } и
f(муж,жена) { return(муж + жена); }
воплощают одну и ту же функцию. "Фактический" - означает значение, даваемое пара-
метру в момент вызова функции:
f(xyz, 43+1);
В Си это означает, что формальным параметрам (в качестве локальных переменных) прис-
ваиваются начальные значения, равные значениям фактических параметров:
x = xyz; y = 43 + 1; /*в теле ф-ции их можно менять*/
При выходе из функции формальные параметры (и локальные переменные) разопределяются
(и даже уничтожаются, см. следующий параграф). Имена формальных параметров могут
"перекрывать" (делать невидимыми, override) одноименные глобальные переменные на
время выполнения данной функции.
Что печатает программа?
char str[] = "строка1";
char lin[] = "строка2";
f(str) char str[]; /* формальный параметр. */
{ printf( "%s %s\n", str, str ); }
main(){
char *s = lin;
/* фактический параметр: */
f(str); /* массив str */
f(lin); /* массив lin */
f(s); /* переменная s */
f("строка3"); /* константа */
f(s+2); /* значение выражения */
}
Обратите внимание, что параметр str из f(str) и массив str[] - это две совершенно
РАЗНЫЕ вещи, хотя и называющиеся одинаково. Переименуйте аргумент функции f и пере-
пишите ее в виде
f(ss) char ss[]; /* формальный параметр. */
{ printf( "%s %s\n", ss, str ); }
Что печатается теперь? Составьте аналогичный пример с целыми числами.
1.100. Поговорим более подробно про область видимости имен.
int x = 12;
f(x){ int y = x*x;
if(x) f(x - 1);
}
main(){ int x=173, z=21; f(2); }
Локальные переменные и аргументы функции отводятся в стеке при вызове функции и
А. Богатырев, 1992-95 - 47 - Си в UNIX
уничтожаются при выходе из нее:
-+ +- вершина стека
|локал y=0 |
|аргумент x=0 | f(0)
|---------------|---------
"кадр" |локал y=1 |
frame |аргумент x=1 | f(1)
|---------------|---------
|локал y=4 |
|аргумент x=2 | f(2)
|---------------|---------
|локал z=21 |
auto: |локал x=173 | main()
================================== дно стека
static: глобал x=12
==================================
Автоматические локальные переменные и аргументы функции видимы только в том вызове
функции, в котором они отведены; но не видимы ни в вызывающих, ни в вызываемых функ-
циях (т.е. видимость их ограничена рамками своего "кадра" стека). Статические гло-
бальные переменные видимы в любом кадре, если только они не "перекрыты" (заслонены)
одноименной локальной переменной (или формалом) в данном кадре.
Что напечатает программа? Постарайтесь ответить на этот вопрос не выполняя
программу на машине!
x1 x2 x3 x4 x5
int x = 12; /* x1 */ | . . . .
f(){ |___ . . .
int x = 8; /* x2, перекрытие */ : | . . .
printf( "f: x=%d\n", x ); /* x2 */ : | . . .
x++; /* x2 */ : | . . .
} :--+ . . .
g(x){ /* x3 */ :______ . .
printf( "g: x=%d\n", x ); /* x3 */ : | . .
x++; /* x3 */ : | . .
} :-----+ . .
h(){ :_________ .
int x = 4; /* x4 */ : | .
g(x); /* x4 */ : |___
{ int x = 55; } /* x5 */ : : |
printf( "h: x=%d\n", x ); /* x4 */ : |--+
} :--------+
main(){ |
f(); h(); |
printf( "main: x=%d\n", x ); /* x1 */ |
} ----
Ответ:
f: x=8
g: x=4
h: x=4
main: x=12
Обратите внимание на функцию g. Аргументы функции служат копиями фактических пара-
метров (т.е. являются локальными переменными функции, проинициализированными значени-
ями фактических параметров), поэтому их изменение не приводит к изменению фактичес-
кого параметра. Чтобы изменять фактический параметр, надо передавать его адрес!
А. Богатырев, 1992-95 - 48 - Си в UNIX
1.101. Поясним последнюю фразу. (Внимание! Возможно, что данный пункт вам следует
читать ПОСЛЕ главы про указатели). Пусть мы хотим написать функцию, которая обмени-
вает свои аргументы x и y так, чтобы выполнялось x < y. В качестве значения функция
А. Богатырев, 1992-95 - 32 - Си в UNIX
вычисления ведутся по модулю 256 (2 в 8 степени). То есть в данном случае 255+1=0
Решений существует два: первое - превратить unsigned char в int. Второе - вста-
вить явную проверку на последнее значение диапазона.
int main(int ac, char *av[]){
unsigned char ch;
for(ch=0; ; ch++){
printf("%d\n", ch);
if(ch == 255) break;
}
return 0;
}
1.73. Подумайте, почему для
unsigned a, b, c;
a < b + c не эквивалентно a - b < c
(первое - более корректно). Намек в виде примера (он выполнялся на 32-битной машине):
a = 1; b = 3; c = 2;
printf( "%u\n", a - b ); /* 4294967294, хотя в
нормальной арифметике 1 - 3 = -2 */
printf( "%d\n", a < b + c ); /* 1 */
printf( "%d\n", a - b < c ); /* 0 */
Могут ли unsigned числа быть отрицательными?
1.74. Дан текст:
short x = 40000;
printf("%d\n", x);
Печатается -25536. Объясните эффект. Указание: каково наибольшее представимое корот-
кое целое (16 битное)? Что на самом деле оказалось в x? (лишние слева биты - обруба-
ются).
1.75. Почему в примере
double x = 5 / 2;
printf( "%g\n", x );
значение x равно 2 а не 2.5 ?
Ответ: производится целочисленное деление, затем в присваивании целое число 2
приводится к типу double. Чтобы получился ответ 2.5, надо писать одним из следующих
способов:
double x = 5.0 / 2;
x = 5 / 2.0;
x = (double) 5 / 2;
x = 5 / (double) 2;
x = 5.0 / 2.0;
то есть в выражении должен быть хоть один операнд типа double.
Объясните, почему следующие три оператора выдают такие значения:
А. Богатырев, 1992-95 - 33 - Си в UNIX
double g = 9.0;
int t = 3;
double dist = g * t * t / 2; /* 40.5 */
dist = g * (t * t / 2); /* 36.0 */
dist = g * (t * t / 2.0); /* 40.5 */
В каких случаях деление целочисленное, в каких - вещественное? Почему?
1.76. Странслируйте пример на машине с длиной слова int равной 16 бит:
long n = 1024 * 1024;
long nn = 512 * 512;
printf( "%ld %ld\n", n, nn );
Почему печатается 0 0 а не 1048576 262144?
Ответ: результат умножения (2**20 и 2**18) - это целое число; однако оно слишком
велико для сохранения в 16 битах, поэтому старшие биты обрубаются. Получается 0.
Затем в присваивании это уже обрубленное значение приводится к типу long (32 бита) -
это все равно будет 0.
Чтобы получить корректный результат, надо чтобы выражение справа от = уже имело
тип long и сразу сохранялось в 32 битах. Для этого оно должно иметь хоть один операнд
типа long:
long n = (long) 1024 * 1024;
long nn = 512 * 512L;
1.77. Найдите ошибку в операторе:
x - = 4; /* вычесть из x число 4 */
Ответ: между `-' и `=' не должно быть пробела. Операция вида
x @= expr;
означает
x = x @ expr;
(где @ - одна из операций + - * / % ^ >> << & |), причем x здесь вычисляется единст-
венный раз (т.е. такая форма не только короче и понятнее, но и экономичнее).
Однако имеется тонкое отличие a=a+n от a+=n; оно заключается в том, сколько раз
вычисляется a. В случае a+=n единожды; в случае a=a+n два раза.
А. Богатырев, 1992-95 - 34 - Си в UNIX
#include <stdio.h>
static int x = 0;
int *iaddr(char *msg){
printf("iaddr(%s) for x=%d evaluated\n", msg, x);
return &x;
}
int main(){
static int a[4];
int *p, i;
printf( "1: "); x = 0; (*iaddr("a"))++;
printf( "2: "); x = 0; *iaddr("b") += 1;
printf( "3: "); x = 0; *iaddr("c") = *iaddr("d") + 1;
for(i=0, p = a; i < sizeof(a)/sizeof(*a); i++) a[i] = 0;
*p++ += 1;
for(i=0; i < sizeof(a)/sizeof(*a); i++)
printf("a[%d]=%d ", i, a[i]);
printf("offset=%d\n", p - a);
for(i=0, p = a; i < sizeof(a)/sizeof(*a); i++) a[i] = 0;
*p++ = *p++ + 1;
for(i=0; i < sizeof(a)/sizeof(*a); i++)
printf("a[%d]=%d ", i, a[i]);
printf("offset=%d\n", p - a);
return 0;
}
Выдача:
1: iaddr(a) for x=0 evaluated
2: iaddr(b) for x=0 evaluated
3: iaddr(d) for x=0 evaluated
iaddr(c) for x=0 evaluated
a[0]=1 a[1]=0 a[2]=0 a[3]=0 offset=1
a[0]=1 a[1]=0 a[2]=0 a[3]=0 offset=2
Заметьте также, что
a[i++] += z;
это
a[i] = a[i] + z; i++;
а вовсе не
a[i++] = a[i++] + z;
1.78. Операция y = ++x; эквивалентна
y = (x = x+1, x);
а операция y = x++; эквивалентна
y = (tmp = x, x = x+1, tmp);
или
y = (x += 1) - 1;
где tmp - временная псевдопеременная того же типа, что и x. Операция `,' выдает
А. Богатырев, 1992-95 - 35 - Си в UNIX
значение последнего выражения из перечисленных (подробнее см. ниже).
Пусть x=1. Какие значения будут присвоены x и y после выполнения оператора
y = ++x + ++x + ++x;
1.79. Пусть i=4. Какие значения будут присвоены x и i после выполнения оператора
x = --i + --i + --i;
1.80. Пусть x=1. Какие значения будут присвоены x и y после выполнения оператора
y = x++ + x++ + x++;
1.81. Пусть i=4. Какие значения будут присвоены i и y после выполнения оператора
y = i-- + i-- + i--;
1.82. Корректны ли операторы
char *p = "Jabberwocky"; char s[] = "0123456789?";
int i = 0;
s[i] = p[i++]; или *p = *++p;
или s[i] = i++;
или даже *p++ = f( *p );
Ответ: нет, стандарт не предусматривает, какая из частей присваивания вычисляется
первой: левая или правая. Поэтому все может работать так, как мы и подразумевали, но
может и иначе! Какое i используется в s[i]: 0 или уже 1 (++ уже сделан или нет), то
есть
int i = 0; s[i] = i++; это
s[0] = 0; или же s[1] = 0; ?
Какое p будет использовано в левой части *p: уже продвинутое или старое? Еще более
эта идея драматизирована в
s[i++] = p[i++];
Заметим еще, что в
int i=0, j=0;
s[i++] = p[j++];
такой проблемы не возникает, поскольку индексы обоих в частях присваивания незави-
симы. Зато аналогичная проблема встает в
if( a[i++] < b[i] )...;
Порядок вычисления операндов не определен, поэтому неясно, что будет сделано прежде:
взято значение b[i] или значение a[i++] (тогда будет взято b[i+1] ). Надо писать
так, чтобы не полагаться на особенности вашего компилятора:
if( a[i] < b[i+1] )...; или *p = *(p+1);
i++; ++p;
А. Богатырев, 1992-95 - 36 - Си в UNIX
Твердо усвойте, что i++ и ++i не только выдают значения i и i+1 соответственно,
но и изменяют значение i. Поэтому эти операторы НЕ НАДО использовать там, где по
смыслу требуется i+1, а не i=i+1. Так для сравнения соседних элементов массива
if( a[i] < a[i+1] ) ... ; /* верно */
if( a[i] < a[++i] ) ... ; /* неверно */
1.83. Порядок вычисления операндов в бинарных выражениях не определен (что раньше
вычисляется - левый операнд или же правый ?). Так пример
int f(x,s) int x; char *s;
{ printf( "%s:%d ", s, x ); return x; }
main(){
int x = 1;
int y = f(x++, "f1") + f(x+=2, "f2");
printf("%d\n", y);
}
может печатать либо
f1:1 f2:4 5
либо
f2:3 f1:3 6
в зависимости от особенностей поведения вашего компилятора (какая из двух f() выпол-
нится первой: левая или правая?). Еще пример:
int y = 2;
int x = ((y = 4) * y );
printf( "%d\n", x );
Может быть напечатано либо 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 <stdio.h>
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))
= b + ((a - b) & (0xffffffff))
= b + (a - b)
= a
что корректно.
Случай 2: a >= b
Здесь (a - b) >= 0, поэтому старший бит разности
(a - b) равен 0. Тогда (a - b) >> 31 == 0, и мы имеем:
min(a, b) = b + ((a - b) & ((a - b) >> 31))
= b + ((a - b) & (0x00000000))
= b + (0)
= b
что также корректно.
Статья предоставлена by Jeff Bonwick.
1.93. Есть ли быстрый способ определить, является ли X степенью двойки? Да, есть.
int X является степенью двойки
тогда и только тогда, когда
(X & (X - 1)) == 0
(в частности 2 здесь окажется степенью двойки). Как это работает? Пусть X != 0. Если
X - целое, то его двоичное представление таково:
X = bbbbbbbbbb10000...
где 'bbb' представляет некие биты, '1' - младший бит, и все остальные биты правее -
нули. Поэтому:
X = bbbbbbbbbb10000...
X - 1 = bbbbbbbbbb01111...
------------------------------------
X & (X - 1) = bbbbbbbbbb00000...
Другими словами, X & (X-1) имеет эффект обнуления последнего единичного бита. Если X
- степень двойки, то он содержит в двоичном представлении ровно ОДИН такой бит, поэ-
тому его гашение обращает результат в ноль. Если X - не степень двойки, то в слове
есть хотя бы ДВА единичных бита, поэтому X & (X-1) должно содержать хотя бы один из
оставшихся единичных битов - то есть не равняться нулю.
Следствием этого служит программа, вычисляющая число единичных битов в слове X:
int popc;
for (popc = 0; X != 0; X &= X - 1)
popc++;
При этом потребуется не 32 итерации (число бит в int), а ровно столько, сколько еди-
ничных битов есть в X. Статья предоставлена by Jeff Bonwick.
А. Богатырев, 1992-95 - 43 - Си в UNIX
1.94. Функция для поиска номера позиции старшего единичного бита в слове. Использу-
ется бинарный поиск: позиция находится максимум за 5 итераций (двоичный логарифм
32х), вместо 32 при линейном поиске.
int highbit (unsigned int x)
{
int i;
int h = 0;
for (i = 16; i >= 1; i >>= 1) {
if (x >> i) {
h += i;
x >>= i;
}
}
return (h);
}
Статья предоставлена by Jeff Bonwick.
1.95. Напишите функцию, округляющую свой аргумент вниз до степени двойки.
#include <stdio.h>
#define INT short
#define INFINITY (-999)
/* Функция, выдающая число, являющееся округлением вниз
* до степени двойки.
* Например:
* 0000100010111000110
* заменяется на
* 0000100000000000000
* то есть остается только старший бит.
* В параметр power2 возвращается номер бита,
* то есть показатель степени двойки. Если число == 0,
* то эта степень равна минус бесконечности.
*/
А. Богатырев, 1992-95 - 44 - Си в UNIX
unsigned INT round2(unsigned INT x, int *power2){
/* unsigned - чтобы число рассматривалось как
* битовая шкала, а сдвиг >> заполнял левые биты
* нулем, а не расширял вправо знаковый бит.
* Идея функции: сдвигать число >> пока не получится 1
* (можно было бы выбрать 0).
* Затем сдвинуть << на столько же разрядов, при этом все правые
* разряды заполнятся нулем, что и требовалось.
*/
int n = 0;
if(x == 0){
*power2 = -INFINITY; return 0;
}
if(x == 1){
*power2 = 0; return 1;
}
while(x != 1){
x >>= 1;
n++;
if(x == 0 || x == (unsigned INT)(-1)){
printf("Вижу %x: похоже, что >> расширяет знаковый бит.\n"
"Зациклились!!!\n", x);
return (-1);
}
}
x <<= n;
*power2 = n; return x;
}
int counter[ sizeof(unsigned INT) * 8];
int main(void){
unsigned INT i;
int n2;
for(i=0; ; i++){
round2(i, &n2);
if(n2 == -INFINITY) continue;
counter[n2]++;
/* Нельзя писать for(i=0; i < (unsigned INT)(-1); i++)
* потому что такой цикл бесконечен!
*/
if(i == (unsigned INT) (-1)) break;
}
for(i=0; i < sizeof counter/sizeof counter[0]; i++)
printf("counter[%u]=%d\n", i, counter[i]);
return 0;
}
1.96. Если некоторая вычислительная функция будет вызываться много раз, не следует
пренебрегать возможностью построить таблицу решений, где значение вычисляется один
раз для каждого входного значения, зато потом берется непосредственно из таблицы и не
вычисляется вообще. Пример: подсчет числа единичных бит в байте. Напоминаю: байт
состоит из 8 бит.
А. Богатырев, 1992-95 - 45 - Си в UNIX
#include <stdio.h>
int nbits_table[256];
int countBits(unsigned char c){
int nbits = 0;
int bit;
for(bit = 0; bit < 8; bit++){
if(c & (1 << bit))
nbits++;
}
return nbits;
}
void generateTable(){
int c;
for(c=0; c < 256; c++){
nbits_table[ (unsigned char) c ] = countBits(c);
/* printf("%u=%d\n", c, nbits_table[ c & 0377 ]); */
}
}
int main(void){
int c;
unsigned long bits = 0L;
unsigned long bytes = 0L;
generateTable();
while((c = getchar()) != EOF){
bytes++;
bits += nbits_table[ (unsigned char) c ];
}
printf("%lu байт\n", bytes);
printf("%lu единичных бит\n", bits);
printf("%lu нулевых бит\n", bytes*8 - bits);
return 0;
}
1.97. Напишите макрос swap(x, y), обменивающий значениями два своих аргумента типа
int.
#define swap(x,y) {int tmp=(x);(x)=(y);(y)=tmp;}
... swap(A, B); ...
Как можно обойтись без временной переменной? Ввиду некоторой курьезности последнего
способа, приводим ответ:
int x, y; /* A B */
x = x ^ y; /* A^B B */
y = x ^ y; /* A^B A */
x = x ^ y; /* B A */
Здесь используется тот факт, что A^A дает 0.
1.98. Напишите функцию swap(x, y) при помощи указателей. Заметьте, что в отличие от
макроса ее придется вызывать как
А. Богатырев, 1992-95 - 46 - Си в UNIX
... swap(&A, &B); ...
Почему?
1.99. Пример объясняет разницу между формальным и фактическим параметром. Термин
"формальный" означает, что имя параметра можно произвольно заменить другим (во всем
теле функции), т.е. само имя не существенно. Так
f(x,y) { return(x + y); } и
f(муж,жена) { return(муж + жена); }
воплощают одну и ту же функцию. "Фактический" - означает значение, даваемое пара-
метру в момент вызова функции:
f(xyz, 43+1);
В Си это означает, что формальным параметрам (в качестве локальных переменных) прис-
ваиваются начальные значения, равные значениям фактических параметров:
x = xyz; y = 43 + 1; /*в теле ф-ции их можно менять*/
При выходе из функции формальные параметры (и локальные переменные) разопределяются
(и даже уничтожаются, см. следующий параграф). Имена формальных параметров могут
"перекрывать" (делать невидимыми, override) одноименные глобальные переменные на
время выполнения данной функции.
Что печатает программа?
char str[] = "строка1";
char lin[] = "строка2";
f(str) char str[]; /* формальный параметр. */
{ printf( "%s %s\n", str, str ); }
main(){
char *s = lin;
/* фактический параметр: */
f(str); /* массив str */
f(lin); /* массив lin */
f(s); /* переменная s */
f("строка3"); /* константа */
f(s+2); /* значение выражения */
}
Обратите внимание, что параметр str из f(str) и массив str[] - это две совершенно
РАЗНЫЕ вещи, хотя и называющиеся одинаково. Переименуйте аргумент функции f и пере-
пишите ее в виде
f(ss) char ss[]; /* формальный параметр. */
{ printf( "%s %s\n", ss, str ); }
Что печатается теперь? Составьте аналогичный пример с целыми числами.
1.100. Поговорим более подробно про область видимости имен.
int x = 12;
f(x){ int y = x*x;
if(x) f(x - 1);
}
main(){ int x=173, z=21; f(2); }
Локальные переменные и аргументы функции отводятся в стеке при вызове функции и
А. Богатырев, 1992-95 - 47 - Си в UNIX
уничтожаются при выходе из нее:
-+ +- вершина стека
|локал y=0 |
|аргумент x=0 | f(0)
|---------------|---------
"кадр" |локал y=1 |
frame |аргумент x=1 | f(1)
|---------------|---------
|локал y=4 |
|аргумент x=2 | f(2)
|---------------|---------
|локал z=21 |
auto: |локал x=173 | main()
================================== дно стека
static: глобал x=12
==================================
Автоматические локальные переменные и аргументы функции видимы только в том вызове
функции, в котором они отведены; но не видимы ни в вызывающих, ни в вызываемых функ-
циях (т.е. видимость их ограничена рамками своего "кадра" стека). Статические гло-
бальные переменные видимы в любом кадре, если только они не "перекрыты" (заслонены)
одноименной локальной переменной (или формалом) в данном кадре.
Что напечатает программа? Постарайтесь ответить на этот вопрос не выполняя
программу на машине!
x1 x2 x3 x4 x5
int x = 12; /* x1 */ | . . . .
f(){ |___ . . .
int x = 8; /* x2, перекрытие */ : | . . .
printf( "f: x=%d\n", x ); /* x2 */ : | . . .
x++; /* x2 */ : | . . .
} :--+ . . .
g(x){ /* x3 */ :______ . .
printf( "g: x=%d\n", x ); /* x3 */ : | . .
x++; /* x3 */ : | . .
} :-----+ . .
h(){ :_________ .
int x = 4; /* x4 */ : | .
g(x); /* x4 */ : |___
{ int x = 55; } /* x5 */ : : |
printf( "h: x=%d\n", x ); /* x4 */ : |--+
} :--------+
main(){ |
f(); h(); |
printf( "main: x=%d\n", x ); /* x1 */ |
} ----
Ответ:
f: x=8
g: x=4
h: x=4
main: x=12
Обратите внимание на функцию g. Аргументы функции служат копиями фактических пара-
метров (т.е. являются локальными переменными функции, проинициализированными значени-
ями фактических параметров), поэтому их изменение не приводит к изменению фактичес-
кого параметра. Чтобы изменять фактический параметр, надо передавать его адрес!
А. Богатырев, 1992-95 - 48 - Си в UNIX
1.101. Поясним последнюю фразу. (Внимание! Возможно, что данный пункт вам следует
читать ПОСЛЕ главы про указатели). Пусть мы хотим написать функцию, которая обмени-
вает свои аргументы x и y так, чтобы выполнялось x < y. В качестве значения функция