*/
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. . -
: 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 */
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. -
(.. , -
), -
. , !
. , 1992-95 - 48 - UNIX
1.101. . (! ,
). , -
x y , x < y.
(x+y)/2. :
int msort(x, y) int x, y;
{ int tmp;
if(x > y){ tmp=x; x=y; y=tmp; }
return (x+y)/2;
}
int x=20, y=8;
main(){
msort(x,y); printf("%d %d\n", x, y); /* 20 8 */
}
. x y,
, .. .
!
,
, :
int msort(xptr, yptr) int *xptr, *yptr;
{ int tmp;
if(*xptr > *yptr){tmp= *xptr;*xptr= *yptr;*yptr=tmp;}
return (*xptr + *yptr)/2;
}
int x=20, y=8, z;
main(){
z = msort(&x,&y);
printf("%d %d %d\n", x, y, z); /* 8 20 14 */
}
, x y, &x
&y.
( x ) scanf()
:
int x; scanf("%d", &x); /* scanf("%d", x); */
, ( )
, :
int xx=12, *xxptr = &xx, a[2] = { 13, 17 };
int *fy(){ return &y; }
msort(&x, &a[0]); msort(a+1, xxptr);
msort(fy(), xxptr);
msort(&(x+1), &y); msort(&x, &17);
,
:
msort(&xx - 20, a+40);
( ).
: -
( ) ,
( ).
- (
. , 1992-95 - 49 - UNIX
- return-, -
- "" ).
: ?
int a=2, b=13, c;
int f(x, y, z) int x, *y, z;
{
*y += x; x *= *y; z--;
return (x + z - a);
}
main(){ c=f(a, &b, a+4); printf("%d %d %d\n",a,b,c); }
(: 2 15 33)
1.102. - .
:
char *func1(char *s){
int s; /* : s */
...
}
int func2(int x, int y){
int z;
...
}
int func2(){
int x = __1__;
int y = __2__;
int z;
...
}
:
.
1.103. 3 :
- in - ;
- out - , ;
, ;
- in/out - .
. (
) :
int f( /*IN*/ int x,
/*OUT*/ int *yp,
/*INOUT*/ int *zp){
*yp = ++x + ++(*zp);
return (*zp *= x) - 1;
}
int x=2, y=3, z=4, res;
main(){ res = f(x, &y, &z);
printf("res=%d x=%d y=%d z=%d\n",res,x,y,z);
/* 14 2 8 15 */
}
, - .
,
(), . ,
- .
. , 1992-95 - 50 - UNIX
, .
" " ( bi_conv).
1.104. :
void func( int arg1
, char *arg2 /* argument 2 */
, char *arg3[]
, time_t time_stamp
){ ... }
, ( )
. ,
. , , :
enum { red
, green
, blue
};
, .
1.105. ?
char *val(int x){
char str[20];
sprintf(str, "%d", x);
return str;
}
void main(){
int x = 5; char *s = val(x);
printf("The values:\n");
printf("%d %s\n", x, s);
}
: val .
val() ( str[]) - s
! -
str[] ( ):
static char str[20];
printf("%s %s\n", val(1), val(2));
val() str[] -
"1 1" "2 2", "1 2".
val() :
char *val(int x, char str[]){
sprintf(str, "%d", x);
return str;
}
void main(){
int x=5, y=7;
char s1[20], s2[20];
printf("%s %s\n", val(x, s1), val(y, s2));
}
. , 1992-95 - 51 - UNIX
1.106. ( ) |-?
main() {
double y; int x = 12;
y = sin (x);
printf ("%s\n", y);
}
:
- sin() double,
. ,
int y=sin(x) -
int , .. double.
( - double) ( int), -
( ), -
, . -
, , , malloc() itoa().
, int, -
( ) , |=:
extern double sin();
extern long atol();
extern char *malloc(), *itoa();
, ,
( ,
, , ):
/*extern*/ char *f();
main(){
char *s;
s = f(1); puts(s);
}
char *f(n){ return "knights" + n; }
, , .
include-. ,
(sin, cos, fabs, ...)
/usr/include/math.h. main
#include <math.h>
extern double sin(), cos(), fabs();
- sin() double,
int ( double -
). , ..
12. :
y = sin( (double) x );
sin(12.0); sin(12);
____________________
|- , sin,
cos, exp, log, sqrt, ... -lm
cc file.c -o file -lm
|= extern ("") , -
- , ,
, .
. , 1992-95 - 52 - UNIX
- printf double :
%g %f ( scanf() - %lf).
long %d %ld .
( , " "). -
, sin
double sin(double x);
( )
- C++ (streams).
1.107. :
int sum(x,y,z){ return(x+y+z); }
main(){
int s = sum(12,15);
printf("%d\n", s);
}
, sum() ,
! , z sum() .
s = sum(12,15,17,24);
( -
!).
, :
int x; scanf("%d%d", &x );
%d
. %-
scanf printf.
1.108. (,,) f() ?
f(x, y, z){
printf("%d %d %d\n", x, y, z);
}
main(){ int t;
f(1, (2, 3, 4), 5);
f(1, (t=3,t+1), 5);
}
: (2,3,4) - "",
. 1 4 5.
- ,
, . :
int y = 2, x;
x = (y+4, y, y*2); printf("%d\n", x); /* 4 */
x = y+4, y, y*2 ; printf("%d\n", x); /* 6 */
x = (x=y+4, ++y, x*y); printf("%d\n", x); /* 18 */
. - x y (
y - ), - ,
! .
x=y*2; x=y+4 (.. ,
. , 1992-95 - 53 - UNIX
). , (
) :
x+y; z++; x == y+1; x;
, - (
, ):
f(12,x); putchar('');
, , x=cos(0.5)/3.0; c=getchar();
"" , ,
, :
main(){ int i, x = 0;
for(i=1; i < 4; i++)
x++, if(x > 2) x = 2; /* { ; } */
}
if .
void ( ):
void f(){}
...
for(i=1; i < 4; i++)
x++, f();
.
, ,
:
if( ) { x = 0; y = 0; }
if( ) x = 0, y = 0;
if( ) x = y = 0;
1.109. :
switch(c){
case 1:
x++; break;
case 2:
y++; break;
defalt:
z++; break;
}
c=3, z++ . ? (, defalt: - , -
default).
1.110. , -
, 0 1?
while ( c = getchar() != 'e')
printf("%d %c\n, c, c);
: :
while ((c = getchar()) != 'e')
printf("%d %c\n, c, c);
. , 1992-95 - 54 - UNIX
, ! : -
. :
if( x & 01 == 0 ) ... if( c&0377 > 0300)...;
:
if( (x & 01) == 0 ) ... if((c&0377) > 0300)...;
:
FILE *fp;
if( fp = fopen( "", "w" ) == NULL ){
fprintf( stderr, " \n");
exit(1);
}
fprintf(fp,"Good bye, %s world\n","cruel"); fclose(fp);
, fp 0 ( !)
fprintf() ( |-).
( ) :
/* from to */
char *strcpy( to, from ) register char *from, *to;
{
char *p = to;
while( *to++ = *from++ != '\0' );
return p;
}
1.111. (0, NULL, '\0') (
).
if( i == 0 ) ...; --> if( !i ) ... ;
if( i != 0 ) ...; --> if( i ) ... ;
,
char s[20], *p ;
for(p=s; *p != '\0'; p++ ) ... ;
for(p=s; *p; p++ ) ... ;
char s[81], *gets();
while( gets(s) != NULL ) ... ;
while( gets(s)) ... ;
strcpy .
____________________
|- "" - . " ". " -
" - . UNIX ,
: SIGBUS, SIGSEGV, SIGILL.
" ". , ,
!
. , 1992-95 - 55 - UNIX
1.112.
if( 2 < 5 < 4 )
: ! , , "" ""
" 0" "0" ( 1 0).
if :
((2 < 5) < 4)
(2 < 5) 1. (1 < 4) 1 ().
, .
if( a < x < b )
if( a < x && x < b )
1.113. . ;
?
int c;
for(;;) {
printf(" :");
c = getchar();
if(c = 'e') {
printf(" e, \n"); break;
}
printf( " %03o\n", c & 0377 );
}
: if : `=' `=='.
( +=, -=, *=, ...)
, !
c = 'e'; if( c ) ... ;
, 'e'!= 0, ! ,
(/). :
= == if
( ).
:
for( i=0; !(i = 15) ; i++ ) ... ;
( );
static char s[20] = " abc"; int i=0;
while(s[i] = ' ') i++;
printf("%s\n", &s[i]); /* abc */
( ).
, , :
int x, y, z;
x = y = z = 1; x = (y = (z = 1));
. , 1992-95 - 56 - UNIX
|-
y=f( x += 2 ); // x+=2; y=f(x);
if((y /= 2) > 0)...; // y/=2; if(y>0)...;
"" ( - ..
( 4 )):
#include <stdio.h>
main(){
int sum = 0, card; char answer[36];
srand( getpid()); /* */
do{ printf( " %d . ? ", sum);
if( *gets(answer) == 'n' ) break;
/* */
printf( " %d \n",
card = 6 + rand() % (11 - 6 + 1));
} while((sum += card) < 21); /* SIC ! */
printf ( sum == 21 ? "\n" :
sum > 21 ? "\n":
"%d \n", sum);
}
, .
, ,
(printf), .. , :
#include <stdio.h>
int width = 20; /* */
int len; char str[512];
main(){
while(gets(str)){
if((len = strlen(str)) > width){
fprintf(stderr,"width %d\n", width=len);
}
printf("|%*.*s|\n", -width, width, str);
}
}
a.out < > /dev/null
1.114. "" ( - ) ?
int x = 0;
while( x < 100 );
printf( "%d\n", x++ );
printf( "\n" );
: while?
: ; . :
.
1.115. ,
. , :
x = 1 << 2 + 1 ;
____________________
|- //, - -
C++. //
.
. , 1992-95 - 57 - UNIX
8, 5, . :
:
x = (1 << 2) + 1 ;
: x 40, , 1:
int bigFlag = 1, x = 2;
x = x + bigFlag ? 40 : 1;
printf( "%d\n", x );
40, 42,
x = (x + bigFlag) ? 40 : 1;
x = x + (bigFlag ? 40 : 1);
. ?:
.
, () , . , -
long a = 50, x; int b = 4;
x = (a * 100) / b;
/* ! */
x = (a * 100)/b = 5000/4 = 1250
x = (a/b) * 100 = 12*100 = 1200
, * / (
"" , ). -
, .. :
{ long a100 = a * 100; x = a100 / b; }
1.116. .
main (. argv
argc " UNIX"):
$ a.out sin 0.5
sin(0.5)=0.479426
( $ , ).
double
atof().
char *str1, *str2, *str3; ...
extern double at