Tmp cerc 6

From Algopedia
Jump to navigationJump to search

Lecție

Reprezentarea în memorie a valorilor întregi

Valorile întregi se reprezintă în memorie ca o secvență de biți (cifre binare, 0 și 1). Acestă secvență poate avea 8, 16, 32 sau 64 de biți. Reprezentarea în memorie a datelor de tip întreg se face în mod similar pentru toate tipurile cu semn (char, short int, int, long long int) și similar pentru toate tipurile fără semn (unsigned char, unsigned short int, unsigned int, unsigned long long int). În exemplele care urmează vom folosi tipurile reprezentate pe 16 biți: unsigned short int, respectiv short int. Reprezentarea în memorie a valorilor de tip unsigned short int Tipul unsigned short int memorează valori mai mari sau egale cu 0. Acestea se reprezintă în memorie astfel:

  • se transformă numărul în baza 2 și se memorează, adăugând la început cifre de 0 nesemnificative, atâtea câte sunt necesare până la completarea celor 16 biți.
  • dacă reprezentarea în baza 2 a numărului are mai mult de 16 cifre, se vor memora numai ultimele 16 cifre – numărul se va trunchia.

Astfel, valorile fără semn care se pot reprezenta pe 16 biți sunt cuprinse între 0 și 216-1, adică 0 și 65535.

0 se reprezintă     0000000000000000
65535 se reprezintă 1111111111111111
5 se reprezintă     0000000000000101
133 se reprezintă   0000000010000101

Reprezentarea în memorie a valorilor de tip short int Tipul short int memorează atât valori pozitive, cât și valori negative. Astfel, dintre cei 16 biți disponibili, cel mai din dreapta (numit bit de semn) stabilește semnul numărului. Dacă acest bit este 0, numărul este pozitiv, dacă acest bit este 1, numărul este negativ. Astfel, se pot memora 32768 valori negative, de la -32768 la -1, și 32768 pozitive sau zero, de la 0 la 32767. Modalitatea de reprezentarea în memorie a întregilor se numește cod complementar. Reprezentarea numerelor pozitive se face exact ca mai sus: se transformă numărul în baza 2 și se completează cu zerouri nesemnificative. Nu la fel se face reprezentarea numerelor întregi negative. Această reprezentare se face conform pașilor următori: se determină reprezentarea în memorie a numărului ce reprezintă valoarea absolută a numărului inițial. Aceasta are bitul de semn 0. se determină complementul față de 1 a reprezentării de la pasul anterior – fiecare bit 1 devine 0 și fiecare bit 0 devine 1. se adună 1 la valoarea obținută De exemplu, pentru reprezentarea în memorie a numărului -133 (considerat de tip short int) se procedează astfel:

se determină reprezentarea în memorie a lui 133
se obține complementul față de 1
se adună 1 și se obține:
0000000010000101
1111111101111010
1111111101111011

Mecanismul de memorare numerelor este același pentru toate tipurile întregi. Diferă numai numărul de biți folosiți pentru reprezentare și implicit intervalul din care fac parte valorile reprezentate.

Operatori logici pe biti

Operatorii la nivel de bit se aplica fiecărui bit din reprezentarea operanzilor întregi, spre deosebire de restul operatorilor care se aplică valorilor operanzilor.

Din această categorie fac parte operatorii următori, care apar in ordinea descrescatoare a priorității:

Negaţia pe biţi ~

Acest operator are ca efect schimbarea biților unui număr din 0 in 1 si din 1 in 0.

Deplasarea la stânga/ la dreapta pe biți <<, >>

  • Expresia x << i este echivalentă cu expresia x * 2i. Are ca efect eliminarea celor mai din stânga i biţi ai lui x şi adaugarea la dreapta i biţi de 0.

De exemplu, dacă x = 1110(2), atunci x << 2 înseamnă 111000(2) = 56 (adică 14 * 22).

  • Expresia x >> i este echivalentă cu x div 2i . Operatorul de deplasare la dreapta elimină cei mai din dreapta i biţi ai lui x şi adaugă la stânga i biţi de 0.

De exemplu, dacă x = 1110(2), atunci x >> 2 înseamnă 0011(2) = 3 (adică 14 div 22).

Si pe biţi &

n1  1010 & 
n2  1011 = 
rez 1010

