Przeliczanie między dowolnymi systemami

Wprowadzenie

Do tej pory poznaliśmy konwersje między konkretnymi systemami (BIN ↔ DEC, DEC ↔ HEX). Teraz nauczymy się uniwersalnych algorytmów, które działają dla dowolnej podstawy (2-36, a nawet większych).

Umiejętność konwersji między dowolnymi systemami jest przydatna w:

Systemach nietypowych (np. base58 w Bitcoin, base64 w kodowaniu)
Kompresji danych (reprezentacje o wyższych podstawach)
Kryptografii (kodowanie kluczy, hashy)
Optymalizacji (wybór optymalnej podstawy dla danych)
Matematyce komputerowej (arytmetyka w różnych podstawach)

Teoria konwersji między systemami

Trzy podejścia do konwersji

1. Przez system dziesiętny (pośredni)

System A → DEC → System B

Najprostsze
Dwa kroki konwersji
Uniwersalne

2. Bezpośrednie (przez BIN)

System A → BIN → System B

Dla systemów będących potęgami 2 (BIN, OCT, HEX)
Bardzo szybkie
Ograniczone zastosowanie

3. Bezpośrednie (matematyczne)

System A → System B (bezpośrednio)

Złożone matematycznie
Najszybsze
Rzadko używane w praktyce

Uniwersalne algorytmy konwersji

1. Z dowolnej podstawy → DEC

Algorytm: Schemat Hornera (uniwersalny)

Dla liczby w systemie o podstawie 'base':
  result = 0
  dla każdej cyfry (od lewej do prawej):
    result = result * base + wartość_cyfry

Przykład: 231₅ → DEC

base = 5

result = 0
result = 0 * 5 + 2 = 2
result = 2 * 5 + 3 = 13
result = 13 * 5 + 1 = 66

Wynik: 231₅ = 66₁₀

Implementacja: ANY → DEC

Wyjście:

=== Konwersja z różnych systemów → DEC ===

1010   (base  2, binarny        ) →     10 (DEC)
231    (base  5, piątkowy       ) →     66 (DEC)
77     (base  8, ósemkowy       ) →     63 (DEC)
FF     (base 16, szesnastkowy   ) →    255 (DEC)
Z      (base 36, base-36        ) →     35 (DEC)
123    (base  4, czwórkowy      ) →     27 (DEC)

2. DEC → dowolna podstawa

Algorytm: Dzielenie przez podstawę

Dla konwersji na system o podstawie 'base':
  dopóki liczba > 0:
    reszta = liczba % base
    dodaj cyfrę odpowiadającą reszcie
    liczba = liczba // base
  odwróć kolejność cyfr

Przykład: 66₁₀ → base 5

66 ÷ 5 = 13 reszta 1 → '1'
13 ÷ 5 = 2  reszta 3 → '3'
2  ÷ 5 = 0  reszta 2 → '2'

Wynik (od dołu): 231₅

Implementacja: DEC → ANY

Wyjście:

=== Konwersja DEC → różne systemy ===

DEC    | base  2 | base  5 | base  8 | base 12 | base 16 | base 36
-----------------------------------------------------------------
10     |    1010 |      20 |      12 |       A |       A |       A
42     |  101010 |     132 |      52 |      36 |      2A |      16
100    | 1100100 |     400 |     144 |      84 |      64 |      2S
255    |11111111 |    2010 |     377 |     193 |      FF |      73
1000   |11111010|   13000 |    1750 |     6B4 |     3E8 |      RS
       |   00   |         |         |         |         |

Konwersja bezpośrednia ANY → ANY

Metoda 1: Przez DEC (dwuetapowa)

Najprostsza i najczęściej używana metoda:

Wyjście:

=== Konwersja bezpośrednia ANY → ANY ===

BIN → HEX            | 1010       (base  2) → A          (base 16)
HEX → BIN            | FF         (base 16) → 11111111   (base  2)
OCT → DEC            | 77         (base  8) → 63         (base 10)
DEC → base-5         | 100        (base 10) → 400        (base  5)
base-36 → DEC        | Z          (base 36) → 35         (base 10)
BIN → OCT            | 1111       (base  2) → 17         (base  8)

Konwersja dla potęg dwójki (optymalizacja)

BIN ↔ OCT ↔ HEX (bezpośrednia)

Dla systemów będących potęgami 2 (2, 4, 8, 16, 32...) możliwa jest konwersja bez obliczeń:

BIN (2¹) ↔ OCT (2³) ↔ HEX (2⁴)

1 cyfra OCT = 3 bity BIN
1 cyfra HEX = 4 bity BIN

Implementacja: Konwersja między potęgami 2

Wyjście:

=== Konwersja między potęgami 2 (optymalizacja) ===

