Vežbe iz Programiranja 1

 BITOVSKI OPERATORI (BITWISE operatori)

ZADACI ZA VEZBU
Zadatak 1: NCP koji ucitava sa standardnog ulaza dva cela broja i stampa njihov zbir u

• u oktalnom sistemu
• u heksadekadnom sistemu (slovne cifre da budu prikazane u formi velikih slova)
• u heksadekadnom sistemu (slovne cifre da budu prikazane u formi malih slova)

Ako imate problem sa implementacijom resenja za zadatke 3 ili 4, pazljivo proucite primere koji slede.

& bitovsko AND       1&1=1 0&1=0 0&0=0
Neka je b ili 0 ili 1.
Onda b & 0 =0, b&1=b
AKO ZELITE DA NEKE BITOVE POSTAVITE NA NULA, MORATE URADITI OPERACIJU AND SA 0

Primer: 255 & 15= ?
255 -> 1111 1111
15 -> 0000 1111
255&15-> 0000 1111 -> oktalno 17 -> heksadekadno 0F
-> dekadno 15

Primer: Dato je unsigned x; Koliko je x & 01?

B4, B3, ..., B0 su bitovi na pozicijama 4,3,...0
x binarno Bn B_n-1 ....B4 B3 B2 B1 B0
X&01= Bn B_n-1 ....B4 B3 B2 B1 B0
     & 0 0 ....    0 0   0 0   1
===================================
      0 0 ....     0 0   0 0   B0
ZAKLJUCAK x & 01 vraca kao rezultat nulti bit broja x
Da li Vam ovaj zakljucak pomaze da resite zadatak 4 sa gore navedenog spiska zadataka za vezbu?

| BITOVSKO OR       1 | 1 = 1, 1 | 0 =1, 0 | 0 = 0
Ako je b ili 0 ili 1, onda b | 0= b, b | 1 = 1
AKO ZELITE DA POSTAVITE NEKI BIT NA 1, RADITI OPERACIJU OR SA 1com

Primer: 255 | 15 = ?

255 -> 1111 1111
| 15 -> 0000 1111
======================
255 <- 1111 1111
oktalno 377
heksadekadno FF

Primer: Dato je unsigned x; Sta je rezultat rada x= x | 01

x Bn B_n-1 ... B3 B2 B1 B0
| 0  1    ... 0  0 0   1
==============================
  Bn B_n-1 ... B3 B2 B1 1

ODGOVOR> rezultat je broj X kome je 0-ti bit postavljen na 1

POSTAVITI 5. bit (B4) na 1, a ostale sacuvati

x Bn B_n-1 .... B6 B5 B4 B3 B2 B1 B0
| 0   0 .....  0  0  1  0  0  0  0      (dekadno gledano, ova maska je broj 16)
======================================
  Bn Bn-1 .... B6 B5 1 B3 B2 B1 B0

X | 16 postavlja 5. bit u X na 1, a ostle bitove ne menja

ZAKLJUCAK x | pow(2, n-1) postavlja n-ti bit u x na 1

KAKO POSTAVITI 4. bit u broju x na 0, a ostale ne menjati?
X & 8 postavlja bit B3 na 0, a ostale bitove ne menja

KAKO POSTAVITI NAJNIZA 3 BITA U BROJU X na nule, a ostale bitove ne dirati?

X Bn B_n-1 ... B3 B2 B1 B0
& 1  1 ...    1  0  0  0
=====================================
  Bn B_n-1 ... B3 0  0  0

KOJI JE TO BROJ KOME SU POSLEDNJE 3 bita 0?

AKO JE REGISTAR 8-bitni to je broj 1111 1000 = 255 - 7 = (256 - 1) -7
AKO JE REGISTAR 16-bitni to je broj 1111 1111 1111 1000 = (2 na 16) -1 - 7
ZAKLJUCAK
X & ( ( 2 na (sizeof(x)*8)) -1 -7) postavlja tri posednja. bita na 0

KAKO POSTAVITI NAJNIZA 3 BITA U X na 1ce?
X | 7

***************************************************************

^ caret BITOVSKO XOR, XOR JE ekskluzivna disjunkcija
JE not EQUIVAVLENT

