PCLP Laborator12: Optimizarea programelor folosind operaţii pe biţi

Obiective

În acest laborator vom studia:

• concepte legate de operații pe biți;
• operatorii folosind în lucrul pe biți;
• mai multe despre organizarea și prelucrarea datelor (în format binar);
• cum putem gestiona eficient memoria folosită în anumite aplicații (prin folosirea operațiilor pe biți);
• cum putem implementa eficient o simplă structură de date în C.

Materiale utile

• [OCW/Suport Teoretic pentru Laborator] Optimizarea programelor folosind operaţii pe biţi

Exerciții

Discutați cu asistentul și scrieți pe tablă rezolvarea pentru exercițiile:

• 0
• 1
• 3
• 4

Veți rezolva individual:

• Toate subpunctele de la exercițiul 5.1, în ordinea indicată în enunț.
  Se vor testa funcționalitățile implementate înainte de a se trece la exercițiul următor.
• Toate subpunctele de la exercițiul 5.2, în ordinea indicată în enunț.

ATENȚIE! Toate sarcinile se vor realiza folosind o abordare modularizată. Discutați cu asistentul alegerile voastre.

ATENȚIE! Se urmărește folosirea corespunzătoare a noțiunilor legate de operații pe biți.

BONUS-urile se rezolvă în următoarea ordine:

• B1
• B2

0: Verificare că un număr e par

Să se verifice folosind operații pe biți că un număr natural n e par.

int is_even(int n);

1. Calcul putere a lui 2

Să se scrie o funcție care să calculeze (2^n), unde ( n <= 30 ).

int pow2(int n);

Întrebări:

• Care este cea mai eficientă variantă de implementare pentru funcția propusă? Implementați această variantă.
• Are sens să scriem o astfel de funcție în C?

2. Negarea biților unui număr n

Să se scrie o funcție care să nege biții unui număr n (32 biți).

int flip_bits(int n);

Răspundeți la întrebarea: are sens să scriem o astfel de funcție?

3. Afișarea biților unui număr n

Să se scrie o funcție care să afișeze toți biții unui număr întreg pe 32 biți.

void print_bits(int n);

4. Verificare că un număr este putere al lui 2

Să se scrie o funcție care verifică dacă un număr întreg n pe 32 biți este puterea a lui 2. Funcția va returna 1 dacă n este putere a lui 2, 0 altfel.

int is_power2(int n);

5. bitset

O mulțime de numere întregi poate fi reprezentată astfel: spunem că un număr i aparține unei mulțimi S dacă bit-ul al i-lea din vectorul S are valoarea 1.

Pentru eficientă, vectorul S va conține date de tipul unsigned char (reamintim ca sizeof(unsigned char) == 1 byte adică 8 biți).

Notă:
Pentru a folosi cu ușurință același cod facând schimbări minime (de exemplu schimbăm dimensiunea maximă a unei mulțimi), putem să ne definim propriul tip astfel:

#define SET_SIZE 100                   // dimensiunea maximă alocată în bytes pentru o structură set
typedef unsigned char SET[SET_SIZE];   // definire tipul SET, care este un vector cu maxim 100 de elemente de tip unsigned char

5.1

Implementați următoarele funcții. Realizați un program în C prin care să demonstrați că funcțiile implementate funcționează.

Notă:
Există un exemplu detaliat care vă explică cum functionează aceastea.
Treceți la subpunctul următor abia după ce v-ați asigurat că acestea funcționează.

• adăugarea unui element în mulțime

  // adaugă numărul n în mulțimea s
  void insert_in_set(SET s, unsigned int n);
  

• ștergerea unui element din mulțime

  // șterge numărul n din mulțimea s
  void delete_from_set(SET s, unsigned int n);
  

• verificarea faptului că un element n aparține unei mulțimi

  // returnează 1 dacă n este în mulțimea s, 0 altfel
  int is_in_set(SET s, unsigned int n);
  

• ștergerea tuturor elementelor din mulțime

  // elimină toate elementele din mulțimea S
  void delete_all_from_set(SET s);
  

• calcularea cardinalul unei mulțimi

  // returnează cardinalul mulțimii s
  int card_set(SET s);
  

• verificarea faptului că mulțimea este vidă

  // returnează 1 daca mulțime s este goală, 0 alfel
  int is_empty_set(SET s);
  

• o funcție care să citească de la tastatură o mulțime

  // citește numărul n de elemente al unei mulțimi s
  // apoi citește cele n numere și le inserează în mulțimea s
  // returnează numărul n
  int read_set(SET s);
  

• o funcție care să afișeze pe ecran elementele care se află într-o mulțime

  // printează elementele mulțimii s
  void print_set(SET s);
  

Urmăriți acest exemplu cu bitset pentru a înțelege cum funcționează aceste operații.

5.2

Realizați un program care, utilizând metodele definite anterior, citește 2 mulțimi A (n și B și afișează: ( A U B, A ∩ B, A - B, B - A ).

Pentru a realiza acest lucru, va trebui să implementați următoarele funcții:

• reuniunea a două mulțimi

  // implementează operația c = a U b, unde a, b și c sunt mulțimi
  void merge_set(SET a, SET b, SET c);
  

• intersecția a două mulțimi

  // implementează operația c = a ∩ b, unde a, b și c sunt mulțimi
  void intersect_set(SET a, SET b, SET c);
  

• diferența a două mulțimi (1p)

  // implementează operația c = a \ b, unde a, b și c sunt mulțimi
  void diff_set(SET a, SET b, SET c);
  

În final va trebui sa creați o funcție main și să faceți un program care rezolvă cerința folosind funcțiile implementate.

B1. Optimizations

O să învățați pe viitor că nu toate înstrucțiunile sunt la fel din punct de vedere al timpului de execuției. Ca un punct de start, gândiți-vă că dacă ați face pe foaie o adunare sau o înmultire, durează mai mult să înmulțiți decât să adunați. Această dificulate o are și procesorul din laptopul vostru!

Pentru a-l ajuta și a face programul mai rapid, putem înlocui operații costisitoare (*, /) cu altele mai puțin costistoare (+, -). Cele mai rapide instrucțiuni sunt cele care lucrează direct pe biți (deoarece numerele sunt stocate în memorie în binar, deci este modul natural de lucru pentru calculator).

Acest exercițiu vă propune să aplicați aceste optimizări pe codul vostru!

B2. MSB/LSB

Să se scrie o câte o funcție pentru aflarea MSB (Most significant bit), respectiv LSB (Least significant bit), pentru un număr n pe 32 biți.

// returnează 2 la puterea i, unde i este LSB
int get_lsb(int n);
// returnează 2 la puterea i, unde i este MSB
int get_msb(int n);

Problemset (extra)

Vă propunem să lucrați acasă probleme din PCLP Laborator12: Problemset (extra).