Sau exclusiv pe biţi (xor) ^

n1  1010 ^ 
n2  1011  
rez 0001 

Sau pe biţi |

n1  1010 | 
n2  1011  
rez 1011 

Prioritatea operatorilor ( precedenta operatorilor )

Operator Descriere Asociativitate
~ Complement faţă de 1 pe biţi dreapta-stânga
<< si >> Deplasare stânga/dreapta a biţilor stânga-dreapta
& ŞI pe biţi stânga-dreapta
^ SAU-EXCLUSIV pe biţi stânga-dreapta
| SAU pe biţi stânga-dreapta
&= și |= Atribuire cu ŞI/SAU dreapta-stânga
^= Atribuire cu SAU-EXCLUSIV dreapta-stânga
<<= şi >>= Atribuire cu deplasare de biţi dreapta-stânga

Aplicații ale operatorilor pe biţi

Inmultirea cu 2

Se citeşte un număr natural n. Să se afişeze valoarea 2*k. Vom folosi operatorul de deplasare la stânga pe biţi: n << 1. Deci secvenţa va fi:

 
scanf("%d", &n);
printf(n << 1) ;    //echivalent cu n = n * 2;
x = 1 << 2;         100 = 4 = 2^2
// vectorii x si s vor fi declarati global asa ca nu ne vor trebui parametri in functie
void scadere()
{ int i,j;
for (i = 1; i <= x[0]; i++)
        if(x[i]>=y[i])
            x[i]-=y[i];
        else
        {
            j=i+1;
            while(x[j]==0)
                x[j++]=9;
            x[j]--;
            x[i]=10+x[i]-y[i];
        }
    while(x[x[0]]==0)
        x[0]--;//nu vom afisa si zerourile de la inceput
}

Catul impartirii la 2

Se citeşte un număr natural n. Să se afişeze valoarea n/2. Vom folosi operatorul de deplasare la stânga pe biţi: n >> 1. Deci secvenţa va fi:

 
scanf("%d", &n);
printf(n >> 1) ;   //echivalent cu n = n / 2;

Restul impartirii la 2

Se citeşte un număr natural n. Să se afişeze valoarea n % 2. Vom aplica operatorul & între n si numărul 1 (numărul 1 joacă rol de mască). Aceasta masca are primii biţi 0 si ultimul bit 1. Astfel incat dacă n & 1 va avea ca efect extragerea ultimei cifre binare a lui n.

 
scanf("%d", &n);
printf(n & 1) ;   //echivalent cu n = n % 2; catul impartirii la 2;

Verificarea parității

Se consideră un număr natural n. Să se verifice dacă n este par sau impar.

Ex1: pentru n este impar, avem ultima cifra binara 1. De exemplu, n = 13 se scrie în baza 2 ca 1101. Atunci

1101 & 
0001 =
0001

Ex2: pentru n este par, avem ultima cifra binara 0. De exemplu, n = 14 se scrie în baza 2 ca 1110.Atunci

1110 & 
0001 = 
0000 
scanf("%d", &n);
if (( n & 1 ) == 1) printf( "Numar impar" );
else cout << printf("Numar par") ;

ATENȚIE! operatorul &, ca si operatorii ^ si |, are prioritate mai mica decat operatorul ==, de aceea este necesara utilizarea parantezelor pentru a da prioritate operatorului & în expresia instrucţiunii if. ( Expresia n & 1 == 1 este interpretată de compilator ca fiind n & (1 == 1) )

2 la puterea k

Se citeşte un număr natural k <= 15. Să se afişeze valoarea 2k. Vom folosi operatorul de deplasare la stânga pe biţi: 1 << k.

 
scanf("%d", &k);
printf("%d", 1 << k) ;

Câtul și restul împărțirii lui n la 2k

Se consideră un număr natural n. Să se determine câtul şi restul împărţirii lui n la un număr m de forma 2k.

Împărțirea unui număr zecimal la o putere a lui 10 are ca efect împărțirea numarului zecimal in 2 părți: câtul și restul impărțirii numarului la puterea lui 10. Similar, împărțirea unui număr la o putere a lui 2, separă reprezentarea binara a acestuia de asemenea în 2 zone: câtul și restul impărțirii numarului la puterea lui 2.

