Zamiana liczb między systemami: dziesiętny ↔ dowolna podstawa

System pozycyjny to umowa o tym, ile znaczy cyfra w zależności od miejsca, na którym stoi. W systemie o podstawie p dostępnych jest dokładnie p cyfr – od 0 do p minus 1 – a kolejne pozycje od prawej mają wagi 1, p, p do kwadratu, p do sześcianu i tak dalej. Dziesiętny, dwójkowy, trójkowy, ósemkowy i szesnastkowy to nie pięć osobnych tematów, tylko pięć wartości p w jednej definicji.

Stąd jedyna dobra wiadomość tego działu: procedura jest jedna dla wszystkich podstaw. Kto umie zamienić 13 na dwójkowy, umie też zamienić 400 na trójkowy i 1861 na dziewiątkowy – zmienia się wyłącznie dzielnik. Podstawa bywa w zadaniach nietypowa (3, 4, 7, 9) właśnie po to, żeby wyszło, kto zna zasadę, a kto wykuł tabelkę potęg dwójki.

Cztery reguły wystarczą do każdego zadania z tego tematu:

• Z dziesiętnego na dowolny: dziel przez podstawę, zbieraj reszty, czytaj je od końca. Reszta z każdego dzielenia to jedna cyfra wyniku. Dzielisz, aż iloraz osiągnie 0 – nie do momentu, w którym „już się nie da".
• Z dowolnego na dziesiętny: pomnóż cyfry przez wagi pozycji i zsumuj. Wagi to kolejne potęgi podstawy, licząc od prawej. Ten sam rachunek robi się szybciej schematem Hornera, bez liczenia potęg.
• W systemie o podstawie p nie ma cyfry p ani większej. W trójkowym największą cyfrą jest 2, w ósemkowym 7, w szesnastkowym F. 1213 nie jest liczbą trójkową – to nie „inna wartość", to zapis nieistniejący.
• Sam ciąg cyfr nie mówi nic bez podstawy. 101 to pięć dwójkowo, dziesięć trójkowo, sto jeden dziesiętnie i dwieście pięćdziesiąt siedem szesnastkowo – dlatego podstawę zapisuje się indeksem dolnym: 101₂, 101₃, 101₁₆.

Szesnastkowy ma szesnaście cyfr: 0–9, a potem litery A, B, C, D, E, F dla wartości od 10 do 15 – litera jest tu zwykłą cyfrą, nie skrótem, więc C8 to 12 razy 16 plus 8. Sąsiednie tematy mają własne strony: skrót bez dzielenia między podstawami 2, 8 i 16, czyli grupowanie bitów, działania pisemne w arytmetyce pozycyjnej i zapis liczb ujemnych w kodzie uzupełnień do dwóch.

Dzielenie z resztą – dziesiętny na dwójkowy. Zamieniamy 13, dzieląc przez 2:

• 13 dzielone przez 2 daje 6, reszta 1
• 6 dzielone przez 2 daje 3, reszta 0
• 3 dzielone przez 2 daje 1, reszta 1
• 1 dzielone przez 2 daje 0, reszta 1

Reszty czytane od ostatniej do pierwszej dają 1101. To ten szczegół, na którym wykłada się najwięcej osób: w kolejności powstawania wyszłoby 1011, czyli 11 zamiast 13. Kontrola: 8 + 4 + 0 + 1 = 13.

Druga metoda na dwójkowy – odejmowanie potęg. Wypisz potęgi dwójki (1, 2, 4, 8, 16, 32, 64, 128) i bierz największą, która mieści się w reszcie: na jej pozycji stawiasz jedynkę i odejmujesz. Dla 13 mieści się 8 (zostaje 5), potem 4 (zostaje 1), dwójka nie – jej pozycja dostaje 0 – a na końcu 1. Znów 1101, i od razu widać, ilu bitów potrzeba.

Ta sama metoda, inna podstawa – 200 na szesnastkowy. Dzielimy przez 16, a reszty od 10 do 15 zapisujemy literami: 200 przez 16 daje 12 reszty 8, a 12 przez 16 daje 0 reszty 12, czyli C. Od końca: C8 (kontrola: 192 + 8).

Podstawa 7 – 100 na siódemkowy. Reszty wychodzą kolejno 2, 0, 2 (ilorazy 14, 2, 0), więc wynik to 202; kontrola: 2 razy 49, plus 2, czyli 100.

Podstawy 3 i 9 – przykład wprost z CKE. Zamiana 400 na trójkowy daje reszty 1, 1, 2, 2, 1, 1, więc wynik czytany od końca to 112211. Ta sama liczba w podstawie 9: 400 przez 9 daje 44 reszty 4, 44 daje 4 reszty 8, 4 daje 0 reszty 4 – czyli 484 (kontrola: 324 + 72 + 4).

Dlaczego trójka i dziewiątka są ze sobą związane. Ponieważ 9 = 3², dwie cyfry trójkowe składają się na dokładnie jedną cyfrę dziewiątkową – tak jak cztery bity na jedną szesnastkową. Weź 2112221₃ (to 1861), dopisz z lewej zero do parzystej długości i pogrupuj po dwie od prawej: 02, 11, 22, 21. Pary dają 2, 4, 8 i 7, czyli 2487₉ – bez ani jednego dzielenia.

