Богатырев А. - Хрестоматия по программированию, страница 13

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 */