1111   (base  2) → 33              (base  4)
1111   (base  2) → 17              (base  8)
FF     (base 16) → 11111111        (base  2)
FF     (base 16) → 377             (base  8)
77     (base  8) → 3F              (base 16)

Systemy o większych podstawach

Base-64 (kodowanie danych)

Wyjście:

=== Base-64 (kodowanie) ===

DEC        Base-64         Weryfikacja
----------------------------------------
0          A               0            ✓
10         K               10           ✓
63         /               63           ✓
64         BA              64           ✓
100        Bk              100          ✓
1000       Po              1000         ✓
4095       //              4095         ✓

Kompletny uniwersalny konwerter

Wyjście:

=== Uniwersalny konwerter (base 2-62) ===

1010       (base  2) → 10                   (base 10)
FF         (base 16) → 11111111             (base  2)
100        (base 10) → 202                  (base  7)
Z          (base 36) → 35                   (base 10)
hello      (base 36) → 29234652             (base 10)

Konwersja: CAFE (base 16) → base 8
--------------------------------------------------
Krok 1: CAFE (base 16) → 51966 (DEC)
Krok 2: 51966 (DEC) → 145376 (base 8)

Wynik: CAFE (base 16) = 145376 (base 8)

Praktyczne zastosowania

1. Kodowanie Base58 (Bitcoin)

Wyjście:

=== Base58 (Bitcoin) ===

0            → 1          →            0 ✓
57           → z          →           57 ✓
58           → 21         →           58 ✓
100          → 2W         →          100 ✓
1000         → He         →         1000 ✓
123456789    → BukQL      →    123456789 ✓

2. Walidator liczb w różnych systemach

Wyjście:

=== Walidacja liczb ===

1010   (base  2): ✓ OK
1012   (base  2): ✗ Nieprawidłowa cyfra '2' na pozycji 3 dla podstawy 2
FF     (base 16): ✓ OK
FG     (base 16): ✗ Nieprawidłowa cyfra 'G' na pozycji 1 dla podstawy 16
789    (base  8): ✗ Nieprawidłowa cyfra '8' na pozycji 1 dla podstawy 8
123    (base 10): ✓ OK

Złożoność obliczeniowa

Analiza złożoności

Operacja	Złożoność czasowa	Złożoność pamięciowa
ANY → DEC	O(n)	O(1)
DEC → ANY	O(logₐ m)	O(logₐ m)
ANY → ANY (przez DEC)	O(n + logₐ m)	O(logₐ m)
Potęgi 2 → Potęgi 2	O(n)	O(n)

gdzie: - n = liczba cyfr w systemie źródłowym - m = wartość liczby - a = podstawa systemu docelowego

Podsumowanie

Kluczowe algorytmy

Konwersja	Metoda	Zalety
ANY → DEC	Schemat Hornera	Uniwersalny, prosty
DEC → ANY	Dzielenie przez podstawę	Standardowy algorytm
ANY → ANY	Przez DEC (2 kroki)	Najprostszy w implementacji
Potęgi 2	Przez BIN (mapowanie)	Bardzo szybki

Praktyczne zastosowania

✅ Kodowanie danych: Base64, Base58, Base32 ✅ Kryptografia: Reprezentacja kluczy i hashy ✅ Kompresja: Wyższe podstawy = krótsza reprezentacja ✅ Matematyka: Arytmetyka w różnych podstawach ✅ Bitcoin/krypto: Base58 dla adresów

Kluczowe fakty

Każda podstawa ≥ 2 może reprezentować dowolną liczbę
Wyższa podstawa = krótsza reprezentacja
Potęgi 2 pozwalają na konwersję bez obliczeń
Base-64 szeroko używany do kodowania danych

Co dalej?

Po opanowaniu konwersji między systemami, następne kroki to:

Lekcja 64: Operacje bitowe w algorytmach
AND, OR, XOR, NOT
Przesunięcia bitowe
Maski i flagi
Lekcja 65: Liczby pierwsze - test pierwszości
Algorytmy sprawdzania pierwszości
Optymalizacje
Lekcja 66: Sito Eratostenesa
Generowanie liczb pierwszych
Optymalizacje pamięciowe

Zadania praktyczne

Zadanie 1: Kalkulator systemów

Napisz interaktywny kalkulator konwertujący między dowolnymi systemami (2-62) z interfejsem CLI.

Zadanie 2: Base64 encoder

Zaimplementuj własny encoder/decoder Base64 zgodny ze standardem RFC 4648.

Zadanie 3: Arytmetyka w różnych podstawach

Napisz funkcje dodawania i mnożenia liczb bezpośrednio w wybranej podstawie (bez konwersji na DEC).

Zadanie 4: Optymalizacja reprezentacji

Znajdź optymalną podstawę dla danego zestawu liczb, minimalizującą łączną długość reprezentacji.

Następna lekcja: Operacje bitowe w algorytmach - AND, OR, XOR, przesunięcia