| Главная | Новости | Статьи | Книги | Ссылки |
Напишите программу, которая устанавливает в 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;
В программах иногда требуется использовать "множество": каждый допустимый элемент множества имеет номер и может либо присутствовать в множестве, либо отсутствовать. Число вхождений не учитывается. Множества принято моделировать при помощи битовых шкал:
#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); /* удалить из множества */
}
Напишите программу, распечатывающую все возможные перестановки массива из N элементов. Алгоритм будет рекурсивным, например таким: в качестве первого элемента перестановки взять i-ый элемент массива. Из оставшихся элементов массива (если такие есть) составить все перестановки порядка N-1. Выдать все перестановки порядка N, получающиеся склейкой i-ого элемента и всех (по очереди) перестановок порядка N-1.
Взять следующее i и все повторить.
Главная проблема здесь - организовать оставшиеся после извлечения i-ого элемента элементы массива в удобную структуру данных (чтобы постоянно не копировать массив).
Можно использовать, например, битовую шкалу уже выбранных элементов. Воспользуемся для этого макросами из предыдущего параграфа:
/* ГЕНЕРАТОР ПЕРЕСТАНОВОК ИЗ 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);
Напишите макроопределения циклического сдвига переменной типа 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)))
Вот как работает 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 на 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 */
Операции умножения * и деления / и % обычно достаточно медленны. В критичных по скорости функциях можно предпринять некоторые ручные оптимизации, связанные с представлением чисел в двоичном коде (хороший компилятор делает это сам!) - пользуясь тем, что операции +, &, >> и << гораздо быстрее. Пусть у нас есть
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 двоичных единиц
Например:
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() в главе "Текстовая обработка".
#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));
Как это работает? Рассмотрим два случая:
Здесь (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что корректно.
Здесь (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что также корректно.
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.
Функция для поиска номера позиции старшего единичного бита в слове. Используется бинарный поиск: позиция находится максимум за 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.
Напишите функцию, округляющую свой аргумент вниз до степени двойки.
#include <stdio.h>
#define INT short
#define INFINITY (-999)
/* Функция, выдающая число, являющееся округлением вниз
* до степени двойки.
* Например:
* 0000100010111000110
* заменяется на
* 0000100000000000000
* то есть остается только старший бит.
* В параметр power2 возвращается номер бита,
* то есть показатель степени двойки. Если число == 0,
* то эта степень равна минус бесконечности.
*/
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;
}
Если некоторая вычислительная функция будет вызываться много раз, не следует пренебрегать возможностью построить таблицу решений, где значение вычисляется один раз для каждого входного значения, зато потом берется непосредственно из таблицы и не вычисляется вообще. Пример: подсчет числа единичных бит в байте. Напоминаю: байт состоит из 8 бит.
#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;
}
Напишите макрос 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.
Напишите функцию swap(x, y) при помощи указателей. Заметьте, что в отличие от макроса ее придется вызывать как
... swap(&A, &B); ...
Почему?
Пример объясняет разницу между формальным и фактическим параметром. Термин "формальный" означает, что имя параметра можно произвольно заменить другим (во всем теле функции), т.е. само имя не существенно. Так
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 ); }
Что печатается теперь? Составьте аналогичный пример с целыми числами.
© Copyright А. Богатырев, 1992-95
Си в UNIX
Назад | Содержание | Вперед