Propedeutyka Informatyki

Arytmetyka dwójkowa

System dziesiętny jakim na co dzień się posługujemy nie jest jedynym możliwym. W Polskim języku pozostał jeszcze ślad po alternatywnym systemie liczenia: kopa = 5 tuzinów (odpowiednio w przeliczeniu na system dziesiętny: 60, 12). Podstawą tego systemu była liczba 12¹. W takim systemie podaje się obecnie czas (zegar ma 12 godzin).

Najbardziej naturalnym systemem liczbowym dla informatyki jest system dwójkowy. W systemie tym potrzebne jest tylko dwie cyfry (0 i 1). Cyfry są pamiętane w komputerach przy pomocy dwustanowych elementów elektronicznych (stan wysoki lub niski napięcia), a to odpowiada dwóm cyfrom. Przetwarzanie tych liczb wykonuje się przy pomocy tak zwanych bramek logicznych, które utożsamiają cyfrę dwójkową z wartością logiczną: 0 = fałsz, 1 = prawda. W teorii natomiast jedna cyfra odpowiada jednemu bitowi, a bit to najmniejsza ilość informacji.

Dany system liczbowy charakteryzuje ilość potrzebnych cyfr (w systemie dziesiętnym – 10, a dwójkowym 2) oraz sposób konstruowania liczb, który jest uniwersalny. Do momentu wyczerpania cyfr liczymy jednostki. Potem zapisujemy 1 na pozycji dziesiątek, dwunastek czy dwójek – zależnie od systemu i znów liczymy jednostki. I tak dalej

Liczba 101 w systemie dziesiętnym:

1*(10*10) + 0*10 + 1

Ten sam zapis (101) w systemie dwójkowym będzie oznaczał:

1*(2*2) + 0*2 + 1

czyli oczywiście mniej cyfr pozwala zapisać mniejszą liczbę przy użyciu takiej samej liczby znaków. Liczba 101 dwójkowo ma wartość równą 5 dziesiętnie.

Jest to bardzo ważne, gdyż zmienne pamiętające liczby mają określoną ilość bitów. Stąd pytanie: jak dużą liczbą można zapisać przy pomocy określonej ilości znaków. To łatwo obliczyć. Największa liczba składa się z samych maksymalnych cyfr – czyli w systemie dwójkowym 1. Na przykład osiem jedynek pamiętamy w jednym bajcie (bajt = 8 bitów).

Warto zauważyć, że jeśli do 11111111 dodamy 1 to otrzymamy 100000000 (1 i osiem zer). A więc na ośmiu bitach możemy zapamiętać liczbę nie większą niż od 2⁸-1 (dwa do ośmiu minus 1). Czyli 255, co nie jest dużo. Dlatego zazwyczaj przyjmuje się do pamiętania liczb zmienne o większej wielkości: od 2 do 12 bajtów.

Dwa bajty pozwalają zapamiętać liczbę nie większą od 255*255. Jeśli dopuszczamy liczby ujemne – to dodatkowo odpada nam jeden bit na zapamiętanie znaku. Dla naprawdę dużych liczb konieczne są inne sposoby ich pamiętania i specjalne sposoby liczenia.

Liczby w systemie szesnastkowym

Do zapisu liczb w systemie dwójkowym wystarczy dwie cyfry: „0” i „1”. W takim zapisie łatwo o pomyłkę. Dlatego zapis liczby dzieli się na grupy i każdą z tych grup zapisuje odrębnie. Każdą grupę możemy potraktować jak liczbę dziesiętną. Taki zapis stosuje się w adresach internetowych. Na przykład adres 11000000101010000000000000000000 zapisujemy jako 11000000.10101000.00000000.00000000, a po zamianie na liczby dziesiętne: 192.168.0.0 (jest to typowy adres dla sieci lokalnych). Jeśli podzielimy liczbę na grupy po 4 bity (cyfry w układzie dwójkowym), to każda grupa będzie liczbą od 0 do 15. Możemy więc łatwo zamienić na system szesnastkowy. W oznaczeniu uzupełniamy cyfry arabskie o 5 pierwszych liter alfabetu: A=10,B=11, C=12, D=13, E=14, F=15. Powyższy adres można zapisać jako C0A80000 (C=1100, A=1010,8=1000).

Odwrotna notacja polska

Powszechnie stosowany zapis wyrażeń arytmetycznych z użyciem nawiasów nie jest jedynym możliwym. W informatyce stosowany bywa na przykład zapis bez nawiasów („postfiksowy”) zwany „odwrotną notacją polską”². W tym zapisie znak operacji stawiamy po „operandach”.

