Bitovski operatori i rad sa karakterima u programskom jeziku C i C++


 

Uporedi vreme izvrsavanja sledeca 2 programa 


#include <iostream>

using namespace std;
const int Nmax=10000000;
int a[Nmax];
int main()
{
    int i, brParnih=0;

    //for (i=0; i<Nmax; i++)  a[i]=3*i+1;
    for (i=0; i<Nmax; i++)  a[i]=3*i+2;

    for (i=0; i<Nmax; i++)
    if (a[i] %2) brParnih++;
    //if (a[i] &1) brParnih++;


    cout <<brParnih << endl;
    return 0;
}


#include <iostream>

using namespace std;
const int Nmax=10000000;
int a[Nmax];
int main()
{
    int i, brParnih=0;

    for (i=0; i<Nmax; i++)  a[i]=3*i+1;
    

    for (i=0; i<Nmax; i++)
    if (a[i] &1) brParnih++;


    cout <<brParnih << endl;
    return 0;
}

Standardna biblioteka ctype.h

PRIMER 

#include <stdio.h>
#include <ctype.h>
main()
{int c;
    c=getchar();
    printf("\nisalpha(%c)=%d", c, isalpha(c));
    printf("\nisdigit(%c)=%d", c, isdigit(c));
     printf("\nisalnum(%c)=%d", c, isalnum(c));
    printf("\nislower(%c)=%d", c, islower(c));    
}
Uporedite naredna dva programa koja ispisuju broj velikih slova, malih slova i cifara u tekstu koji se učitava sa standardnog ulaza do kraja daototeke (EOF):


 BITOVSKI OPERATORI (BITWISE operatori)

& bitovsko AND       1&1=1 0&1=0 0&0=0
Neka bit b ima vrednost 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 -> dekadno 15

 

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

B4, B3, ..., B0 su bitovi na pozicijama 4,3,...0
x binarno Bn Bn-1 ....B4 B3 B2 B1 B0
X&01= Bn Bn-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

 

| BITOVSKO OR       1 | 1 = 1, 1 | 0 =1, 0 | 0 = 0
Ako bit b ima vrednost 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

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

x Bn Bn-1 ... B3 B2 B1 B0
| 0  1    ... 0  0 0   1
==============================
  Bn Bn-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 Bn-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 ostale bitove ne menja

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

 

 

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

X Bn Bn-1 ... B3 B2 B1 B0
| 0  0 ...    1  1  1  0
=====================================
  Bn Bn-1 ... B3 1  1  1

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

^ caret BITOVSKO XOR, XOR JE ekskluzivna disjunkcija
tj. ^ JE not EQUIVALENT

1 ^ 0 = 1, 1 ^ 1 =0, 0 ^ 0 = 0
AKO bit b ima vrednost 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 Bn-1 .... B2 B1 B0
01 -> 0 0   ....  0  0  1
^ ===========================
     Bn Bn-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 / 23,
ali 32 >> 3 se brze izvrsava

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

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


#include <stdio.h>
main()
{
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:

255 & 15 = 15
255 | 15 = 255
255 ^ 15 = 240
2 << 2 = 8
16 >> 2 = 4

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

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


#include <stdio.h>
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


Zadatak 4: NCP koji ucitava sa standardnog ulaza neoznacen ceo broj i ispisuje samo tri najniza (poslednja, krajnja desno) bita tog broja.
IDEJA RESENJA:
x binarno Bn Bn-1 ....B4 B3 B2 B1 B0
X& 7= Bn Bn-1 ....B4 B3 B2 B1 B0
     & 0 0 ....    0 0   1 1   1
===================================
      0 0 ....     0 0   B2 B1   B0

ZAKLJUCAK x & 7 vraca kao rezultat tri bita broja x sa najnizih pozicija B2, B1, B0
Da li Vam ovaj zakljucak pomaze da resite zadatak?
Ako ne, pogledajte resenje, a inace pokusajte sami da resite zadatak.

Zadatak 5: NCP koji ucitava sa standardnog ulaza neoznacen ceo broj i ispisuje taj broj sa postavljenim petim bitom na 1cu. (Pogledajte jedan od gore navedenih primera).

Zadatak 6: NCP koji ucitava sa standardnog ulaza neoznacen ceo broj i ispisuje taj broj sa postavljenim petim bitom na nulu. (Pogledajte jedan od gore navedenih primera).

 

62. 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. Uzeti u obzir da numeracija bitova je takva da bit najmanje tezine (krajnji desno) je nulti bit, a ne prvi bit.

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

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

return 0;
}

63. NCP koji postavlja na k-to mesto 1

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

unsigned n,k;

printf("Unesite broj i poziciju tog broja koju zelite da proverite:\n");
scanf("%u%u",&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.

64. 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;
}

Rešen primer za vežbu: 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');
}

 

/* uporedite sa funkcijom iz prethodnog zadatka */
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));
}

Rešen primer za vežbu: Napisati funkcije get bits, set bits, invert bits za (redom) izdvajanje, postavljanje i invertovanje pojedinacnih bitova. Potom napisati C program koji ilustruje rad ovih funkcija.


#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

65. Napisati funkcije :

  1. unsigned right_rotate(unsigned x, int n) koja vrsi rotaciju neoznacenog broja x za n pozicija udesno
  2. unsigned mirror(unsigned x) koja obrce binarni zapis neoznacenog broja x tako sto bitove cita unatrag
Potom napisati C program koji ilustruje rad ovih funkcija.

#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 7. 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 8. Napisati operator dodeljivanja koji ce u x ocistiti n bitova (postaviti nule) pocev od pozicije p.
x&=~(~(~0<<n)<<(p-1))


Zadatak 9. 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));