Ex: pentru numarul : 12345 prin impărțire la 100 separăm numarul in 2: 12345; 123 = n div 100, 45 = n mod 100.

Similar pentru reprezentarea binara:

n = 20 = 10100 n div 4 = 101 (2) = 5 (10) n mod 4 = 00 (2) = 0 (10)

Putem să obținem aceleași rezultate și prin folosirea operațiilor pe biți. Pentru aflarea câtului vom folosi operatorul de deplasare pe biți. Trebuie însă să îl știm pe k = puterea lui 2.

Pentru rest se utilizează expresia n & (m-1) , deoarece m-1 are toti biții 1, m-1 si in acest fel extragem doar ultimii m-1 biți.

 
scanf("%d", &n);
printf("Catul este : %d", n >> k ) ;
printf("Restul este : %d", (n & (m-1) ) ;

Ex: 20 div 4 = 20 >> 2 = 5

10100 
  >>2=
00101

20 mod 4 = 20 & 3 = 0

10100 &
00011=
00000

Verificare daca n este o putere a lui 2

Se consideră un număr natural n. Să se verifice dacă n este sau nu o putere a lui 2. Rezolvare: Acesta este o problemă destul de cunoscută. Dacă n este o putere a lui 2, atunci reprezentarea sa în baza 2 are un singur bit 1, restul fiind 0. Ceea ce inseamna ca daca vom incerca sa eliminam ultimul bit semnificativ de 1, folosind masca ( n-1 ) va trebui sa obtinem valoarea 0.

( Dacă n este o putere a lui 2, este de forma 0000000000100000, atunci n-1 are reprezentarea de forma 0000000000011111, adică bitul 1 s-a transformat în 0, iar biţii de la dreapta sunt acum toţi 1. Deci o expresie de forma n & (n-1) va furniza rezultatul 0 dacă şi numai dacă n este o putere a lui 2. )

scanf ( "%d", &n) ;
if ( (n & (n-1)) == 0 ) 
  printf( "n este putere a lui 2" );
else 
  printf( "n nu este putere a lui 2") ;

Numararea bitilor de 1 din scrierea binară a unui număr n

Rezolvarea naivă a acestei probleme ar consta în parcurgerea secvenţială a biţilor lui n. În continuare vă prezint această rezolvare:

int count(long n) {
    int num = 0;
    for (int i = 0; i < 32; i++)
        if (n & (1 << i)) num++;
    return num;
}

Dacă ne uităm cu atenţie şi analizăm rezultatul operaţiei n & (n - 1) putem obţine o soluţie mai bună. Să luăm un exemplu:

11011101010000 = n
11011101001111 = n - 1
11011101000000 = n & (n - 1)

Se vede clar de aici că efectul operaţiei n & (n - 1) este anularea celui mai nesemnificativ bit cu valoarea 1.

De aici ideea algoritmului:

int count(long n) {
    int num = 0;
    if (n)
        do num++; while (n &= n - 1);
    return num;
}

Transformarea unui bit în 1

Pornim de la valoarea întreagă n = 50. Reprezentarea acestuia pe 8 biti este 00110010. Presupunem că dorim setarea bitului 2 la valoarea 1. Pentru aceasta vom folosi o mască logică în care doar bitul 2 este 1 restul bitilor fiind 0, adică M = 00000100. Pentru a obtine valoarea lui M vom deplasa valoarea 1 cu spre 2 biti spre stanga. Aplicand operatia de de disjunctie "SAU pe biti" aplicată asupra lui n şi a lui M, conduce la obtinerea rezultatului dorit.

n   00110010 |
M   00000100  
Rez 00110110 

Generalizând, dacă se doreşte ca valorii n, să i se seteze la valoarea 1, bitul B (0≤B≤7), atunci vom avea:

n = n | (1 << B)

Transformarea unui bit în 0

Să luăm ca exemplu n= 109, pentru a vedea cum se setează un bit la valoarea 0. Reprezentarea internă a lui este 01101101. Se cere să se seteze bitul 5 la valoarea 0. De data aceasta masca va conŃine toti bitii de 1, exceptie bitul 5. Aspura lui n şi M vom aplica ŞI logic.

n    01101101 &  
M    11011111  
Rez  01001101 

Presupunem că dorim să setăm la 0 valoarea bitului B (0≤B≤7).

n = n & ~(1 << B)

Testarea valorii unui bit

Plecăm de la valoarea n = 47. Reprezentarea internă a lui este 00101111. Presupunem că dorim să cunoaştem valoarea bitului 3 şi bitului 6. Vom folosi măştile M1=00001000 şi M2=01000000. Vom aplica de fiecare dată ŞI logic între n şi cele două măşti:

n   00101111 &  
M1  00001000  
Rez 00001000 

Respectiv

n   00101111 &  
M2  01000000  
Rez 00000000 

Generalizând, testarea se va realiza prin : n & ( 1 << B )

Testarea valorilor ultimilor biti

Pornim de la valoarea întreagă n=50. Reprezentarea acestuia pe 8 biti este 00110010. Presupunem că dorim să cunoaştem restul la împărtirea întreagă a lui n la 8, adică n%8. Valoarea ultimilor 3 biti din reprezentarea internă a lui, reprezintă tocmai acest rest. Pentru aceasta vom folosi o mască în care ultimii trei bitii sunt 1 restul 0. Aceasta mască are valoarea 7, adică 00000111. Vom aplica operatia ŞI logic.

n   00110010 &  
M   00000111  
Rez 00000010 

Pe caz general, dacă dorim să cunoaştem valoarea ultimilor B biti (care este egal cu restul împărtirii lui X la 2B) vom exprima astfel:

n & (1 << B–1)

Scrierea numarului n in baza 2

???Se consideră un număr natural n. Să se afişeze reprezentarea lui n în baza 2. Rezolvare: Ne bazăm pe faptul că în memorie n este deja reprezentat în baza 2, deci trebuie să-i afişăm biţii de la stânga la dreapta. Presupunând că n este reprezentat pe 16 biţi, pe aceştia îi numerotăm de la dreapta la stânga cu numere de la 0 la 15. Pentru a obţine bitul de pe poziţia i (0 <= i <= 15), utilizăm expresia (n >> i) & 1. Nu rămâne decât să utilizăm expresia pentru fiecare i între 0 şi 15.

cin >> n ;
for (int I = 15 ; i >= 0 ; i--)
   cout << ((n >> i) & 1) ;

Memorarea a doi intregi <255 intr-o singura locatie de memorie

Se consideră două numere naturale a şi b, ambele cuprinse între 0 şi 255. Se cere să se memoreze cele două numere într-un întreg n reprezentabil pe 16 biţi fără semn (deci de tip unsigned short). Rezolvare: Cele două numere a şi b pot fi reprezentate pe 8 biţi. De aceea cei 16 biţi ai lui n sunt suficienţi. Stocăm a pe primii 8 biţi ai lui n, iar pe b pe ultimii 8 biţi ai lui n. n = a * 256 + b ; De asemenea, dacă se cunoaşte n, se pot obţine valorile lui a şi b astfel: a = n >> 8 ; // sau a = n / 256 b = n & 255 ; // sau b = n % 256 ;

Codificare/decodificare

Considerăm un număr pe care dorim să-l codificăm, apoi să-l decodificăm. Rezolvare: O modalitate simplă de codificare şi decodificare este utilizarea operatorului pe biţi XOR. Pentru aceasta considerăm o mască (o parolă) şi ne bazăm pe o proprietate interesantă a operatorului XOR: a ^ b ^ b = a. Deci a ^ b realizează codificarea lui a, iar (a ^ b) ^ b realizează decodificarea. Proprietatea se bazează pe faptul că b ^ b = 0, pentru orice b, iar a ^ 0 = a. Metoda poate fi aplicată şi pentru codificarea unui text utilizând o parolă dată. Cu ajutorul parolei aplicată peste textul iniţial se obţine codificarea, iar o a doua aplicare a parolei peste codificare se obţine textul iniţial. Secvenţa care realizează codificarea/decodificarea unui număr este: int n, masca; n = 65 ; masca = 100 ; cout << "\nValoarea initiala a lui n : " << n ; n = n ^ masca ; cout<< "\nValoarea codificata a lui n : " << n ; n = n ^ masca ; cout<< "\nValoarea decodificata a lui n : " << n ;

TEMA

Pentru o mai buna fixare a operatiilor pe biti, va sfatuiesc ca din cand in cand sa mai rezolvati cate o problema. Aveti aici cateva probleme:

Multimi reprezentate pe biti

Sarcina 1

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 int) == 1 byte adică 8 biți). Implementați următoarele funcții. Realizați un program în C prin care să demonstrați că funcțiile implementate funcționează. Vom considera ca urmatoarele constante se aplica pe parcursul urmatoarelor exemple:

  const int MAXN = 1e4; // se seteaza dupa caz
  const int LOG_BYTE = 3;
  const int SIZE = (MAXN >> LOG_BYTE) + 1;
  • adăugarea unui element în mulțime
  // insert_in_set(s, n) - adauga numarul n in multimea s 
  void insert_in_set(char s[SIZE], unsigned int n) {
    s[n >> LOG_BYTE] |= (1 << (n & ((1 << LOG_BYTE) - 1)));
  }
  • ștergerea unui element din mulțime
  // delete_from_set(s, n) - scoate numarul n din multime s
  void delete_from_set(char s[SIZE], unsigned int n) {
    s[n >> LOG_BYTE] &= ~(1 << (n & ((1 << LOG_BYTE) - 1)));
  }


  • verificarea faptului că un element n aparține unei mulțimi
  // is_in_set(s, n) - returneaza 1 daca n este in s, 0 altfel
  int is_in_set(char s[SIZE], unsigned int n) {
    return (s[n >> LOG_BYTE] &= (1 << (n & ((1 << LOG_BYTE) - 1)))) > 0;
  }
  • ștergerea tuturor elementelor din mulțime
  // delete_all_from_set(s) - elimina toate elementele din multime
  void delete_all_from_set(char s[SIZE]) {
    for (int i = 0; i < SIZE: ++i)
      s[i] = 0;
  }
  • calcularea cardinalul unei mulțimi
  /// card_set(s) - returneaza cardinalul multimii s
  int card_set(char s[SIZE]) {
    int c = 0;
    for (int i = 0; i < SIZE; ++i) {
      int aux = s[i];
      while (aux > 0) {
        aux &= (aux - 1);
        ++c;
      }
    }
    return c;
  }
  • verificarea faptului că mulțimea este vidă
  // is_empty_set(s) - verifica daca multimea este sau nu goala
  // returneaza 1 daca este, 0 daca nu este
  int is_empty_set(char s[SIZE]) {
    for (int i = 0; i < SIZE; ++i)
      if (s[i])
        return 0;
    return 1;
  }
  • o funcție care să citească de la tastatură o mulțime
  // read_set(s) - functia citeste numarul n de elemente care se afla in s
  // apoi citeste cele n numere si le insereaza in a
  // va returna numarul n citit (numarul de elemente)
  int read_set(char s[SIZE]) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      int num;
      scanf("%d", &num);
      insert_in_set(s, num);
    }
    return n;
  }
  • o funcție care să afișeze pe ecran elementele care se află într-o mulțime
  // print_set(s) - functia printeaza elementele multimii s
  void print_set(char s[SIZE]) {
    for (int i = 0; i < (SIZE << LOG_BYTE); ++i)
      if (is_in_set(s, i))
        printf("%d\n", i);
  }

Sarcina 2

Realizati un program care, utilizând metodele de fite anterior, citește 2 mulțimi A (n și B și a fișează: AUB,A∩B,A−B,B−A AUB,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 (1p)
  // c = a U b
  void merge_set(char a[SIZE], char b[SIZE], char c[SIZE]) {
    for (int i = 0; i < SIZE; ++i)
      c[i] = (a[i] | b[i]);
}
  • intersecția a două mulțimi (1p)
  // c = a n b
  void intersect_set(char a[SIZE], char b[SIZE], char c[SIZE]) {
    for (int i = 0; i < SIZE; ++i)
      c[i] = (a[i] & b[i]);
}
  • diferența a două mulțimi (1p)
  // c = a \ b
  void diff_set(char a[SIZE], char b[SIZE], char c[SIZE]) {
    for (int i = 0; i < SIZE; ++i)
      c[i] = (a[i] ^ (a[i] & b[i]));
}

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

Lista de probleme

Probleme rezolvate:

http://www.infoarena.ro/operatii-pe-biti http://campion.edu.ro/arhiva/www/arhiva_2009/papers/paper21.pdf

Tema 5

Infoarena

Tema