1 ^ 0 = 1, 1 ^ 1 =0, 0 ^ 0 = 0
AKO je b ili 0 ili 1, onda b ^ 1 = !b , b ^ 0 = b

255 ^ 15 = ?
255 -> 1111 1111
15 -> 0000 1111
^ ==============
1111 0000 256 -1 - 15 = 240

Primer: Dato je unsigned x; Sta je rezultat naredbe x = x ^ 01;

x -> Bn B_n-1 .... B2 B1 B0
01 -> 0 0   ....  0  0  1
^ ===========================
     Bn B_n-1 .... B2 B1 !B0
ODGOVOR> Rezultat je broj X kome je 0-ti bit invertovan, a ostali bitovi su nepromenjeni

~ BITOVSKO NOT invertuje bitove
Ako je u 8-bitnom registru smesten dekadni broj 7, onda ~7= INVERTOVANO(0000 0111) = 1111 1000 tj. dekadno 248

CEMU JE JEDNAKO ~1?
CEMU JE JEDNAKO ~0?
AKO JE SIZEOF (int) = 1, tj. ako se int registruje u 1 bajtu,
tj. u 8 bitova, onda se:
1 registruje kao 0000 0001
0 registruje kao 0000 0000

TE JE ~1 = INVERTOVANO(0000 0001) = 1111 1110 tj. 254
~1 = (2 na sizeof(int)*8) -2

TE JE ~0 = INVERTOVANO (0000 0000) = 1111 1111
~0 daje citav registar napunjen bitovima koji su 1

>> SHIFT RIGHT, POMERANJE NADESNO,
EFEKAT DELJENJA STEPENOM DVOJKE

NA PRIMER 32 >> 3 je isto sto i 32 / 2³,
ali 32 >> 3 se brze izvrsava

<< SHIFT LEFT, POMERANJE NALEVO
NAPRIMER 3 << 5 je isto sto i 3 * 2⁵,
ali se 3 << 5 brze izvrsava

Primer 59. (Demonstracija bitskih operatora) Sta je rezultat rada sledeceg programa?

#include <stdio.h>
main()
{ printf("%o %o\n",255,15);
printf( "255 & 15 = %d\n", 255 & 15 );
printf( "255 | 15 = %d\n", 255 | 15 );
printf( "255 ^ 15 = %d\n", 255 ^ 15 );
printf( "2 << 2 = %d\n", 2 << 2 );
printf( "16 >> 2 = %d\n", 16 >> 2 );
}
Izlaz iz programa je:
377 17
255 & 15 = 15
255 | 15 = 255
255 ^ 15 = 240
2 << 2 = 8
16 >> 2 = 4

60. Napisati funkciju print bits koja stampa bitove u zapisu datog neoznacenog celog broja x i program koji ilustruje rad sa tom funkcijom. Uocimo da funkcijom print bits se zapravo stampa binarna predstava broja x.

#include <stdio.h>

/*
Funkcija print_bits stampa bitove datog celog broja x.
Vrednost bita na poziciji i je 0 ako i samo ako se dobija 0
pri konjunkciji broja x sa
maskom 000..010....000 (ovu masku cine sve nule, osim 1ce na poziciji i)

Funkcija krece od pozicije najvece tezine kreirajuci masku pomeranjem jedinice u levo
za (broj_bitova(x) - 1) mesto, i zatim pomerajuci ovu masku za jedno mesto u levo u svakoj
sledecoj iteraciji sve dok maska ne postane 0.
*/

void print_bits(unsigned x){

   unsigned wl = sizeof(unsigned)*8; /* wl je broj bitova za registrovanje unsigned promenljive */
    unsigned mask; /* maska bitova */

    for (mask = 1<<wl-1; mask; mask >>= 1) putchar(x&mask ? '1' : '0');

    putchar('\n');
}

main()
{
    print_bits(127);
    print_bits(128);
    print_bits(0x00FF00FF);
    print_bits(0xFFFFFFFF);
}

Izlaz iz programa:
00000000000000000000000001111111
00000000000000000000000010000000
00000000111111110000000011111111
11111111111111111111111111111111

ZADACI ZA VEZBU