Z powrotem na dziesiętny – schemat Hornera. Zamiast liczyć potęgi, idziemy cyframi od lewej i po każdej mnożymy dotychczasowy wynik przez podstawę, a potem dodajemy cyfrę. Dla 1102₃: 0 razy 3 plus 1 daje 1; 1 razy 3 plus 1 daje 4; 4 razy 3 daje 12; 12 razy 3 plus 2 daje 38. Rachunek przez wagi daje to samo (27 + 9 + 2), ale wymaga pamiętania potęg trójki – dlatego w kluczu CKE stoi Horner.

Sprawdzenie w dwie sekundy. Ostatnia cyfra zapisu jest równa reszcie z dzielenia liczby przez podstawę: zapis dwójkowy liczby parzystej kończy się na 0, a 202₇ musi opisywać liczbę dającą resztę 2 z dzielenia przez 7 – i 100 ją daje.

Wyznaczanie podstawy z równania. Dany jest zapis i jego wartość, szukamy podstawy: rozpisz zapis przez wagi i potraktuj podstawę jak niewiadomą. Dla 21 równego 13 mamy 2p + 1 = 13, czyli p = 6. Trudniejszy wariant daje równanie kwadratowe: 121 równe 100 to (p + 1)² = 100, a stąd p = 9 – i rzeczywiście 121₉ to 81 + 18 + 1. Na koniec warunek dopuszczalności: podstawa musi być większa od każdej cyfry zapisu.

Ile cyfr ma zapis. Tyle, ile razy da się liczbę podzielić przez podstawę, zanim iloraz spadnie do zera; im większa podstawa, tym krócej (1000 to 1111101000 dwójkowo, 1750 ósemkowo, 3E8 szesnastkowo). Zadanie potrafi pytać o samą długość, bez podawania liczby – wtedy liczy się związek podstaw: skoro dwie cyfry trójkowe to jedna dziewiątkowa, zapis o 20 cyfrach w podstawie 3 ma ich 10 w podstawie 9.

funkcja na_podstawe(n, p):
  jeżeli n = 0:
    zwróć "0"
  cyfry ← []
  dopóki n > 0:
    cyfry ← [n mod p] + cyfry
    n ← n div p
  zwróć cyfry

funkcja na_dziesietny(cyfry, p):
  wynik ← 0
  dla każdej cyfry c w cyfry od lewej:
    wynik ← wynik * p + c
  zwróć wynik

funkcja liczba_cyfr(n, p):
  jeżeli n = 0:
    zwróć 1
  ile ← 0
  dopóki n > 0:
    ile ← ile + 1
    n ← n div p
  zwróć ile

Reszty zapisane w kolejności powstawania. Najczęstsza pomyłka w całym dziale i jedyny powód, dla którego z 13 wychodzi 11. Reszty rodzą się od najmłodszej cyfry, więc wynik czyta się od dołu do góry – kto notuje je w kolumnie, niech od razu rysuje strzałkę w górę.

Cyfra spoza zakresu podstawy. W podstawie 3 są cyfry 0, 1 i 2 – kropka. 1213 nie jest liczbą trójkową o jakiejś tam wartości, tylko zapisem nieistniejącym, i tak trzeba go nazwać w odpowiedzi. Ten sam błąd w drugą stronę: przy dzieleniu przez 8 uczeń dopisuje resztę „8", chociaż taka reszta nigdy nie przekroczy 7.

Litery szesnastkowe czytane jak liczba dziesiętna. C8 to 200, a nie „C razy 8". Odwrotna wersja jest równie kosztowna: przy zamianie na szesnastkowy uczeń zapisuje resztę 12 jako dwie cyfry 12 zamiast jako C, przez co liczba rośnie o rząd wielkości.

Zapis bez podanej podstawy. 101 bez indeksu nie znaczy nic konkretnego – to 5, 10, 65, 101 albo 257. Gdy zadanie prosi o zapis w podstawie 9, samo 484 bywa uznane za niepełne; odwrotnie, jeśli treść podaje 101201₃, indeks jest daną, a nie ozdobą.

Dzielenie przerwane o krok za wcześnie. Procedura kończy się, gdy iloraz wynosi 0, a nie wtedy, gdy zrobił się mniejszy od podstawy. Kto przerwie na ilorazie 1 i go nie zapisze, zgubi najstarszą cyfrę: z 13 zostanie 101, czyli 5.

Liczba cyfr szacowana na oko. Pytanie „ile cyfr ma ta liczba w innym systemie" nie wymaga zamiany, tylko związku podstaw. Rachunek na długościach działa dla par 3 i 9, 2 i 4, 2 i 8, 2 i 16, ale nie dla 3 i 10 – dziesiątka nie jest potęgą trójki.

• System o podstawie p ma cyfry od 0 do p minus 1; cyfra równa podstawie oznacza błąd, nie inną wartość.
• Z dziesiętnego: dziel przez p i zapisuj reszty, aż iloraz spadnie do zera; czytaj je od ostatniej do pierwszej.
• Na dziesiętny: schemat Hornera – idź cyframi od lewej i po każdej licz wynik razy p plus cyfra; cyfry szesnastkowe to 0–9 oraz A = 10 do F = 15.
• Podstawę z równania wyznacza się, traktując ją jak niewiadomą: 21ₚ = 13 daje p = 6, a 121ₚ = 100 daje p = 9; podstawa musi przewyższać każdą cyfrę zapisu.
• Dwie cyfry trójkowe to jedna dziewiątkowa, więc 20 cyfr w podstawie 3 to 10 cyfr w podstawie 9.
• Między podstawami niepowiązanymi potęgą idzie się przez dziesiętny; między 2, 8 i 16 szybsze jest grupowanie bitów.

Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: