Programare Competitivă

Sisteme de numerație și reguli de conversie

Tot ce scriem zilnic — numere precum 42, 2024, 3.14 — folosește sistemul zecimal (baza 10). Dar există o infinitate de alte baze. Calculatorul lucrează intern în baza 2 (binar), iar adresele de memorie, culorile, permisiunile se scriu adesea în baza 16 (hexadecimal).

A ști să convertim între baze și a înțelege cum se reprezintă un număr într-o bază arbitrară e o deprindere fundamentală în informatică.

Ce înseamnă „baza unui sistem”?

Într-o bază B ≥ 2, un număr se scrie folosind cifre între 0 și B-1. Valoarea numărului depinde de poziția fiecărei cifre — de aceea se numește sistem pozițional.

Formal, dacă avem cifrele c_k c_{k-1} ... c_1 c_0 într-o bază B, valoarea e:

N = c_k · B^k + c_{k-1} · B^{k-1} + … + c_1 · B + c_0

Exemplu

În baza 10, 2025 înseamnă:

2 · 10³ + 0 · 10² + 2 · 10¹ + 5 · 10⁰
= 2000 + 0 + 20 + 5
= 2025

În baza 2, 1011 înseamnă:

1 · 2³ + 0 · 2² + 1 · 2¹ + 1 · 2⁰
= 8 + 0 + 2 + 1
= 11 (în baza 10)

Bazele uzuale

Baza Nume Cifre folosite
2 Binar 0, 1
8 Octal 0, 1, …, 7
10 Zecimal 0, 1, …, 9
16 Hexadecimal 0..9, A(=10), B(=11), …, F(=15)

Pentru baze > 10, folosim litere pentru cifrele ≥ 10: A = 10, B = 11, ..., Z = 35.

De ce baza 2?

Calculatoarele lucrează cu tranzistori care au două stări (pornit/oprit, 1/0). Numerele, literele, imaginile — toate se reduc la șiruri de biți.

De ce baza 16?

Un byte are 8 biți. În baza 16, un byte încape exact în 2 cifre hexa (pentru că 16 = 2⁴, deci o cifră hexa = 4 biți). E mult mai ușor să citești FF decât 11111111.

Conversie din baza B în baza 10

Dacă numărul are cifrele c_k c_{k-1} ... c_0 în baza B, evaluăm polinomul folosind schema lui Horner:

val = 0
pentru fiecare cifră c de la stânga la dreapta:
    val = val * B + c

Exemplu: 1011 din baza 2 în baza 10

val = 0
citesc 1:  val = 0 * 2 + 1 = 1
citesc 0:  val = 1 * 2 + 0 = 2
citesc 1:  val = 2 * 2 + 1 = 5
citesc 1:  val = 5 * 2 + 1 = 11

Rezultat: 11 ✓.

Cod (din baza B în baza 10)

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int cifraValoare(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'A' && c <= 'Z') return c - 'A' + 10;
    if (c >= 'a' && c <= 'z') return c - 'a' + 10;
    return -1;
}

long long bazaBla10(const string &n, int B) {
    long long val = 0;
    for (char c : n) {
        val = val * B + cifraValoare(c);
    }
    return val;
}

int main() {
    string n;
    int B;
    fin >> n >> B;
    fout << bazaBla10(n, B);
    return 0;
}

Complexitate: O(L) unde L e lungimea numărului.

Conversie din baza 10 în baza B

Metoda clasică: împărțiri succesive la B. Restul ne dă cifrele, de la ultima spre prima (trebuie inversate la final).

pas 1: împart N la B, notez restul (cifra de unități)
pas 2: iau câtul și îl împart din nou la B, notez restul (cifra zecilor)
...
mă opresc când câtul devine 0
răspuns: cifrele citite în ordine INVERSĂ

Exemplu: 13 din baza 10 în baza 2

13 / 2 = 6 rest 1
 6 / 2 = 3 rest 0
 3 / 2 = 1 rest 1
 1 / 2 = 0 rest 1

Citim resturile de jos în sus: 1101 ✓ (verificare: 8 + 4 + 0 + 1 = 13).

Exemplu: 255 din baza 10 în baza 16

255 / 16 = 15 rest 15  → F
 15 / 16 =  0 rest 15  → F

Rezultat: FF ✓.

Cod (din baza 10 în baza B)

char valoareCifra(int v) {
    if (v < 10) return '0' + v;
    return 'A' + v - 10;
}

string baza10inB(long long N, int B) {
    if (N == 0) return "0";
    string rez;
    while (N > 0) {
        rez += valoareCifra(N % B);
        N /= B;
    }
    reverse(rez.begin(), rez.end());
    return rez;
}

Complexitate: O(log_B N) — numărul de cifre în baza B.

Conversie între două baze arbitrare (B₁ → B₂)

Metoda standard: trecem prin baza 10 ca intermediar.

număr în B₁  →  (Horner)  →  valoare în baza 10  →  (împărțiri)  →  număr în B₂

Cod

string convert(const string &n, int B1, int B2) {
    long long val = bazaBla10(n, B1);
    return baza10inB(val, B2);
}

Exemplu: 2A din baza 16 în baza 2

  1. 2A din baza 16 în baza 10: 2 · 16 + 10 = 42
  2. 42 din baza 10 în baza 2: 42 = 32 + 8 + 2 = 101010

Rezultat: 101010.

Trucuri speciale: între bază 2 și puteri ale lui 2

Baza 2 ↔︎ Baza 4: grupăm biții în perechi.

10110110   (baza 2)
│ │ │ │
2 3 1 2    (baza 4)

Verificare: 10 = 2, 11 = 3, 01 = 1, 10 = 2.

Baza 2 ↔︎ Baza 8: grupăm biții în grupe de 3.

