Жанр: Учеба
Хрестоматия по программированию на Си в Unix
...= EOF){
printf( "Здравствуй, %s\n", buffer );
printf( "Введите ваше имя:" );
}
}
getstr( s, maxlen )
char *s; /* куда поместить строку */
int maxlen; /* длина буфера:
А. Богатырев, 1992-95 - 29 - Си в UNIX
макс. длина строки = maxlen-1 */
{ int c; /* не char! (почему ?) */
register int i = 0;
maxlen--; /* резервируем байт под конечный '\0' */
while(i " maxlen && (c = getchar()) != '\n'
&& c != EOF )
s[i++] = c;
/* обратите внимание, что сам символ '\n'
* в строку не попадет */
s[i] = '\0'; /* признак конца строки */
return (i == 0 && c == EOF) ? EOF : i;
/* вернем длину строки */
}
Вот еще один вариант функции чтения строки: в нашем примере ее следует вызывать как
fgetstr(buffer,sizeof(buffer),stdin);
Это подправленный вариант стандартной функции fgets (в ней строки @1 и @2 обменяны
местами).
char *fgetstr(char *s, int maxlen, register FILE *fp){
register c; register char *cs = s;
while(--maxlen " 0 && (c = getc(fp)) != EOF){
if(c == '\n') break; /* @1 */
*cs++ = c; /* @2 */
}
if(c == EOF && cs == s) return NULL;
/* Заметьте, что при EOF строка s не меняется! */
*cs = '\0'; return s;
}
Исследуйте поведение этих функций, когда входная строка слишком длинная (длиннее maxlen).
Замечание: вместо нашей "рукописной" функции getstr() мы могли бы использовать
стандартную библиотечную функцию gets(buffer).
1.68. Объясните, почему d стало отрицательным и почему %X печатает больше F, чем в
исходном числе? Пример выполнялся на 32-х битной машине.
main(){
unsigned short u = 65535; /* 16 бит: 0xFFFF */
short d = u; /* 15 бит + знаковый бит */
printf( "%X %d\n", d, d); /* FFFFFFFF -1 */
}
Указание: рассмотрите двоичное представление чисел (смотри приложение). Какие приведения
типов здесь происходят?
1.69. Почему 128 превратилось в отрицательное число?
main()
{
/*signed*/ char c = 128; /* биты: 10000000 */
unsigned char uc = 128;
int d = c; /* используется 32-х битный int */
printf( "%d %d %x\n", c, d, d );
/* -128 -128 ffffff80 */
d = uc;
printf( "%d %d %x\n", uc, d, d );
/* 128 128 80 */
}
А. Богатырев, 1992-95 - 30 - Си в UNIX
Ответ: при приведении char к int расширился знаковый бит (7-ой), заняв всю старшую
часть слова. Знаковый бит int-а стал равен 1, что является признаком отрицательного
числа. То же будет происходить со всеми значениями c из диапазона 128..255 (содержащими
бит 0200). При приведении unsigned char к int знаковый бит не расширяется.
Можно было поступить еще и так:
printf( "%d\n", c & 0377 );
Здесь c приводится к типу int (потому что при использовании в аргументах функции тип
char ВСЕГДА приводится к типу int), затем &0377 занулит старший байт полученного
целого числа (состоящий из битов 1), снова превратив число в положительное.
1.70. Почему
printf("%d\n", '\377' == 0377 );
printf("%d\n", '\xFF' == 0xFF );
печатает 0 (ложь)? Ответ: по той же причине, по которой
printf("%d %d\n", '\377', 0377);
печатает -1 255, а именно: char '\377' приводится в выражениях к целому расширением
знакового бита (а 0377 - уже целое).
1.71. Рассмотрим программу
#include "stdio.h"
int main(int ac, char **av){
int c;
while((c = getchar()) != EOF)
switch©{
case 'ы': printf("Буква ы\n"); break;
case 'й': printf("Буква й\n"); break;
default: printf("Буква с кодом %d\n", c); break;
}
return 0;
}
Она работает так:
% a.out
йфыв
Буква с кодом 202
Буква с кодом 198
Буква с кодом 217
Буква с кодом 215
Буква с кодом 10
^D
%
Выполняется всегда default, почему не выполняются case 'ы' и case 'й'?
Ответ: русские буквы имеют восьмой бит (левый) равный 1. В case такой байт приводится
к типу int расширением знакового бита. В итоге получается отрицательное
число. Пример:
void main(void){
int c = 'й';
printf("%d\n", c);
}
печатает -54
А. Богатырев, 1992-95 - 31 - Си в UNIX
Решением служит подавление расширения знакового бита:
#include "stdio.h"
/* Одно из двух */
#define U© ((c) & 0xFF)
#define UC© ((unsigned char) (c))
int main(int ac, char **av){
int c;
while((c = getchar()) != EOF)
switch©{
case U('ы'): printf("Буква ы\n"); break;
case UC('й'): printf("Буква й\n"); break;
default: printf("Буква с кодом %d\n", c); break;
}
return 0;
}
Она работает правильно:
% a.out
йфыв
Буква й
Буква с кодом 198
Буква ы
Буква с кодом 215
Буква с кодом 10
^D
%
Возможно также использование кодов букв:
case 0312:
но это гораздо менее наглядно. Подавление знакового бита необходимо также и в операторах
if:
int c;
if(c == 'й') ...
следует заменить на
if(c == UC('й')) ...
Слева здесь - signed int, правую часть компилятор тоже приводит к signed int. Приходится
явно говорить, что справа - unsigned.
1.72. Рассмотрим программу, которая должна напечатать числа от 0 до 255. Для этих
чисел в качестве счетчика достаточен один байт:
int main(int ac, char *av[]){
unsigned char ch;
for(ch=0; ch " 256; ch++)
return 0;
}
Однако эта программа зацикливается, поскольку в момент, когда ch==255, это значение
меньше 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© 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. Функция для поиска ном
...Закладка в соц.сетях
