FAQ C: Reprezentarea numerelor în calculator și lucrul pe biți

Reprezentarea numerelor în calculator și lucrul pe biți

Săptămâna aceasta este despre biți. De ce? Pentru că ei sunt unitatea de bază prin care este reprezentată informația în calculator. Și pentru că deși nu ne este de multe ori vizibil acest lucru, calculatorul funcționează și operează la nivel de biți. Lucrul pe biți este important atunci când discutăm despre eficiența și despre optimizarea programelor pe care le dezvoltăm.

Cum sunt reprezentate numerele în calculator? Ce este complementul față de 2 al unui număr? Cum funcționează operația de shiftare și de ce este folositoare? Când apare fenomenul de overflow?

Dorim să răspundem acestor nelămuriri și să clarificăm folosirea operațiilor pe biți, abordând probleme și greșeli cu care te poți confrunta. În plus, discutăm și câteva întrebări recurent întâlnite la interviurile tehnice și exemple în care este favorabil să lucrezi pe biți. Așa că… să o luăm cu începutul!

 

Cum arată informația într-un calculator?

Orice calculator are informațiile structurate sub forma unor înșiruiri de cifre de 0 și 1, o astfel de cifră având denumirea de bit. Astfel, calculatoarele funcționează în baza de numărare 2. Cu toate că noi suntem obișnuiți să lucrăm în baza 10, folosind cifre cu valori cuprinse între 0 și 9, calculatorul nu lucrează decât pe biți, a căror valoare este fie 0, fie 1.

Numerele sunt și ele, deci, reprezentate în binar, un număr fiind de fapt o secvență de 8, 16, 32 sau 64 de biți. Majoritatea procesoarelor folosite în prezent au o arhitectură de 32 de biți, sau de 64 de biți. Acest lucru, printre altele, ne spune care este dimensiunea maximă pe care putem reprezenta un număr.

Numim byte (sau octet) un șir de 8 biți. Acest lucru ne dă posibilitatea să avem mai multe tipuri de date, iar astfel, numerele pot fi reprezentate pe 1, 2, 4 sau 8 bytes. În C, putem da exemplu câteva astfel de tipuri de date folosite uzual:

char – reprezentare pe 1 byte
short – reprezentare pe 2 bytes
int – reprezentare pe 4 bytes
long long int – reprezentare pe 8 bytes

Tipul char este folosit în general atunci când lucrăm cu caractere, iar următoarele trei tipuri din exemplu sunt folosite pentru reprezentarea numerelor întregi.

Spunem despre tipurile de date enumerate mai sus că sunt signed. Acest lucru înseamnă că variabilele declarate cu unul dintre aceste tipuri poate lua atât valori pozitive, cât și valori negative. Și totuși, cum își dă seama calculatorul dacă valoarea unui număr cu semn este pozitivă sau negativă?

Ei bine, la variabilele signed, primul bit din stânga este rezervat pentru a indica semnul numărului – dacă bitul are valoarea 0, atunci semnul numărului este „+” și în cazul în care valoarea este 1, semnul numărului este „-”. Să vizualizăm un pic acest lucru, folosind ca și exemplu un număr reprezentat pe 8 biți:

N₂  = 01011100
N₁₀ = 92

Primul bit este 0, așadar semnul numărului este „+”.

N₂  = 11011100
N₁₀ = -92

Primul bit este 1, așadar semnul numărului este „-”.

Dacă o variabilă este unsigned, atunci primul bit este considerat ca făcând parte din număr și nu este considerat bit de semn. Astfel, dacă am presupune că N este o variabilă fără semn, în cazul de mai sus, am obține:

N₂  = 01011100
N₁₀ = 92

N₂  = 11011100
N₁₀ = 220

De această dată, știm sigur că numărul este reprezentat fără semn și că va fi întotdeauna pozitiv.

Totuși, în funcție de arhitectura calculatorului, există mai multe metode de a reprezenta numerele negative. Pe lângă metoda prezentată mai sus, reprezentarea numerelor se poate face și folosind complementul față de 1, sau complementul față de 2 al unui număr.

 

Complementul față de 1 și complementul față de 2 al unui număr

Complementul față de 1 al unui număr se calculează folosind negarea fiecărui bit (0 devine 1 și 1 devine 0), aplicată pe valoarea pozitivă a numărului.  

Avem numărul -6₁₀. Luăm valoarea fără semn a numărului și o transformăm în baza 2:
6₁₀ = 0110₂
Inversăm valoarea fiecărui bit:
0110 => 1001
Și astfel, am obținut reprezentarea în complement față de 1 a lui -6: 1001.

Complementul față de 2 al unui număr x este rezultatul operației 2^N– | x |, unde notăm:
→ N – numărul de biți pe care este reprezentat numărul
→ | x | – valoarea pozitivă a numărului x