10110110   (baza 2)
↓
010 110 110    (adăugăm zero în față dacă nu se împarte exact)
 2   6   6

Rezultat: 266 în baza 8.

Baza 2 ↔︎ Baza 16: grupăm biții în grupe de 4.

10110110   (baza 2)
↓
1011 0110
  B    6

Rezultat: B6 în baza 16.

Aceste conversii sunt instantanee (nu trec prin baza 10) pentru că 4 = 2², 8 = 2³, 16 = 2⁴.

Pas cu pas: conversie completă

Problemă: convertește 255 din baza 10 în binar și hexadecimal.

Binar

255 / 2 = 127 rest 1
127 / 2 =  63 rest 1
 63 / 2 =  31 rest 1
 31 / 2 =  15 rest 1
 15 / 2 =   7 rest 1
  7 / 2 =   3 rest 1
  3 / 2 =   1 rest 1
  1 / 2 =   0 rest 1

Citim de jos în sus: 11111111.

Hexadecimal

255 / 16 = 15 rest 15  → F
 15 / 16 =  0 rest 15  → F

Rezultat: FF.

Verificare directă: grupăm 11111111 în perechi de 4: 1111 1111 → FF ✓.

Cod complet: convertor universal

#include <fstream>
#include <algorithm>
#include <string>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int cifraValoare(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'A' && c <= 'Z') return c - 'A' + 10;
    if (c >= 'a' && c <= 'z') return c - 'a' + 10;
    return -1;
}

char valoareCifra(int v) {
    if (v < 10) return '0' + v;
    return 'A' + v - 10;
}

long long bazaBla10(const string &n, int B) {
    long long val = 0;
    for (char c : n) val = val * B + cifraValoare(c);
    return val;
}

string baza10inB(long long N, int B) {
    if (N == 0) return "0";
    string rez;
    while (N > 0) {
        rez += valoareCifra(N % B);
        N /= B;
    }
    reverse(rez.begin(), rez.end());
    return rez;
}

int main() {
    string n;
    int B1, B2;
    fin >> n >> B1 >> B2;
    long long val = bazaBla10(n, B1);
    fout << baza10inB(val, B2);
    return 0;
}

Input: 2A 16 2 → Output: 101010.

Numărul de cifre într-o bază

Numărul de cifre necesare pentru a reprezenta N în baza B e:

⌊log_B N⌋ + 1 (pentru N ≥ 1)

Echivalent:

int nrCifre(long long N, int B) {
    int cnt = 0;
    while (N > 0) { N /= B; cnt++; }
    return cnt == 0 ? 1 : cnt;
}

Exemple

  • 255 în baza 10: 3 cifre (255)
  • 255 în baza 2: 8 cifre (11111111)
  • 255 în baza 16: 2 cifre (FF)
  • 1000000 în baza 2: 20 cifre
  • 1000000 în baza 16: 5 cifre (F4240)

Tabel comparativ (primele 20 de numere)

Zecimal Binar Octal Hexa
0 0 0 0
1 1 1 1
2 10 2 2
3 11 3 3
4 100 4 4
5 101 5 5
6 110 6 6
7 111 7 7
8 1000 10 8
9 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F
16 10000 20 10
17 10001 21 11
18 10010 22 12
19 10011 23 13

Aplicații în informatică

  • Adrese IP: 192.168.1.1 — 4 numere în baza 10 reprezintă 4 bytes consecutivi.
  • Culori CSS: #FF5733 — 3 bytes hexa pentru R, G, B.
  • Permisiuni Linux: chmod 755 — 3 cifre octale (rwxr-xr-x).
  • Adrese memorie: 0x7fff5fbff8c0 — adresele sunt afișate în hexa pentru că sunt scurte și se citesc ușor.
  • Litere ASCII: 'A' = 65 = 0x41 = 0b01000001.
  • Operații pe biți (vezi Bitmask): logic AND/OR/XOR funcționează pe biți, deci binarul e natural.

Greșeli frecvente

1. Cifre invalide pentru baza aleasă

În baza B, cifrele valide sunt 0, 1, ..., B-1. În baza 2 NU poți scrie 12 — cifra 2 nu există în binar. Mereu validează input-ul.

2. Ordinea inversă a cifrelor

Metoda împărțirilor succesive dă cifrele de la ultima spre prima. Nu uita să inversezi string-ul la final.

3. Cazul N = 0

Dacă N == 0, bucla while (N > 0) nu se execută, iar rezultatul e un string gol. Tratează special: returnează "0".

4. Overflow la baze mari sau numere mari

Pentru numere cu multe cifre în baza 2 (ex. 64 de cifre), conversia în long long e la limită. Folosește unsigned long long sau BigInt dacă depășești.

5. Confuzia dintre cifre și caractere

c - '0' e valoarea cifrei (0-9), c e caracterul (‘0’-‘9’). La hexa, 'A' - 'A' + 10 = 10, nu 'A' - '0'.

Ce să reții

  • Un sistem de numerație în baza B folosește cifre 0..B-1.
  • Baza 10 → baza B: împărțiri succesive la B, citești resturile invers.
  • Baza B → baza 10: schema lui Horner — val = val * B + cifra.
  • Baza B₁ → baza B₂: trecem prin baza 10 ca intermediar.
  • Bazele 2, 4, 8, 16 sunt legate: grupezi biți în grupe de 2, 3, 4.
  • Bazele uzuale în informatică: 2 (binar, intern), 8 (octal, permisiuni Linux), 10 (zecimal, uman), 16 (hexa, adrese, culori).
  • Numărul de cifre în baza B e ⌊log_B N⌋ + 1.
  • Mereu tratează cazul N = 0 și validează cifrele.
Cuprins Inapoi Inainte