61. NCP koji proverava da li se na k-tom bitu broja koji se ucitava sa standardnog ulaza nalazi 1. Pozicija k se ucitava sa standardnog ulaza. Voditi racuna numeracija bitova je takva da bit najmanje tezine (krajnji desno) je nulti bit, a ne prvi bit.

#include <stdio.h>
main(){
int n,k;
printf("Unesite broj i poziciju tog broja koju zelite da proverite:\n");
scanf("%d %d",&n,&k);

if ((n&(1 << k))!=0) printf("Bit je 1\n");
else printf("Bit je 0\n");

return 0;
}

62. NCP koji postavlja na k-to mesto 1

#include <stdio.h>
void print_bits(unsigned x);
main(){

int n,k;

printf("Unesite broj i poziciju tog broja koju zelite da proverite:\n");
scanf("%d %d",&n,&k);

printf("Binarno\v uneseni broj je\n");
print_bits(n);

printf("Novi broj je %d\n",(n |(1<<k)));
printf("Binarno, novi broj je\n");
print_bits((n |(1<<k)));

return 0;
}


void print_bits(unsigned x){

   unsigned wl = sizeof(unsigned)*8; /* wl je broj bitova za registrovanje unsigned promenljive */
    unsigned mask; /* maska bitova */

    for (mask = 1<<wl-1; mask; mask >>= 1) putchar(x&mask ? '1' : '0');

    putchar('\n');
}

Izrazom a>>b vrsi se pomeranje sadrzaja operanda a predstavljenog u binarnom obliku za b mesta u desno. Popunjavanje upraznjenih mesta na levoj strani zavisi od tipa podataka i vrste racunara. Ako se pomeranje primenjuje nad operandom tipa unsigned popunjavanje je nulama.
Ako se radi o oznacenom operandu popunjavanje je jedinicama kada je u krajnjem levom bitu jedinica, a nulama kada je u krajnjem levom bitu nula.

63. Napisati funkciju koja broji bitove postavljene na 1 u neoznacenom celom broju.

int bitcount(unsigned x)
{
int b;

for(b=0; x!=0; x>>=1)
if (x & 01) b++;

return b;
}

64. NCP koji izracunava sumu bitova datog neoznacenog broja.

#include <stdio.h>
/* Pomocna funkcija - stampa bitove neoznacenog broja */
void print_bits(unsigned x)
{
int wl = sizeof(unsigned)*8;
unsigned mask;
for (mask = 1<<wl-1; mask; mask >>= 1)
putchar(x&mask ? '1' : '0');
putchar('\n');
}

/* MANJE EFIKASNA VERZIJA
int sum_of_bits(unsigned x){

int wl = sizeof(unsigned)*8;
int br = 0;
unsigned mask;

for (mask = 1<<wl-1; mask; mask>>=1)
if (x&mask) br++;

return br;
}

*/

/* Efikasnija verzija */
int sum_of_bits(unsigned x)
{
int br;

for (br = 0; x; x>>=1)
if (x&1) br++;

return br;
}

main()
{
printf("Binarni zapis broja 127 je\n"); print_bits(127);
printf("Suma bitova broja 127 je %d\n",sum_of_bits(127));

printf("Binarni zapis broja 128 je\n");print_bits(128);
printf("Suma bitova broja 128 je %d\n",sum_of_bits(128));

printf("Binarni zapis broja 0x00FF00FF je\n"); print_bits(0x00FF00FF);
printf("Suma bitova broja 0x00FF00FF je %d\n",sum_of_bits(0x00FF00FF));

printf("Binarni zapis broja 0xFFFFFFFF je\n");print_bits(0xFFFFFFFF);
printf("Suma bitova broja 0xFFFFFFFF je %d\n",sum_of_bits(0xFFFFFFFF));
}

65. Napisati funkcije get bits, set bits, invert bits za (redom) izdvajanje, postavljanje i invertovanje pojedinacnih bitova

#include <stdio.h>
/* Pomocna funkcija - stampa bitove neoznacenog broja */
void print_bits(unsigned x)
{
int wl = sizeof(unsigned)*8;
unsigned mask;
for (mask = 1<<wl-1; mask; mask >>= 1)
putchar(x&mask ? '1' : '0');
putchar('\n');
}

