Ważnym tematem omawianym na naszym kursie informatyki są systemy liczbowe
Informatyka od zawsze bazowała na systemie binarnym.
Jest to dwójkowy system liczbowy – oznacza to, że zapis dowolnej liczby jest tworzony przy użyciu tylko dwóch cyfr – 0 i 1.
Owe dwa stany oznaczają – prawdę lub fałsz, włączony lub wyłączony, prąd płynie lub nie płynie. Bardzo wygodnie można zatem ich używać w operacjach logicznych takich jak koniunkcja czy alternatywa, których używa się z kolei do budowania bardziej skomplikowanych systemów takich jak jednostki arytmetyczno-logiczne, które zajmują się realizowaniem obliczeń i operacji logiczn96ych w procesorach.
Najprostsze operacje na liczbach – dodawanie, odejmowanie, dzielenie, mnożenie, przestają być tak proste w zrozumieniu, gdy nie wykonujemy ich na systemie dziesiątkowym, chociaż tak naprawdę rządzą się tymi samymi zasadami.
W końcu system dziesiątkowy, w przeciwieństwie do innych, jest wykorzystywany w niemal wszystkich dziedzinach życia – ceny w sklepach, informacje zapisane w dowodzie czy wszędzie gdzie chcemy określić ile czegoś jest.
Do ręcznego wykonania operacji na dowolnym systemie liczbowym zazwyczaj można zwyczajnie zamienić liczbę na system dziesiętny, wykonać operację a następnie z powrotem zamienić liczbę z dziesiątkowej, na interesujący nas system.
Co jednak, gdy to nie wystarcza – na przykład kiedy wykonujemy obliczenia bez pomocy komputera, a znaczenie ma czas wykonania operacji? Co więcej, komputery same w sobie wszystkie obliczenia przeprowadzają wewnętrznie na systemie binarnym, więc nie mają one luksusu wykonywania obliczeń na systemie dziesiętnym.
Operacja sumowania dwóch liczb w systemie dwójkowym odbywa się następująco:
Oznacza to że:
Przykład dla liczb zapisanych na 4 bitach (mniejszą liczbą dopełniliśmy z lewej strony zerami):
1101 + 0011 = 10000
Uwaga:
W komputerze liczby binarne są przechowywane w konkretnej ilości bitów (8, 16, 32, itd.). Jeżeli nasza suma będzie musiała być zapisana na większej ilości bitów, niż zakładaliśmy nastąpi tzw. overflow (nadmiar lub przepełnienie). W sytuacji wystąpienia overflow, utracona zostaje wartość bitu o największym znaczeniu.
Na przykład gdy miejsce przeznaczone na dodawanie jest ustalone na 4 bity:
1111(2) + 0001(2) = (1)1111 – wartość piątego bitu zostanie utracona.
Można temu zapobiec zawczasu alokując więcej pamięci na sumę, niż potrzebowaliśmy do zapisania.
W skrajnej sytuacji np. 1111 + 1111 = 11110, czyli nawet dla liczb złożonych z samych jedynek, na zapisanie sumy będziemy potrzebować maksymalnie 1 bitu więcej. Co ciekawe dodając analogicznie liczby w systemie dziesiętnym złożone z samych dziewiątek, również będziemy potrzebowali jednej cyfry więcej. Prawidłowość ta występuje dla dowolnych systemów pozycyjnych.
Operacja odejmowania binarnego odbywa się na podobnych zasadach jak dodawania, z tą różnicą, że zamiast przeniesienia, mamy zapożyczenie:
Oznacza to, że:
Przykład:
1101 – 11 = ?
Uwaga:
Podobnie jak przy operacji dodawania, jeżeli będziemy nieostrożni, to możemy wyjść poza zakres bitowy przeznaczony na zapisanie wyniku odejmowania. Nastąpi wtedy sytuacja przeciwna do „przepełnienia” - czyli underflow (niedomiar). Sytuacja taka wystąpi, gdy od mniejszej liczby odejmiemy mniejszą – naturalny system binarny nie jest przystosowany do kodowania liczb ujemnych. Próba odjęcia zapożyczenia od bitu niebędącego w zakresie sprawi, że zwrócony wynik będzie wartością maksymalną jaką można zapisać na danej ilości bitów.
Przykład dla liczb zapisanych na 4 bitach:
0000 (2) – 0001 (2) = 1111
Aby zapobiec takiej sytuacji, należy sprawdzić która liczba jest większa:
Ustawiamy obie liczby jedna pod drugą w taki sposób, aby ich bity o tej samej znaczności znalazły się w jednej kolumnie (wygodniej jest dłuższą zapisać nad krótszą).
Następnie stosujemy zwykłe mnożenie „pisemne”:
Przykład:
101 * 1011 = ?
Operację dzielenia binarnego można przeprowadzić ręcznie korzystając z metody „pisemnej” tak, jak to robimy w systemie dziesiętnym.
Kiedy jednak chcemy podzielić dwie liczby binarne w programie komputerowym, należy:
Przykład:
1010 : 11 = ?
Dzielna „0001” jest mniejsza od dzielnika „11”, więc resztą z dzielenia będzie „0001” a ilorazem liczba, którą zapisaliśmy nad kreską dzielenia – „11”.
[ 2 ] – jeżeli ostatni bit (skrajnie po prawej) jest równy 0, to liczb jest parzysta.
[ 3 ] – zasada wygląda następująco:
[ 5 ] – sposób działania:
czyli kolejne reszty z dzielenia to: 1, 2, 4, 3, 1, 2, 4, 3, 1, …
[ 7 ] – sposób działania:
Przykład:
Przyjmijmy liczbę – 28 (10) = 11100 (2)
11100 | 111 → ?
1.
Ostatni = 0
Reszta = 1110
2.
Różnica = 1110 – 00 = {14 – 0 } = 1110 (2) = 14 (10)
3.
(1110 | 111 ⇔ 14 | 7 ) => (11100 | 111 ⇔ 28 | 7)
Jest co ciekawy sposób podejścia, ale czy aby na pewno przydatny? Nie koniecznie możemy znać przecież wartość dziesiętną różnicy. Czy można zmodyfikować ten sposób, aby nie trzeba było zamieniać liczby na system dziesiątkowy?
Sprawdźmy jak algorytm zachowa się dla liczby 7:
111 | 111 → ?
1.
Ostatni = 1
Reszta = 11
2.
Różnica = 11 – 11 = 0
Wiemy już, że dla liczby 7, algorytm zwraca 0. Ponadto z zasady działania wiemy, że jeżeli wynik różnicy jest podzielny przez 7, to liczba też dzieli się przez 7 całkowicie.
Można więc używać algorytmu tak wiele razy, aż napotkamy jedną z dwóch „instrukcji stop”:
W przeciwnym wypadku powtarzamy działanie algorytmu.
Przykład:
101110 | 7 = ?
Pierwsze wykonanie algorytmu wyglądać będzie następująco:
Następne wykonania algorytmu:
[ podzielność przez kolejne potęgi liczby 2]
Przyjmijmy n za dowolną potęgę 2.
Jeżeli wszystkie bity o mniejszej znaczności od bitu, którego wartość wynosi n wynoszą 0, to liczba ta jest podzielna przez n.
Przykład:
110101000 (2)
Dla n = 4:
Nasz bit kodujący liczbę n, znajduje się na 3 pozycji licząc od najmniej znaczącego bitu, czyli:
110101000 (2)
Wszystkie bity przed nim są równe 0, więc liczba ta, jest podzielna przez 4.
110101000 (2) = 424 (10)
424 | 4 = Prawda → zgadza się
Dla n = 16:
110101000 (2)
Nie wszystkie bity przed nim są równe 0, więc ta liczba nie jest podzielna przez 16.
424 | 16 = Fałsz → zgadza się
Ciekawostka:
Korzystając z powyższych zasad, można w prosty sposób sprawdzić podzielność naszej liczby, przez liczby złożone – na przykład aby liczba była podzielna przez 12, musi się ona dzielić przez 4 (potęgę dwójki) oraz 3.