wstecz

20.03.2014 by noniwoo

Czytałeś wcześniejszy artykuł nt. liczb binarnych?

Liczby binarne 2: dziesiętny na dwójkowy

Umiesz już zamieniać liczby binarne na dziesiętne, warto więc byś nauczył się zamiany w drugą stronę. Zanim jednak to nastąpi, rzućmy okiem jak rozebrać liczbę dziesiętną na części.

Dziesiętne na drobne

Załóżmy, że mamy liczbę 254 w systemie dziesiętnym. Co się stanie jeśli podzielimy ją przez 10?

254 / 10  = 25,4

Jak widać, ostatnia cyfra przesunęła się za przecinek. Utnijmy tę ostatnią cyfrę od liczby i zobaczmy co się dzieje dalej z pozostałą częścią.

25 / 10 = 2,5
2 / 10 = 0,2

Jak widać zawsze jak dzielimy liczbę naturalną przez 10, to ostatnia cyfra ląduje za przecinkiem. Czemu tak jest i czy tak jest zawsze? Spójrzmy na to z innej strony - rozpiszmy liczbę na sumę potęg, tak jak ostatnio.

254 = 2 * 102 + 5 * 101 + 4 * 100

Dzielenie tej liczby przez 10, to tak na prawdę odejmowanie 1 od każdej potęgi przy 10, czyli

254 / 10 =
(2 * 102 + 5 * 101 + 4 * 100) / 10 = 
 2 * 102-1 + 5 * 101-1 + 4 * 100-1 = 
 2 * 101 + 5 * 100 + 4 * 10-1 = 
 2 * 10 + 5 * 1 + 4 * 0,1 = 20 + 5 + 0,4 = 25,4

Jak widać zawsze będzie się tak działo, że jeśli liczba jest naturalna i podzielimy ją przez 10, to ostatnia cyfra pójdzie za przecinek. Jeśli więc mielibyśmy narzędzie, które potrafiłoby odcinać cyfrę która znajdzie się za przecinkiem, potrafilibyśmy uzyskiwać kolejne cyfry danej liczby. Jak się okazuje znamy takie narzędzie i nazywa się reszta z dzielenia.

Reszta z dzielenia

Pamiętasz może ze szkoły podstawowej, gdy dzieląc liczbę przez inną zapisywałeś wynik dzielenia i resztę z niego? Odbywało się to mniej więcej tak:

254 / 10 = 25 reszta 4
25 / 10 = 2 reszta 5
2 / 10 = 0 reszta 2

Szkoda tylko że nikt wtedy nie zastanawiał się nad systemami liczbowymi. Czemu? Zobacz na reszty z tego dzielenia. Układają się dokładnie w liczbę od której zaczęliśmy.

Należy jednak zwrócić uwagę, że na górze (po pierwszym dzieleniu) mamy cyfrą najmniej znaczącą, czyli tutaj jest to 4. Dopiero dalej 5, oraz 2. Gdybyśmy to przeczytali od góry do dołu, wyszłoby 452, czyli nasza liczba tylko czytana od prawej strony. Należy więc pamiętać, żeby reszty czytać od dołu do góry.

Teraz warto się zastanowić nad pozornymi zbiegami okoliczności i ich konsekwencjami.

254 to liczba zapisana w systemie dziesiętnym. Widzieliśmy to wyraźnie gdy rozpisaliśmy ją na sumę potęg - 10x określało jak ważna jest dana cyfra, czyli na której pozycji stoi.

Dzieląc 254 przez 10 i zapisując kolejne reszty z dzielenia dostawaliśmy kolejne cyfry. Jak widzieliśmy po rozpisaniu liczby na sumę potęg, nie był to przypadek. Zawsze dokładnie jedna cyfra ucieka za przecinek jeśli podzielimy liczbę przez 10. Cyfra ta jest resztą przy dzieleniu z resztą.

Mamy więc liczbę dziesiętną i dzielimy ją przez 10 (podstawa systemu). Zapisując reszty z tego dzielenia dostajemy kolejne cyfry tej liczby. Cyfry dziesiętne.

A gdyby tak spróbować tego samego, ale nie dzielić przez 10, tylko przez 2? Skoro dzielenie przez 10 daje cyfry w systemie dziesiętnym, to może dzielenie przez 2 da cyfry w sytemie binarnym?

Dziesiętny na binarny

Podzielmy przykładową liczbę 13 przez 2 zapisując kolejne reszty z dzielenia.

13 / 2 = 6 reszta 1
6 / 2 = 3 reszta 0
3 / 2 = 1 reszta 1
1 / 2 = 0 reszta 1

Wyszła nam liczba 1101 (pamiętaj - reszty czytaj od dołu) i zdaje się że jest binarna. Nie widać niczego poza zerami i jedynkami.

Sprawdźmy czy się zgadza, jeśli zamienimy ją na dziesiętną znanym nam sposobem.

1101 =10

1 * 23 + 1 * 22 + 0 * 21 + 1 * 20 =

1 * 8  + 1 * 4  + 0 * 2  + 1 * 1 =

  8    +   4    +   0    +   1   = 13

No i proszę - zgadza się. Czyli zapisując reszty z dzielenia przez 2 i czytając je od dołu mamy binarną reprezentację danej liczby. Ale pozostaje ciągle pytanie:

Czemu to działa?

Każda liczba naturalna zapisana dziesiętnie może być też zapisana binarnie - cudów nie ma. Jeśli mamy więc liczbę 3475, wiemy że jest ona zapisana też jakoś w postaci binarnej, czyli:

3475 =
a0 * 20 + a1 * 21 + a2 + 22 + ...

To czego nie znamy to kolejne cyfry reprezentacji binarnej, czyli tutaj a0, a1, a2 itd. Możemy natomiast w naszym znanym systemie dziesiętnym dzielić tą liczbę przez 2. I mimo że nie znamy cyfr, to wiemy że wszystkie potęgi przy podstawie systemu binarnego (czyli przy liczbie 2) zostaną pomniejszone o 1.

(a0 * 20 + a1 * 21 + a2 * 22 + ...) / 2 =
a0 * 20-1 + a1 * 21-1 + a2 * 22-1 + ... =
a0 * 2-1 + a1 * 20 + a2 * 21 + ...

Stąd tak samo jak w systemie dziesiętnym najmniej znacząca cyfra zostanie przeseunięta poza przecinek. A skoro tak to jest ona resztą z dzielenia.

Jeśli więc będziemy dzielić przez 2 i zapisywać resztą z dzielenia, będziemy mieli kolejne cyfry binarnej reprezentacji danej liczby. Z tym że od najmniej znaczącej. Czytamy więc reszty od dołu do góry - tak samo jak było w systemie dziesiętnym z resztami - i voila! Mamy liczbę w systemie binarnym.