Przeliczanie BIN ↔ DEC

Wprowadzenie

Konwersja między systemami binarnym (BIN) i dziesiętnym (DEC) to fundamentalna umiejętność w programowaniu. Choć Python oferuje wbudowane funkcje (bin(), int()), zrozumienie algorytmów konwersji jest kluczowe dla:

  • Programowania niskopoziomowego (mikrokontrolery, sterowniki)
  • Optymalizacji algorytmów (operacje bitowe)
  • Zrozumienia reprezentacji danych w pamięci
  • Debugowania problemów z liczbami binarnymi
  • Własnych implementacji (np. w innych językach)

BIN → DEC: Konwersja binarna na dziesiętną

Metoda 1: Wagi pozycji (podstawowa)

Algorytm: 1. Każda cyfra binarna (bit) ma wagę 2^pozycja 2. Pozycje numerowane od prawej (od 0) 3. Suma: bit₀ × 2⁰ + bit₁ × 2¹ + ... + bitₙ × 2ⁿ

Przykład: 1011₂ → DEC

Pozycje:  3  2  1  0
Bity:     1  0  1  1

Obliczenia:
  1 × 2³ = 1 × 8  = 8
  0 × 2² = 0 × 4  = 0
  1 × 2¹ = 1 × 2  = 2
  1 × 2⁰ = 1 × 1  = 1
                   ---
  Suma           = 11₁₀

Implementacja: BIN → DEC (metoda wag)

Wyjście:

=== BIN → DEC (metoda wag) ===

0            →     0 (weryfikacja: 0)
1            →     1 (weryfikacja: 1)
10           →     2 (weryfikacja: 2)
1011         →    11 (weryfikacja: 11)
11111111     →   255 (weryfikacja: 255)
10101010     →   170 (weryfikacja: 170)

Metoda 2: Schemat Hornera (optymalizacja)

Algorytm: Zamiast potęgowania, używamy mnożenia i dodawania:

1011₂ = ((1 × 2 + 0) × 2 + 1) × 2 + 1

Krok po kroku:
  result = 0
  result = 0 × 2 + 1 = 1
  result = 1 × 2 + 0 = 2
  result = 2 × 2 + 1 = 5
  result = 5 × 2 + 1 = 11

Zalety: - Brak potęgowania (szybsze) - Jeden przebieg od lewej do prawej - Lepsze dla bardzo długich liczb

Implementacja: BIN → DEC (schemat Hornera)

Wyjście:

=== BIN → DEC (schemat Hornera) ===

0            →     0 ✓
1            →     1 ✓
10           →     2 ✓
1011         →    11 ✓
11111111     →   255 ✓
10101010     →   170 ✓

BIN → DEC z wizualizacją kroków

Wyjście:

=== BIN → DEC (wizualizacja) ===

Konwersja: 1011₂ → DEC

Początek: decimal = 0

Krok 1: bit='1'
  decimal = 0 × 2 + 1 = 1

Krok 2: bit='0'
  decimal = 1 × 2 + 0 = 2

Krok 3: bit='1'
  decimal = 2 × 2 + 1 = 5

Krok 4: bit='1'
  decimal = 5 × 2 + 1 = 11

Wynik: 1011₂ = 11₁₀

DEC → BIN: Konwersja dziesiętna na binarną

Metoda: Dzielenie przez 2

Algorytm: 1. Dziel liczbę przez 2 2. Zapisz resztę (0 lub 1) - to jest kolejny bit (od prawej) 3. Kontynuuj z wynikiem dzielenia 4. Zatrzymaj się gdy wynik = 0 5. Odczytaj bity od dołu do góry

Przykład: 11₁₀ → BIN

11 ÷ 2 = 5 reszta 1  ← najmłodszy bit (LSB)
 5 ÷ 2 = 2 reszta 1
 2 ÷ 2 = 1 reszta 0
 1 ÷ 2 = 0 reszta 1  ← najstarszy bit (MSB)

Wynik (od dołu): 1011₂

Implementacja: DEC → BIN

Wyjście:

=== DEC → BIN ===

    0 → 0               (weryfikacja: 0              ) ✓
    1 → 1               (weryfikacja: 1              ) ✓
    2 → 10              (weryfikacja: 10             ) ✓
    5 → 101             (weryfikacja: 101            ) ✓
   11 → 1011            (weryfikacja: 1011           ) ✓
   42 → 101010          (weryfikacja: 101010         ) ✓
  100 → 1100100         (weryfikacja: 1100100        ) ✓
  255 → 11111111        (weryfikacja: 11111111       ) ✓
 1024 → 10000000000     (weryfikacja: 10000000000    ) ✓

DEC → BIN z wizualizacją kroków

Wyjście:

=== DEC → BIN (wizualizacja) ===

Konwersja: 42₁₀ → BIN

Krok 1: 42 ÷ 2 = 21 reszta 0
Krok 2: 21 ÷ 2 = 10 reszta 1
Krok 3: 10 ÷ 2 = 5 reszta 0
Krok 4: 5 ÷ 2 = 2 reszta 1
Krok 5: 2 ÷ 2 = 1 reszta 0
Krok 6: 1 ÷ 2 = 0 reszta 1

Odczytaj reszty od dołu do góry: 101010
Wynik: 42₁₀ = 101010₂

Optymalizacje i warianty

1. DEC → BIN z operacjami bitowymi

2. BIN → DEC z walidacją

Wyjście:

=== BIN → DEC (z walidacją) ===

Prawidłowe wejścia:
  0b1010     → 10
  1111       → 15
  0B101      → 5

