Koło informatyczne

Przyspieszony kurs języka C++

Liczby całkowite w systemie dwójkowym

Współczesne komputery przetwarzają bity. Bit może przyjąć tylko jeden z dwóch stanów. Stany te na papierze oznaczamy cyframi 0 i 1. Wewnątrz komputera bity są pamiętane jako poziomy napięć, np. 0,4V i 5V. Powodem wyboru bitów były względy ekonomiczne – układy elektroniczne przetwarzające tylko dwa poziomy napięć są prostsze od układów, gdzie tych poziomów byłoby więcej. Rośnie również niezawodność i odporność na błędy.

Powstaje pytanie, jak za pomocą bitów można przedstawiać liczby? Odpowiedzią są liczbowe systemy pozycyjne. Ludzie już od dawna używają takich systemów. W systemie dziesiętnym mamy 10 cyfr:

{0,1,2,3,4,5,6,7,8,9}

Za pomocą tych cyfr zapisujemy liczby. W systemie pozycyjnym istotne jest położenie cyfry w zapisie liczby. Każda pozycja posiada tzw. wagę. W systemie dziesiętnym wagi pozycji są kolejnymi potęgami liczby 10, którą nazywamy podstawą systemu:

obrazek

Cyfra określa ilość wag danej pozycji, która występuje w liczbie. W powyższym przykładzie nasza liczba składa się z 7 tysięcy, 5 setek, 3 dziesiątek i 6 jedności (zwróć uwagę, że pozycje numerujemy od końca zapisu liczby, a wagi tych pozycji są równe podstawie systemu podniesionej do potęgi numeru pozycji). Jest to dla wszystkich oczywiste. Jeśli jednak zmienimy podstawę systemu, to ta oczywistość zniknie, ponieważ zapis liczby nie będzie odpowiadał jej wartości dziesiętnej. Na przykład weźmy liczbę piątkową. W systemie piątkowym mamy 5 cyfr:

{0,1,2,3,4}

Zapis pewnej liczby wygląda następująco:

obrazek

Problem jest taki, że chociaż liczba wygląda znajomo, to jednak nie ma wartości trzy tysiące sto czterdzieści dwa, ponieważ wagi jej pozycji są teraz potęgami liczby 5. W liczbie tej mamy 3 sto dwudziestki piątki, 1 dwudziestkę piątkę, 4 piątki oraz 2 jedynki. Zatem jej wartość w systemie dziesiętnym jest równa:

3 x 125 + 1 x 25 + 4 x 5 + 2 x 1 = 375 + 25 + 20 + 2 = 422

Wynika z tego prosty wniosek. Jeśli operujemy na systemach liczbowych o różnych podstawach, to zawsze powinniśmy oznaczyć, w którym systemie dana liczba jest zapisana. Umówmy się, że liczby dziesiętne, jako standardowe, nie będziemy specjalnie oznaczać. W myśl tej konwencji mamy:

3142₅ = 422

Zapamiętaj ważną rzecz:

Wartość liczby pozycyjnej jest równia sumie iloczynów cyfr przez wagi ich pozycji. Waga ostatniej pozycji (dla liczby całkowitej) jest zawsze równa 1. Wagi kolejnych pozostałych pozycji można prosto wyliczyć, mnożąc poprzednią wagę przez podstawę systemu. Na przykład dla liczby szóstkowej 52013₆:

6x216	6x36	6x6	1x6	1
1296	216	36	6	1
5	2	0	1	3

Wartość tej liczby jest równa:

5 x 1296 + 2 x 216 + 1 x 6 + 3 = 6480 + 432 + 6 + 3 = 6921

52013₆ = 6921

Najmniejszą podstawą dla systemów pozycyjnych jest liczba 2. System o takiej podstawie nazywamy systemem dwójkowym lub systemem binarnym (co na jedno wychodzi, gdyż przymiotnik binarny jest tylko "mądrzejszą" wersją zupełnie dobrego przymiotnika dwójkowy). System posiada tylko dwie cyfry, które idealnie można zastąpić bitami (bit = binary digit, czyli cyfra dwójkowa):

{0,1}

Zapis liczby wygląda następująco:

obrazek

W systemie dwójkowym wartość liczby oblicza się szczególnie prosto, ponieważ mamy tylko iloczyny cyfr 0 i 1. Jeśli cyfra ma wartość 0, to jej wagi brak w liczbie. Bierzemy zatem tylko wagi pozycji, na których stoją cyfry 1 i sumujemy je:

8 + 2 + 1 = 11

1011₂ = 11

Każdy informatyk powinien znać pierwsze 16 liczb dwójkowych. Naucz się ich na pamięć:

Wartość dziesiętna	Liczba dwójkowa
0	0000
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000
9	1001
10	1010
11	1011
12	1100
13	1101
14	1110
15	1111

Dla wprawy oblicz wartość liczb dwójkowych:

111000₂ = ?
101010₂ = ?
101101₂ = ?

Obliczanie wartości dziesiętnej liczb dwójkowych jest proste. Jak jednak przeliczyć liczbę dziesiętną na dwójkową? Istnieje prosty algorytm (przepis, sposób postępowania), który rozwiązuje ten problem.

Jeśli liczba jest równa zero, to wynikiem jest zero
inaczej dopóki liczba nie jest równa zero, dzielimy ją przez 2 i za kolejną od końca cyfrę bierzemy resztę z tego dzielenia.

Przeliczmy wg tego algorytmu liczbę 89 na zapis dwójkowy:

89 : 2 = 44 i reszta 1

	44 : 2 = 22 i reszta 0

	22 : 2 = 11 i reszta 0

	11 : 2 =  5 i reszta 1

	 5 : 2 =  2 i reszta 1

	 2 : 2 =  1 i reszta 0

	 1 : 2 =  0 i reszta 1

, kończymy, bo liczba jest równa 0.

89 = 1011001₂

Dla wprawy przelicz na system dwójkowy liczby dziesiętne 100 i 1000.

Bardzo ważną rzeczą jest zakres liczb dwójkowych. Odpowiedzmy sobie na pytanie, jakie liczby da się przedstawić za pomocą n bitów. Najmniejszą liczbą będzie oczywiście 0:

000...000
n bitów

A jaka będzie największa? Największa będzie wtedy, gdy wszystkie cyfry przyjmą wartość 1 (dlaczego?). Zapiszmy:

Liczba bitów	Liczba dwójkowa	Wartość dziesiętna
1	1	1
2	11	3
3	111	7
4	1111	15
5	11111	31
6	111111	63
...	...	...

Cała trudność sprowadza się do zauważenia faktu, iż otrzymany ciąg wartości dziesiętnych da się zapisać następująco:

Liczba bitów	Liczba dwójkowa	Wartość dziesiętna	Ciąg
1	1	1	2 - 1	2¹ - 1
2	11	3	4 - 1	2² - 1
3	111	7	8 - 1	2³ - 1
4	1111	15	16 - 1	2⁴ - 1
5	11111	31	32 - 1	2⁵ - 1
6	111111	63	64 - 1	2⁶ - 1
...	...	...	...
n	111...111			2ⁿ - 1

Zatem: przy pomocy n bitów możemy zapisać liczby z zakresu od 0 do 2ⁿ - 1. Zapamiętaj ten fakt.

Taki system zapisu liczb nosi nazwę naturalnego kodu binarnego i jest oznaczany skrótem NBC (ang. Natural Binary Code). Kod NBC pozwala kodować tylko liczby nieujemne.