Conversii între baze

De ce contează?

Același preț poate fi scris în lei sau în euro — e aceeași valoare, doar „limba" diferă. Conversia între baze e exact asta: păstrezi valoarea, schimbi modul de scriere. 11 în zecimal devine 1011 în binar, dar e tot aceeași cantitate.

Două direcții, două metode

Zecimal → baza b: împărțiri repetate la b, citești resturile.
Baza b → zecimal: aduni cifră · putere, sau folosești schema lui Horner.

Zecimal → binar: împărțiri repetate

Convertim 11 în baza 2 împărțind repetat la 2 și reținând resturile:

Pas	număr	: 2	rest
1	11	5	1
2	5	2	1
3	2	1	0
4	1	0	1

Resturile, citite de jos în sus: 1011. Deci 11₁₀ = 1011₂.

Observația-cheie

Primul rest (1) e cifra unităților — cea mai din dreapta. De aceea resturile se citesc invers față de ordinea în care apar. E greșeala clasică la conversii.

Implementare: zecimal → baza b

#include <iostream>
using namespace std;

int main() {
    int n, b;
    cin >> n >> b;              // numar zecimal, baza tinta
    int cifre[64], k = 0;
    if (n == 0) cifre[k++] = 0;
    while (n > 0) {
        cifre[k++] = n % b;     // restul = cifra curenta
        n /= b;
    }
    // cifrele sunt in ordine inversa -> afisam de la coada la cap
    for (int i = k - 1; i >= 0; i--) {
        cout << cifre[i];
    }
    cout << "\n";
    return 0;
}

Pentru n = 11, b = 2 → 1011.

Baza b → zecimal: schema lui Horner

Parcurgem cifrele de la stânga la dreapta. La fiecare pas: înmulțim rezultatul cu baza și adăugăm cifra curentă.

biți

Horner pe 1011₂: pornești cu 0, apoi 0·2+1=1, 1·2+0=2, 2·2+1=5, 5·2+1=11. Rezultatul crește cifră cu cifră.

cifră	rezultat = rezultat·2 + cifră
1	0·2 + 1 = 1
0	1·2 + 0 = 2
1	2·2 + 1 = 5
1	5·2 + 1 = 11

#include <iostream>
using namespace std;

int main() {
    int b;
    cin >> b;
    string cifre;
    cin >> cifre;               // numarul in baza b, ca sir
    long long rezultat = 0;
    for (char c : cifre) {
        int cifra = c - '0';    // valoarea cifrei
        rezultat = rezultat * b + cifra;   // Horner
    }
    cout << rezultat << "\n";   // 1011 in baza 2 -> 11
    return 0;
}

Observația-cheie

Horner evită calcularea separată a puterilor bazei (b⁰, b¹, ...). Un singur *b + cifră pe pas — mai scurt și fără overflow la puteri intermediare.

Complexitate

Conversie	Timp	Spațiu
zecimal → baza b	O(log_b n)	O(log_b n)
baza b → zecimal	O(nr. cifre)	O(1)

Numărul de pași e proporțional cu numărul de cifre — foarte rapid.

Greșeli frecvente

Capcane reale la conversii:

Ordinea resturilor: afișezi resturile în ordinea găsită, nu invers → numărul iese „pe dos". Citește-le de jos în sus.
Cazul n = 0: bucla while (n > 0) nu rulează → nu afișezi nimic. Tratează 0 separat.
Overflow la baza b → zecimal: un număr lung în baza mică poate depăși int în zecimal. Folosește long long.
Cifre peste 9: la baza 16, cifrele A...F nu sunt c - '0'. Tratează literele separat.

De reținut

Zecimal → baza b: împărțiri repetate la b, resturile citite invers.
Baza b → zecimal: schema lui Horner, rezultat = rezultat·b + cifră, de la stânga.
Numărul de pași = numărul de cifre; folosește long long la valori mari.