= 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
#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
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. Аргументы функции служат копиями фактических пара-
метров (т.е. являются локальными переменными функции, проинициализированными значени-
ями фактических параметров), поэтому их изменение не приводит к изменению фактичес-
