Conversia între baze de numerație: din baza 10 în baza 2 și invers

Un număr scris în baza b folosește cifrele de la 0 la b−1, iar fiecare poziție valorează o putere a lui b. În baza 10, 4728 înseamnă 4·10³ + 7·10² + 2·10 + 8. În baza 2, 1101 înseamnă 1·2³ + 1·2² + 0·2 + 1 = 13. La BAC informatică întâlnești conversiile în două forme: direct („scrieți reprezentarea în baza 2 a lui 25”) și, mai des, ascunse într-un algoritm în pseudocod pe care trebuie să-l urmărești și să-l înțelegi.

Din baza 10 în baza 2: împărțiri repetate

Regula: împarți numărul la 2, reții restul, apoi continui cu câtul, până când câtul devine 0. Resturile citite de jos în sus formează numărul în baza 2.

Exemplu pentru 13:

Citind resturile de jos în sus: 13₍₁₀₎ = 1101₍₂₎. Încă un exemplu: 25 → resturi 1, 0, 0, 1, 1, deci 11001₍₂₎. Verificare: 16 + 8 + 1 = 25.

Este exact algoritmul de extragere a cifrelor unui număr, doar că împarți la 2 în loc de 10. De aceea și aici resturile ies în ordine inversă.

Din baza 10 în baza 2 în C++

Ca să obținem rezultatul ca număr (cu cifrele 0 și 1 „scrise” în baza 10), folosim tehnica de construire cu puteri ale lui 10: fiecare rest nou se pune în fața celor de până acum.

long long inBaza2(int n)
{
    long long r = 0, p = 1;
    while (n > 0)
    {
        r = r + (n % 2) * p;
        p = p * 10;
        n = n / 2;
    }
    return r;
}

Pentru n = 13: r devine 1, apoi 1 (rest 0, p = 10), apoi 101 (rest 1, p = 100), apoi 1101 (rest 1, p = 1000). Am folosit long long pentru că reprezentarea în baza 2 are mult mai multe cifre decât numărul inițial: 1023 devine 1111111111, cu 10 cifre. Chiar și cu long long, metoda este sigură doar pentru reprezentări de cel mult 18 cifre, adică pentru numere mai mici de 2¹⁸ = 262 144. Pentru numere mai mari, reții cifrele binare într-un vector și le afișezi de la ultima la prima.

Din baza 2 în baza 10

Aici sunt două metode, ambele utile.

Metoda puterilor (de la dreapta la stânga)

Înmulțești fiecare cifră cu puterea lui 2 corespunzătoare poziției și aduni: 1101₍₂₎ = 1·1 + 0·2 + 1·4 + 1·8 = 13. În C++, dacă numărul binar este dat ca întreg cu cifre 0 și 1, extragi cifrele cu % 10 și le înmulțești cu puteri ale lui 2:

int dinBaza2(long long x)
{
    int r = 0, p = 1;
    while (x > 0)
    {
        r = r + (x % 10) * p;
        p = p * 2;
        x = x / 10;
    }
    return r;
}

Schema lui Horner (de la stânga la dreapta)

Pornești de la 0 și, pentru fiecare cifră de la stânga la dreapta, înmulțești rezultatul cu baza și aduni cifra. Pentru 1101: 0·2 + 1 = 1, apoi 1·2 + 1 = 3, apoi 3·2 + 0 = 6, apoi 6·2 + 1 = 13. Metoda este ideală când cifrele vin pe rând, de la stânga la dreapta — de exemplu dintr-un șir de caractere:

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char s[65];
    cin >> s;                         // de exemplu 1101
    long long r = 0;
    for (int i = 0; i < (int)strlen(s); i++)
        r = r * 2 + (s[i] - '0');
    cout << r;                        // 13
    return 0;
}

Orice bază b ≤ 10

Ambii algoritmi se generalizează înlocuind 2 cu b. Pentru 100 în baza 3: 100 = 33·3 + 1, 33 = 11·3 + 0, 11 = 3·3 + 2, 3 = 1·3 + 0, 1 = 0·3 + 1. Resturile de jos în sus: 10201₍₃₎. Verificare: 1·81 + 0·27 + 2·9 + 0·3 + 1 = 100.

long long inBazaB(int n, int b)
{
    long long r = 0, p = 1;
    while (n > 0)
    {
        r = r + (n % b) * p;
        p = p * 10;
        n = n / b;
    }
    return r;
}

Pentru baze mai mari de 10 (de exemplu 16) ai nevoie de „cifre” suplimentare: A = 10, B = 11, …, F = 15. Atunci rezultatul nu mai poate fi un număr zecimal, ci un șir de caractere: 255₍₁₀₎ = FF₍₁₆₎, pentru că 15·16 + 15 = 255.

Scurtături utile la grile

• Puterile lui 2 de reținut: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024.
• Un număr în baza 2 este par dacă și numai dacă ultima lui cifră este 0.
• 2^k − 1 se scrie în baza 2 cu k cifre de 1: 31 = 11111₍₂₎.
• Din baza 2 în baza 8: grupezi cifrele câte 3 de la dreapta. 11001 → 011 001 → 31₍₈₎, adică 3·8 + 1 = 25. Din baza 2 în baza 16 grupezi câte 4.
• Numărul de cifre de 1 din reprezentarea binară se obține numărând resturile egale cu 1 în algoritmul de împărțiri repetate.