Systemy liczbowe: zadania z rozwiązaniami krok po kroku

1Czym jest system liczbowy

W życiu codziennym liczysz w systemie dziesiętnym, o podstawie 10. Ma dziesięć cyfr, od 0 do 9, a każde miejsce jest warte dziesięć razy więcej niż miejsce po jego prawej stronie.

W liczbie 352 cyfra 3 jest warta 300, cyfra 5 jest warta 50, a cyfra 2 jest warta 2. Miejsca mają wartości 1, 10, 100, licząc od prawej.

Komputer przechowuje wszystko jako przełączniki włączone lub wyłączone. Dlatego liczy w systemie dwójkowym (binarnym), o podstawie 2, tylko z cyframi 0 i 1.

Jedna cyfra dwójkowa to bit. Grupa 8 bitów to bajt.

Zasada jest taka sama w każdym systemie: każda cyfra jest warta swoją wartość razy potęgę podstawy.

2System dwójkowy i szesnastkowy

W systemie dwójkowym miejsca mają wartości 1, 2, 4, 8, 16 i tak dalej, licząc od prawej. Każde miejsce jest warte dwa razy więcej niż miejsce po jego prawej stronie.

W liczbie 8-bitowej miejsca mają wartości 128, 64, 32, 16, 8, 4, 2 i 1.

Aby odczytać liczbę dwójkową, dodaj wartości miejsc wszystkich bitów równych 1. Dla 0011 0010 jest to 32 + 16 + 2 = 50.

Długie ciągi bitów trudno czytać. Programiści często zapisują je zamiast tego w systemie szesnastkowym (hex), o podstawie 16.

System szesnastkowy potrzebuje 16 cyfr. Używa cyfr od 0 do 9, a potem liter A = 10, B = 11, C = 12, D = 13, E = 14 i F = 15.

Miejsca w systemie szesnastkowym mają wartości 1, 16, 256 i 4096, licząc od prawej. Liczbę szesnastkową często zapisuje się z 0x z przodu, na przykład 0x2F.

Jedna cyfra szesnastkowa to dokładnie 4 bity, więc 0011 0010 to 0x32: 0011 to 3, a 0010 to 2.

3Liczby ujemne: kod uzupełnień do dwóch

Bajt, w którym wszystkie miejsca są dodatnie, przechowuje wartości od 0 do 255. Nazywamy to zapisem bez znaku.

Do przechowywania liczb ujemnych komputery używają kodu uzupełnień do dwóch. Jedyna zmiana polega na tym, że skrajnie lewy bit jest wart −128 zamiast +128.

Zatem 1000 0011 to −128 + 2 + 1 = −125. Skrajnie lewy bit nazywa się bitem znaku: gdy wynosi 1, liczba jest ujemna.

8-bitowa liczba w kodzie uzupełnień do dwóch obejmuje zakres od −128 (1000 0000) do +127 (0111 1111).

Aby zapisać liczbę ujemną −x, zacznij od +x w zapisie dwójkowym, zaneguj każdy bit (0 zamień na 1, 1 na 0) i dodaj 1.

Przykład dla −5: 5 to 0000 0101. Po zanegowaniu bitów jest to 1111 1010. Dodanie 1 daje 1111 1011.

Ten sam wzorzec odczytany jako liczba bez znaku ma wartość 256 − x. Dla −5 jest to 251, a 1111 1011 to rzeczywiście 128 + 64 + 32 + 16 + 8 + 2 + 1 = 251.

4Metoda krok po kroku

Z systemu dwójkowego lub szesnastkowego na dziesiętny:

1. Zapisz wartość miejsca pod każdą cyfrą: potęgi 2 dla systemu dwójkowego, potęgi 16 dla szesnastkowego, zaczynając od 1 po prawej.
2. W systemie szesnastkowym zastąp każdą literę jej wartością: od A = 10 do F = 15.
3. Pomnóż każdą cyfrę przez wartość jej miejsca i dodaj wszystko.

Kod uzupełnień do dwóch:

1. Aby odczytać wzorzec, nadaj skrajnie lewemu bitowi wartość −128 (w 8 bitach) i dodaj wartości miejsc wszystkich bitów równych 1.
2. Aby zapisać −x, zapisz +x na 8 bitach, zaneguj każdy bit i dodaj 1.
3. Wartość tego wzorca bez znaku to 256 − x. Użyj jej do sprawdzenia bitów.

Bity, zakresy i pamięć:

1. n bitów daje 2ⁿ różnych wzorców.
2. Bez znaku przechowują od 0 do 2ⁿ − 1. W kodzie uzupełnień do dwóch przechowują od −2ⁿ⁻¹ do 2ⁿ⁻¹ − 1.
3. Aby każdy z k elementów dostał własny kod, znajdź najmniejsze b, dla którego 2^b ≥ k.
4. Dla pamięci pomnóż liczbę elementów przez liczbę bitów na element, a potem podziel przez 8, aby dostać bajty, i przez 1024, aby dostać KiB.

5Przykład krok po kroku

Przejdź przez każdy krok. Spróbuj przewidzieć następny, zanim go odsłonisz.

6Typowe błędy

• Zapomnienie o dodaniu 1 po zanegowaniu bitów. Wynik jest o jeden za mały.
• Odczytanie wzorca w kodzie uzupełnień do dwóch jako liczby bez znaku, na przykład 1111 1111 jako 255 zamiast −1.
• Traktowanie bitu znaku jak znaku minus przed pozostałymi bitami. W kodzie uzupełnień do dwóch jest on wart −128.
• Podawanie miejsc w złej kolejności. Miejsce o wartości 1 jest zawsze po prawej.
• Przyjęcie A = 11 w systemie szesnastkowym. Litery zaczynają się od A = 10.
• Mieszanie bitów i bajtów w zadaniach o pamięci. Podziel liczbę bitów przez 8.

7Jak wyglądają zadania egzaminacyjne

• Łatwe: z systemu dwójkowego i szesnastkowego na dziesiętny. Zamień 8-bitową liczbę dwójkową lub 3-cyfrową liczbę szesnastkową na dziesiętną.
• Średnie: kod uzupełnień do dwóch. Odczytaj wartość 8-bitowego wzorca ze znakiem albo zapisz liczbę ujemną jako wzorzec i podaj jego wartość bez znaku.
• Trudne: bity, zakresy i pamięć. Największa lub najbardziej ujemna wartość mieszcząca się w n bitach, liczba bitów potrzebnych na k kodów albo pamięć zajmowana przez obraz.

Przykład trudnego zadania: obraz 256 × 256 z 24 bitami na piksel zajmuje 256 · 256 · 24 / 8 / 1024 = 192 KiB.