Avem numărul -6₁₀. Luăm valoarea fără semn a numărului și o transformăm în baza 2:
6₁₀ = 0110₂
Deoarece luăm în considerare și bitul de semn, obținem:
N = 4
Calculăm conform formulei date mai sus:
2^N– |x| =2⁴– | -6 | = 16 – 6 = 10
Transformăm valoarea obținută în binar și avem:
10 = 1010₂
Astfel, am obținut reprezentarea în complement față de 2 a lui -6: 1010.

Cea mai cunoscută și folosită metodă de reprezentare a numerelor în prezent este cea a complementului față de 2. Acest lucru este datorat faptului că facilitează efectuarea operațiilor aritmetice pe numere întregi. De asemenea, spre deosebire de celelalte două metode menționate, această reprezentare are o singură reprezentare pentru 0.

Vom detalia ulterior, în următoarele săptămâni conceptele de tipuri de date în C și folosirea variabilelor signed și unsigned.

 

Operații pe biți

În primul rând, menționăm cele patru operații logice: AND, OR, XOR și NOT. Fiind operații logice, fiecare dintre ele are un tabel de adevăr, ce spune care este rezultatul aplicării operației pe biți. Să urmărim cum funcționează fiecare dintre ele la nivel de biți și cum arată tabelele de adevăr în următoarele exemple:

 

AND (ȘI-LOGIC) – în C, operatorul este &

Operația AND primește doi biți și are ca rezultat 1 doar atunci când ambii biți au valoarea 1 și 0 în caz contrar.

Tabelul de adevăr este: x y output 0 0 0 0 1 0 1 0 0 1 1 1

Exemplu:                        01101101 & 01001011  ——————- 01001001

OR (SAU-LOGIC) – în C, operatorul este |

Operația OR primește doi biți și are ca rezultat 1 atunci când cel puțin unul dintre biți este 1 și 0 atunci când ambii biți au valoarea 0.

Tabelul de adevăr este: x y output 0 0 0 0 1 1 1 0 1 1 1 1

Exemplu:                       01101101 | 01001011  ——————- 01101111

XOR (SAU-EXCLUSIV) – în C, operatorul este ^

Operația XOR primește doi biți și are ca rezultat 1 atunci când biții au valori diferite și 0 în caz contrar.

Tabelul de adevăr este: x y output 0 0 0 0 1 1 1 0 1 1 1 0

Exemplu:                        01101101 ^ 01001011  ——————- 00100110

NOT (NU-LOGIC) – în C, operatorul este ~

Operația NOT primește un singur bit și inversează valoarea acestuia. Astfel, transformă valoarea 0 în 1 și valoarea 1 în 0.

Tabelul de adevăr este:   x   output 0 1 1 0

Exemplu:                      ~01101101   ——————-   10010010

După cum se observă, operația NOT am folosit-o atunci când am calculat complementul față de 1 al unui număr. Aceasta poate fi folosită și când calculăm complementul față de 2. Modul de folosire este următorul:

Avem numărul -6₁₀.
Considerăm valoarea pozitivă a numărului și o scriem în binar:
6₁₀=0110₂
Aplicăm operația NOT pe numărul în binar:
~0110 = 1001
Adunăm 1 la rezultat și obținem:
1001 + 0001 =1010
Astfel, rezultatul este egal cu cel obținut prin formulă: 1010.

În afară de operațiile descrise mai sus, mai există și operațiile SHIFT LEFT, respectiv SHIFT RIGHT. Procesul de „shiftare” este de fapt translatarea biților, fie spre stânga fie spre dreapta cu un număr de poziții.

 

SHIFT LEFT (in C, operatorul este <<)

Sintaxa în C, având o variabilă x, este următoarea:

x << N;                     // N – numărul de poziții cu care se vor muta biții la stânga

Luăm și un exemplu numeric:

x₂= 00001011 = 11₁₀
N = 2
x<< N = 00001011 << 2 = 00101100 = 44₁₀

Astfel, biții s-au mutat la stânga cu 2 poziții. Cei doi biți având valoarea 0 din numărul inițial nu mai sunt luați în considerare. La final, pe pozițiile rămase „libere”, se vor pune biți de 0. După cum se observă din reprezentarea în baza 10, după realizarea operației de SHIFT LEFT, numărul a fost înmulțit cu 4. Dar 4 = 2². Să vedem ce se întâamplă pentru N = 3.

x << N = 00001011 << 3 = 01011000 = 88₁₀

Observăm că numărul a fost înmulțit cu 8. Dar 8 = 2³.

Generaelizat, operația de SHIFT LEFT cu N poziții realizează înmulțirea unui număr cu 2^N.

 

SHIFT RIGHT (in C, operatorul este >>)

Sintaxa în C, având o variabilă x, este următoarea:

x >> N;                     // N – numărul de poziții cu care se vor muta biții la dreapta

Să observăm ce se întâmplă pe un exemplu numeric:

x₂= 00011100 = 28₁₀
N = 2
x>> N = 00011100 >> 2 = 00000111 = 7₁₀

Nu detaliem foarte mult, fiindcă operația SHIFT RIGHT este opusul operației SHIFT LEFT: biții sunt translatați la dreapta cu N poziții.

