Liczby naturalne

grafika

Gottfried Wilhelm von Leibniz (1646–1716)

System dwójkowy, zbadany i spopularyzowany przez Wilhelma Gotfrieda Leibniza w wieku XVII, ma wiele zalet. Podobnie jak w dziesiętnym systemie pozycyjnym, liczby naturalne przedstawiamy jako sumę potęg bazy (2) z odpowiednimi wagami reprezentowanymi przez cyfry – w tym przypadku tylko dwie: 0 i 1. Każda liczba naturalna dodatnia ma zatem reprezentację postaci
\( \sum_{k=0}^{m} a_k2^k \), gdzie \( a_k\in\{0,1\} \).
Reprezentacja ta jest jednoznaczna, jeśli przyjmiemy, że nie stosujemy wiodących zer. Warto zapamiętać pierwszych 16 wartości:

Jeśli ustalimy z góry pewną liczbę \( n \) cyfr, za pomocą których będziemy reprezentowali liczby naturalne, to w automatyczny sposób uzyskamy \( n \)-cyfrowe reprezentacje, uzupełniając je do pełnych \( n \) cyfr zerami z lewej strony. Kolejno mielibyśmy np. dla \( n=8:00000000,00000001,00000010,\ldots,11111111 \). Widać, że różnych wartości \( n \)-cyfrowych jest \( 2^n \): od \( 0 \) do \( 2^n-1 \).
Jak w prosty sposób znajdować reprezentacje dwójkowe liczb naturalnych? Są dwie proste metody. Załóżmy, że chodzi nam o przedstawienie dwójkowe liczby \( m>0 \).

• Znajdujemy największą liczbę \( d=2^k \) nieprzekraczającą \( m \). Piszemy jedynkę, odejmujemy od \( m \) wartość \( d \), a następnie kolejno dla wszystkich mniejszych potęg dwójki sprawdzamy, czy mieszczą się one w tym, co zostało z \( m \). Jeśli dana potęga dwójki nie mieści się, to dopisujemy zero, a jeśli mieści się, to dopisujemy jedynkę i odejmujemy tę wartość od tego, co zostało z \( m \). Przykładowo dla \( m=13: \)

• Zaczynamy od liczby \( m \), a następnie dopóki m jest większe od zera dzielimy \( m \) przez 2, zapisując kolejno otrzymywane reszty. Ciąg reszt odczytany od końca da nam poszukiwaną reprezentację. Przykładowo dla tego samego \( m=13: \)

Ciąg reszt z ostatniej kolumny czytany od dołu do góry daje właśnie \( 1101 \), czyli reprezentację dwójkową \( 13 \).
W odwrotną stronę trudno podać lepszą metodę niż proste dodanie kolejnych potęg dwójki, zatem np. 10101, to
\( 1\cdot 16+0\cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1\cdot 1=21 \).
Teoretycznie jesteśmy więc w stanie reprezentować każdą liczbę naturalną. Musimy jednak zdać sobie sprawę z tego, że to jest tylko ułuda. W rzeczywistości trzeba by mieć nieograniczoną pamięć, aby reprezentować bardzo duże liczby, a w każdym komputerze, ba, we wszystkich komputerach świata łączna pamięć jest i będzie ograniczona i skończona. Musimy zatem pogodzić się z tym, że będziemy w stanie reprezentować jedynie skończony podzbiór liczb naturalnych. Zazwyczaj robi się to tak, że do reprezentacji liczb całkowitych używa się standardowo określonej z góry liczby bitów (typowo 8, 16, 32 lub 64). Jeżeli chcemy reprezentować liczby o większej długości, to musimy sami sobie to zaprogramować, ale i tak wszystkich liczb naturalnych nie będziemy w stanie wyrazić.
Z tych prostych uwag wynikają ważne wnioski. Po pierwsze może nam zabraknąć liczb do realizacji założonych celów. Po drugie, świat liczb naturalnych różni się od świata liczb naturalnych reprezentowanych w komputerze choćby tym, że nie wszystkie działania będą wykonalne. I to nie tylko chodzi o dzielenie. W szczególności, skoro zbiór liczb reprezentowanych w komputerze jest skończony, to istnieją w nim dwie największe i dodanie ich do siebie spowoduje, że wynik będzie niereprezentowalny.