Nieprawidłowe wejścia:
  102        → BŁĄD: Nieprawidłowa liczba binarna: 102
  abc        → BŁĄD: Nieprawidłowa liczba binarna: abc
  12a        → BŁĄD: Nieprawidłowa liczba binarna: 12a

3. Konwersja z kontrolą długości (padding)

Wyjście:

=== DEC → BIN (8-bitowe) ===

  5 → 00000101 (8-bit)
 42 → 00101010 (8-bit)
100 → 01100100 (8-bit)
255 → 11111111 (8-bit)

Praktyczne zastosowania

1. Kalkulator BIN ↔ DEC

Wyjście:

=== Przykłady użycia konwertera ===

BIN → DEC:
  0b1010          → 10
  0b11111111      → 255
  0b101010        → 42

DEC → BIN:
   10 → 1010            (0b1010)
  255 → 11111111        (0b11111111)
   42 → 101010          (0b101010)

DEC → BIN (8-bit):
   10 → 00001010
  255 → 11111111
   42 → 00101010

2. Analiza bitowa liczby

Wyjście:

=== Analiza liczby 42₁₀ ===

Reprezentacja binarna: 101010₂
Liczba bitów: 6
Liczba bitów = 1: 3
Liczba bitów = 0: 3

Bity ustawione (= 1):
  Pozycja 1: 2^1 = 2
  Pozycja 3: 2^3 = 8
  Pozycja 5: 2^5 = 32

Własności:
  Parzysta? True
  Potęga dwójki? False
  Najmłodszy bit: 0

=== Analiza liczby 64₁₀ ===

Reprezentacja binarna: 1000000₂
Liczba bitów: 7
Liczba bitów = 1: 1
Liczba bitów = 0: 6

Bity ustawione (= 1):
  Pozycja 6: 2^6 = 64

Własności:
  Parzysta? True
  Potęga dwójki? True
  Najmłodszy bit: 0

=== Analiza liczby 255₁₀ ===

Reprezentacja binarna: 11111111₂
Liczba bitów: 8
Liczba bitów = 1: 8
Liczba bitów = 0: 0

Bity ustawione (= 1):
  Pozycja 0: 2^0 = 1
  Pozycja 1: 2^1 = 2
  Pozycja 2: 2^2 = 4
  Pozycja 3: 2^3 = 8
  Pozycja 4: 2^4 = 16
  Pozycja 5: 2^5 = 32
  Pozycja 6: 2^6 = 64
  Pozycja 7: 2^7 = 128

Własności:
  Parzysta? False
  Potęga dwójki? False
  Najmłodszy bit: 1

Złożoność obliczeniowa

Analiza złożoności

Operacja Metoda Złożoność czasowa Złożoność pamięciowa
BIN → DEC Wagi pozycji O(n) O(1)
BIN → DEC Schemat Hornera O(n) O(1)
DEC → BIN Dzielenie przez 2 O(log m) O(log m)
DEC → BIN Operacje bitowe O(log m) O(log m)

gdzie: - n = liczba bitów w reprezentacji binarnej - m = wartość liczby dziesiętnej

Uwaga: n ≈ log₂(m), więc obie złożoności są podobne!

Porównanie metod

BIN → DEC

Podsumowanie

Kluczowe algorytmy

Konwersja Algorytm Złożoność Zalety
BIN → DEC Wagi pozycji O(n) Intuicyjny, łatwy do zrozumienia
BIN → DEC Schemat Hornera O(n) Szybszy (brak potęgowania)
DEC → BIN Dzielenie przez 2 O(log n) Standardowy algorytm
DEC → BIN Operacje bitowe O(log n) Najszybszy

Kiedy używać której metody?

Schemat Hornera (BIN → DEC): ✅ Produkcyjny kod (szybsze) ✅ Długie liczby binarne ✅ Częste konwersje

Metoda wag (BIN → DEC): ✅ Nauka / zrozumienie ✅ Kod edukacyjny ✅ Debugowanie

Operacje bitowe (DEC → BIN): ✅ Kod niskopoziomowy ✅ Maksymalna wydajność ✅ Systemy embedded

Co dalej?

Po opanowaniu BIN ↔ DEC, następne kroki to:

  1. Lekcja 62: Przeliczanie DEC ↔ HEX
  2. System szesnastkowy
  3. Konwersje z prefiksem 0x

  4. Zastosowania w programowaniu

  5. Lekcja 63: Przeliczanie między dowolnymi systemami

  6. Uniwersalne algorytmy
  7. Systemy o podstawach > 36

  8. Konwersje bezpośrednie (bez DEC)

  9. Lekcja 64: Operacje bitowe w algorytmach

  10. AND, OR, XOR, NOT
  11. Przesunięcia bitowe
  12. Maski i flagi

Zadania praktyczne

Zadanie 1: Konwerter dwukierunkowy

Napisz funkcję, która automatycznie rozpoznaje czy wejście to BIN czy DEC i konwertuje w odpowiednią stronę.

Zadanie 2: Reprezentacja liczb ujemnych

Zaimplementuj konwersję dla liczb ujemnych używając: - Znak-moduł (sign-magnitude) - Kod uzupełnień do dwóch (two's complement)

Zadanie 3: Konwersja z ułamkami

Rozszerz algorytmy aby obsługiwały liczby zmiennoprzecinkowe (np. 10.5₁₀ → 1010.1₂).

Zadanie 4: Wizualizacja kroków

Stwórz interaktywny program wizualizujący każdy krok konwersji krok po kroku.

Następna lekcja: Przeliczanie DEC ↔ HEX - system szesnastkowy

Wróć do spisu lekcji