Analog, operația de SHIFT RIGHT cu N poziții realizează împărțirea unui număr la 2^N.

În realizarea operațiilor SHIFT LEFT și SHIFT RIGHT, cele mai întâlnite probleme sunt situația de overflow și folosirea unor numere negative. Aceste probleme le vom trata ulterior, în săptămânile următoare.

 

Greșeli frecvente în folosirea operațiilor logice

Confundarea operatorilor „!” și „~”

Operatorul „!” realizează transformarea din „fals” (=0) în „adevărat” și din „adevărat” (orice e diferit de 0) în „fals”.

!00101 = 0
!00000 = 1

Operatorul „~” realizează inversarea valorii biților. Orice bit cu valoarea 1 devine 0 și orice bit cu valoarea 1 devine 0.

~00101 = 11010
~00000 = 11111

Confundarea operatorilor „&&” și „&”

Operatorul „&&” este folosit în evaluarea expresiilor. Acesta realizează operația de ȘI-LOGIC, folosind tabelul de adevăr al operației AND și returnează 1 dacă valorile tuturor elementelor din expresie sunt diferite de 0 (deci evaluate ca „adevărat”).

00110111 && 01001011 = 1
00000000 && 01100101 = 0

Operatorul „&” efectuează operația de ȘI-LOGIC, conform tabelului de adevăr AND, la nivel de biți.

00110111 & 01001011 = 00000011
00000000 & 01100101 = 00000000

Confundarea operatorilor „||” și „|”

Operatorul „||” este folosit în evaluarea expresiilor. Atunci când cel puțin un element din expresie are valoarea diferită de 0 (deci „adevărat”), returnează 1.

00000000 || 01001011 = 1
00000000 || 00000000 = 0

Operatorul „|” efectuează operația de SAU-LOGIC, conform tabelului de adevăr OR, la nivel de biți.

00000000 || 01001011 = 01001011
00000000 || 00000000 = 00000000

 

Întrebări frecvent întâlnite la interviuri tehnice

Lucrul pe biți este un subiect preferat când vine vorba de interviurile tehnice, așa că am selectat câteva exemple de astfel de întrebări.

Interschimbarea valorilor a două variabile fără a folosi o variabilă auxiliară

    INPUT
        37
    OUTPUT
        a = 7, b = 3

Exemplu:
    a = 0011; b = 0100
    a = a ^ b => a = 0011 ^ 0100 = 0111
    b = a ^ b => b = 0111 ^ 0100 = 0011
    a = a ^ b => a = 0111 ^ 0011 = 0100

Verificarea parității unui număr

    INPUT
    a = 33
    OUTPUT
    Numarul este impar.

    INPUT
    a = 24
    OUTPUT
    Numarul este par.

Explicația este aceea că orice număr par are bitul cel mai din dreapta 0, iar orice număr impar îl are 1. Astfel, dacă aplicăm operația & între număr și 1, obținem 0 atunci când numărul este par și 1 atunci când numărul este impar.

Să se verifice dacă un număr este putere a lui 2

    INPUT
    a = 32
    OUTPUT
    Numarul este putere a lui 2.

    INPUT
    a = 56
    OUTPUT
    Numarul nu este putere a lui 2.

Exemplu:
    a = 00010000 (16₁₀)

    00010000 & 00001111 = 00000000 => Numarul este putere a lui 2
 

Sumar. Cuvinte cheie

Acestea fiind spuse, ajungem la finalul primului articol din seria FAQ C. Așa că… hai să amintim puțin ce am discutat:

• Informațiile în calculator, incluzând numerele, sunt reprezentate în baza 2.
• Există mai multe tipuri de date în C și numerele pot fi reprezentate pe 1, 2, 4 sau 8 bytes.
• Există mai multe metode de reprezentare a numerelor cu semn în calculator, cele mai cunoscute fiind:

    – folosirea celui mai semnificativ bit pentru a stabili semnul numărului
    - complementul față de 1 al numărului
    - complementul față de 2 al numărului

• Complementul față de 1 al unui număr negativ se calculează prin aplicarea operației NOT pe valoarea pozitivă a numărului.
• Complementul față de 2 al unui număr negativ se calculează în 2 moduri:

•     folosirea formulei 2^N– | x |
•     aplicarea operației NOT pe valoarea pozitivă a numărului și adăugarea valorii 1

• Operațiile logice de bază sunt AND, OR, XOR, NOT.
• Operația de SHIFT LEFT realizează translatarea biților unui număr spre stânga cu N poziții și este echivalentul înmulțirii numărului cu 2N.
• Operația de SHIFT RIGHT realizează translatarea biților unui număr spre dreapta cu N poziții și este echivalentul împăarțirii numărului la 2N.
• A nu se confunda operatorii folosiți la evaluarea expresiilor („!”, „&&”, „||”) cu operatorii folosiți pentru a realiza calcule la nivel de biți („~”, „&”, „|”).

Cuvinte cheie: baza 2, tipuri de date în C, complementul față de 1, complementul față de 2, operații pe biți, operatori logici