/* Funkcija vraca n bitova broja x koji pocinju na poziciji p */
unsigned get_bits(unsigned x, int p, int n)
{
/* Gradimo masku koja ima poslednjih n jedinica
0000000...00011111
tako sto sve jedinice ~0 pomerimo u levo za n mesta
1111111...1100000
a zatim komplementiramo
*/
unsigned last_n_1 = ~(~0 << n);

/* x pomerimo u desno za odgovarajuci broj mesta, a zatim
konjunkcijom sa konstruisanom maskom obrisemo pocetne cifre */
return (x >> p+1-n) & last_n_1;

}

/* Funkcija vraca modifikovano x tako sto mu je izmenjeno n bitova
pocevsi od pozicije p i na ta mesta je upisano poslednjih n bitova broja y */
unsigned set_bits(unsigned x, int p, int n, unsigned y)
{
/* Maska 000000...000111111 - poslednjih n jedinica */
unsigned last_n_1 = ~(~0 << n);
/* Maska 1111100..000111111 - n nula pocevsi od pozicije p */
unsigned middle_n_0 = ~(last_n_1 << p+1-n);

/* Brisemo n bitova pocevsi od pozicije p */
x = x & middle_n_0;

/* Izdvajamo poslednjih n bitova broja y i pomeramo ih na poziciju p */
y = (y & last_n_1) << p+1-n;

/* Upisujemo bitove broja y u broj x i vracamo rezultat */
return x | y;
}

/* Invertuje n bitova broja x pocevsi od pozicije p */
unsigned invert_bits(unsigned x, int p, int n)
{
/* Maska 000000111...1100000 - n jedinica pocevsi od pozicije p */
unsigned middle_n_1 = ~(~0 << n) << p+1-n;

/* Invertujemo koristeci ekskluzivnu disjunkciju */
return x ^ middle_n_1;
}

main()
{
unsigned x = 0x0AA0AFA0;
print_bits(x);
print_bits(get_bits(x, 15, 8));
print_bits(set_bits(x, 15, 8, 0xFF));
print_bits(invert_bits(x, 15, 8));
}

Izlaz iz programa:
00001010101000001010111110100000
00000000000000000000000010101111
00001010101000001111111110100000
00001010101000000101000010100000

66. napisati funkcije right rotate bits, mirror bits za rotiranje i simetrija bitova.

#include <stdio.h>
/* Pomocna funkcija - stampa bitove neoznacenog broja */
void print_bits(unsigned x)
{
int wl = sizeof(unsigned)*8;
unsigned mask;
for (mask = 1<<wl-1; mask; mask >>= 1)
putchar(x&mask ? '1' : '0');
putchar('\n');
}

/* Funkcija vrsi rotaciju neoznacenog broja x za n pozicija u desno */
unsigned right_rotate(unsigned x, int n)
{
int i;
int wl = sizeof(unsigned)*8;

/* Postupak se ponavlja n puta */
for (i = 0; i < n; i++)
{
/* Poslednji bit broja x */
unsigned last_bit = x & 1;

/* x pomeramo za jedno mesto u desno */
x >>= 1;

/* Zapamceni poslednji bit stavljamo na pocetak broja x*/
x |= last_bit<<wl-1;
}

return x;
}

/* Funkcija obrce binarni zapis neoznacenog broja x tako sto bitove cita unatrag */
unsigned mirror(unsigned x)
{
int i;
int wl = sizeof(unsigned)*8;

/* Rezultat inicijalizujemo na poslednji bit broja x */
unsigned y = x & 1;

/* Postupak se ponavlja wl-1 puta */
for (i = 1; i<wl; i++)
{
/* x se pomera u desno za jedno mesto */
x >>= 1;
/* rezultat se pomera u levo za jedno mesto */
y <<= 1;
/* Poslednji bit broja x upisujemo na poslednje mesto rezultata */
y |= x & 1;
}

return y;
}

main()
{
unsigned x = 0xFAF0FAF0;
print_bits(x);
print_bits(mirror(x));
print_bits(right_rotate(x, 2));
}

Izlaz iz programa:
11111010111100001111101011110000
00001111010111110000111101011111
00111110101111000011111010111100

