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

/* элемент еще не был выбран */

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...