Dla powyższego przykładu 1*(10*10) + 0*10 + 1

zapis w odwrotnej notacji polskiej będzie wyglądał następująco:

10 10 * 1 * 0 10 * + 1 +

Można to przetestować przy użyciu programu:

stos = []
operatory = {'+', '-', '*', '/'}
wyrazenie=[10,10,'*',1,'*',0,10,'*',1,'+']
for token in wyrazenie:
  if token not in operatory:
    stos.append(token)
  else:
    operand1 = stos.pop()
    operand2 = stos.pop()
    if token == '+':
      wynik_dzialania = operand2 + operand1
    elif token == '-':
      wynik_dzialania = operand2 - operand1
    elif token == '*':
      wynik_dzialania = operand2 * operand1
    elif token == '/':
      wynik_dzialania = operand2 / operand1
    stos.append(wynik_dzialania)
  print(stos)

Program używa dwóch list w jednej jest wyrażenie w notacji odwrotnej polskiej, a w drugiej tak zwany stos. Jest to lista do której dołącza się elementy (append = „włożenie na stos”) lub pobiera ostatnio dodany (pop = „zdjęcie ze stosu”).

zobacz też: https://www.101computing.net/reverse-polish-notation/

Liczby zmiennoprzecinkowe

Dla liczb rzeczywistych są to „liczby zmiennoprzecinkowe”. Najkrócej mówiąc liczby zmiennoprzecinkowe pozwalają zapamiętać bardzo duże liczby z ograniczoną dokładnością. Liczba pamiętana jest w postaci mantysy (określonej ilości cyfr znaczących) oraz wykładnika (cechy). Wartość to mantysa (M) pomnożona przez 2 do potęgi zapisanej jako wykładnik (C):

M*2^C

Język Python traktuje liczby całkowite oraz zmiennoprzecinkowe jako wartości dwóch

różnych typów. Przy użyciu funkcji type() można sprawdzić, z jakim typem mamy do czynienia:

>>> type(5)
<class 'int'>
>>> type(0.5)
<class 'float'>
>>> type(5.0)
<class 'float'>

Jak widać Python „zgaduje” jaki mamy typ danych na podstawie zapisu liczby (czy użyto kropki). Dlatego liczba 5 jest traktowana jak liczba całkowita (typ 'int'), natomiast 5.0 jak rzeczywista / zmiennoprzecinkowa (typ 'float').

Uwaga!

W Pythonie (ogólnie: w programowaniu) stosujemy konwencję amerykańską, zgodnie z którą miejsca dziesiętne w liczbach oddzielamy kropką (a nie – jak w Polsce – przecinkiem).

Liczby jako obiekty

Jeszcze inna możliwość zapisu wyrażeń pojawia się, gdy liczby potraktujemy jak obiekty.

Wiemy już, że liczby całkowite są obiektami typu int. Można na nich wykonywać działania arytmetyczne zapisywane tak jak w kalkulatorze.

Ponieważ jednak są to obiekty, mają zdefiniowane metody (własności) zwane „magicznymi”³, które można jawnie wywołać. Odpowiadają one za poszczególne operacje wykonywane na liczbach. Na przykład __add__ to dodawanie, a __neg__ - negacja.

Te dwa zapisy są równoważne:

Przykład 1:

n=10
n=n+2
n=-n
print(n)

Przykład 2:

n=int(10)
n=n.__add__(2)
n=n.__neg__()
print(n)

Różnica sprowadza się do tego, że drugi zapis wprost używa wywołania metod obiektu.

Obiekty można rozbudowywać poprzez dziedziczenie. Zapis class Potomek(Rodzic) oznacza, że klasa „Potomek” dziedziczy wszystkie własności klasy „Rodzic”. Niektóre z tych własności mogą być w definicji Potomka przedefiniowane („przykryte”),

Przykład:

class Modulo10(int):
    def __add__(self, other):
        return super().__add__(other) % 10

    def __sub__(self, other):
        return super().__sub__(other) % 10
        
    def __mul__(self, other):
        return super().__mul__(other) % 10

    def __neg__(self):
        return super().__neg__() % 10


a=Modulo10(7)
b=a+5
print(b)
c=a*b
print(c)

Zdefiniowaliśmy klasę Modulo10 i użyliśmy jej do kilku działań na liczbach modulo 10 (modulo = reszta z dzielenia).

Czy te definicje działań mogą być dowolne? Nie zawsze ma to sens. Matematycy stworzyli struktury matematyczne (grupy, pierścienie, ciała), dla których podano pewne warunki jakie muszą spełniać definiowane działania.