Zadaci za vezbu:
Zadatak 1. Napisati program koji prihvata sa standardnog ulaza dva niza iste dimenzije i ispisuje na standardni izlaz da li dva niza imaju barem jedan zajednicki element.
Zadatak 2. Napisati operator dodeljivanja koji ce broju x tipa unsigned sacuvati n krajnjih desnih bitova, a ostale postaviti na nulu.
x=x&~(~0 << n); ili x&=~(~0 << n);

Zadatak 3. Napisati operator dodeljivanja koji ce u x ocistiti n bitova (postaviti nule) pocev od pozicije p.
x&=~(~(~0<<n)<<(p-1))

Zadatak 4. Napisati operator dodeljivanja kojim se invertuje x (prevodi jedan u nulu i nula u jedan) pocev od pozicije p na duzini n.
x^=(~(~0<<n)<<(p-1));

67. (naredba break)
Napisati C program koji proverava korektnu uparenost zagrada ( i ) u tekstu koji dolazi sa standardnog ulaza. Npr. zagrade su korektno uparene u izrazu 5 * (8+3), a nisu u izrazu 3 + )2) ili izrazu ( (3+6) * 8

#include <stdio.h> 

main() 
{ 
    int c;    /*tekuci karakter sa ulaza*/
    int br_otv = 0; /*brojac zagrada*/
    while((c=getchar()) != EOF) 
    { 
         if(c=='(')   br_otv++; 
         if (c== ')') 
             { br_otv--; 
              if (br_otv<0) { printf("Visak zatvorenih zagrada\n"); break; } 
             } 
    } 
     if (br_otv == 0) printf("Zagrade su u redu\n"); 
     else      if (br_otv >0) printf("Visak otvorenih zagrada\n"); 
} 

68. (naredba continue) NCP koji prihvata sa standardnog ulaza pozitivan ceo broj n (n <=50), proverava korektnost unete vrednosti, a zatim prihvata po jedan element n-dimenzionalnog niza celih brojeva. Formirati drugi niz koji sadrži samo nenegativne elemente unetog niza, a potom članove drugog niza ispisati na standardni izlaz. /*prepis pozitivnih clanova niza u drugi niz i stampanje drugog niza */

#include <stdio.h>
main()
{
int n; /* dimenzija niza */
int indeks; /* brojac */
int a[50];/*niz celih brojeva iz kog se izdvajaju nenegativni brojevi */
  int j; /*broj nenegativnih clanova*/
  int rezultat[50];/* niz nenegativnih clanova*/
 

/*unos dimenzije niza : 1..50 */
do
{printf("Unesite broj elemenata niza\n");
scanf("%d", &n);
} while (n <1 || n > 50);
 

/* unos clanova niza celih brojeva */
for( indeks=0; indeks<n; indeks++) scanf("%d", &a[indeks]);
 

/* prepis nenegativnih elemenata u niz rezultat */
for( indeks=0, j=0; indeks<n; indeks++)
{

/* ignorisanje clanova niza a koji ne mogu biti clanovi niza rezulat */
if(a[indeks]<0)    continue;
/* dopuni niz rezultat */rezultat[j++]=a[indeks];
}
 

/* ispis niza rezultat */
  printf("\nNovi niz je: ");
  for( indeks=0; indeks<j; indeks++) printf("%d\t", rezultat[indeks]);

printf("\n");
return 0;
}

Biblioteka matematičkih funkcija

69. (zaglavlje math.h) NCP koji unosi realan broj sa standardnog ulaza i ispisuje na standardni izlaz: taj broj, najmanji ceo broj ne manji ( >=) od tog broja, najveći ceo broj ne veći ( <=) od tog broja, kvadratni koren tog broja (ako broj je nenegativan), kub tog broja, kosinus tog broja.

Pri upotrebi kompajlera gcc, mora se upotrebiti opcija -l za naziv biblioteke s kojom se linkuje program, a za matematicku biblioteku libm(#include <math.h>) oznaka je m, tj. kompilacija zad69.c bi mogla biti:
gcc zad69.c -lm -o racunaj


#include <stdio.h>
#include <math.h>
/*NAPOMENA: Funkcije ceil(x), floor(x), sqrt(x), sin(x) su iz zaglavlja math.h
Argumenti su tipa double, rezultati su tipa double*/

 main()
{  double x;
   printf("Unesite broj: ");
   scanf( "%lf", &x);
   printf("\n\nUneli ste: %lf", x);
   printf("\nCeil Vaseg broja: %lf", ceil(x));
   printf("\nFloor Vaseg broja %lf", floor(x));
   if( x >= 0 )  printf("\nKvadratni koren: %lf", sqrt(x) );
    else printf("\nNegativni broj" );
   printf("\nKub Vaseg broja %lf", pow(x,3));
  printf("\nCosinus: %lf\n", cos(x));
 return(0);
}

Testirajte program za x =4.9998887, x=4.11199, x=0.001, x=-0.001, x=0.25, x=0, x=-1, x=1

70. (zaglavlje math.h, funkcija fabs) Napisati C program koji prihvata sa standardnog ulaza koeficijente kvadratne jednacine, a na standrdni izlaz ispisuje njene korene.

/* Program za nalazenje korena kvadratne jednacine */

#include <stdio.h>  
#include <math.h> 

main () {
  double a, b, c,              /* Koeficijenti jednacine                      */
         d,                    /* Diskriminanta jednacine                     */
         x1, x2,               /* Realni koreni                               */
         z1r, z1i, z2r, z2i,   /* Kompleksni koreni                           */
         x;                    /* Resenje linearne jednacine                  */
  int    por;                  /* Poruka o vrsti resenja                      */

  printf ("Koeficijenti kvadratne jednacine: ");
  scanf ("%lf%lf%lf", &a, &b, &c);
  if (! a)
    if (! b)               por = 1;
    else     { x = -c / b; por = 2; }
  else {
    d = b * b - 4 * a * c;
    if (d < 0) {
      z1r = -b / (2 * a); z1i =  sqrt (-d) / (2 * a);
      z2r = z1r;          z2i = - z1i;                por = 3;
    } else {
      x1 = (-b + sqrt (d)) / (2 * a);
      x2 = (-b - sqrt (d)) / (2 * a);                 por = 4;
    }
  }

  switch (por) {
    case 1: printf ("Ulazni podaci nemaju smisla!\a\n");
            break;
    case 2: printf ("Koren linearne jednacine je %g\n", x);
            break;
    case 3: printf ("Kompleksni koreni su %g%ci%g i %g%ci%g\n",
                    z1r, ((z1i >= 0) ? '+' : '-'),  fabs (z1i),
                    z2r, ((z2i >= 0) ? '+' : '-'), fabs (z2i));
            break;
    case 4: if (x1 != x2)
              printf ("Realni koreni su %g i %g\n", x1, x2);
            else
              printf ("Jednacina ima dvostruki koren %g\n",x1);
            break;
  }
}

main()
{
enum {F,T};   /*false,true;0,1*/
int znak,prvi=T; /* znak sa ulaza, indikator pojavepocetka recenice */
 
/* ucitavanje ulaza do markera kraja (EOF) 
i pretvaranje pocetnih slova recenice u velika 
i pretvaranje velikih slova iz sredine recenice u mala slova. */
while ( (znak=getchar() ) != EOF)
{
  if (isupper(znak) )
   { if ( !prvi)            /* if (prvi==0)  */
       znak=tolower(znak);    /*u sredini recenice veliko slovo->malo slovo */
     else prvi=F;           /*napusta se pocetak recenice */
   }
  else  if (islower(znak) )
    { if(prvi)                /*recenica pocinje */
       { znak=toupper(znak);  /*  velikim slovom */
         prvi=F;              /*napusta se pocetak recenice */
       }
     }
  else  /*nije slovo */
   if (znak =='.' || znak=='!' || znak =='?')
      prvi=T;     /*novi pocetak */
  putchar(znak); /*slanje rezultata obrade naizlaz */
}



ZADACI ZA VEZBU
Zadatak 1. Napisati program koji broji pojavljivanja samoglasnika i suglasnika u tekstu koji se
unosi sa standardnog ulaza (koristiti naredbu switch).

Zadatak 2. Napisati program koji broji pojavljivanja za svako od slova engleske abecede u tekstu
koji se unosi sa standardnog ulaza i stampa rezultat na standardni izlaz.

Zadatak 3. Napisati funkciju koja konvertuje malo u veliko slovo.
Napisati program koji prepisuje ulaz na izlaz pri cemu se sva mala slova konvertuju u velika.