Online: 0x02D (45)
haker.iиfø  — Etyczny hacking_
Spreading knowledge like a virus.

Podstawy arytmetyki komputerowej

   Dawid Farbaniec    1340 słów

0x01. Słowem wstępu

la niektórych ten wpis może być tylko przypomnieniem, ale postanowiłem to jednak opisać. Rozpocznę od wyjaśnienia czym jest system liczbowy. System reprezentacji liczb pozwala zapisywać liczby z użyciem określonego zbioru znaków. Dwa bardzo ważne w informatyce systemy liczbowe oprócz dziesiętnego, którego używamy na co dzień to system binarny (dwójkowy) oraz heksadecymalny (szesnastkowy). Często w celu rozróżnienia w jakim systemie jest zapisana określona liczba używa się przedrostków i przyrostków. Liczby binarne przyjęło się zapisywać z przyrostkiem „b” np. 101000111b. Natomiast liczby w systemie heksadecymalnym zapisuje się z przyrostkiem h np. 02FFh lub z przedrostkiem 0x np. 0x2FF.

Nie chcę tutaj tworzyć na ten temat wywodu matematycznego. Na początek wystarczy, że początkujący czytelnicy, gdy zobaczą w programie zapis np. 0FFFFh to będą wiedzieć, że to liczba tylko inaczej zapisana (szesnastkowo). W systemie dwójkowym (binarnym) do zapisu określonej liczby używa się tylko dwóch znaków: zero (0) oraz jeden (1). Natomiast w systemie szesnastkowym (heksadecymalnym) do przedstawienia liczby używa się szesnastu znaków: od 0 do 9 oraz od A do F.

W tabeli poniżej przedstawiono przykładowe wartości liczbowe zapisane w trzech różnych systemach.

System decymalny (dziesiętny) System binarny (dwójkowy) System heksadecymalny (szesnastkowy)
1 1 1
2 10 2
3 11 3
... ... ...
9 1001 9
10 1010 A
11 1011 B
12 1100 C
13 1101 D
14 1110 E
15 1111 F
16 10000 10
17 10001 11
18 10010 12
... ...
255 11111111 FF
256 100000000 100
257 100000001 101
... ...
65532 1111111111111100 FFFC
65535 1111111111111111 FFFF

0x02. Konwersje pomiędzy systemami liczbowymi

Do przeliczania wartości pomiędzy systemami liczbowymi można użyć systemowego kalkulatora.
Wystarczy tylko przełączyć się w Tryb programisty (rysunek 2.1).

Kalkulator Windows
Rysunek 2.1. Kalkulator systemowy w trybie Programisty

0x03. Bity, bajty, słowa...

Pamięć komputerowa posiada swoje jednostki miary. Najmniejsza jednostka informacji pamięci komputerowej to bit. Może mieć on wartość jeden lub zero (rysunek 3.1).

Bit
Rysunek 3.1. Bit jako jednostka informacji pamięci komputerowej

Inne jednostki to:

  • Półbajt (ang. nibble) – ma rozmiar 4 bitów.
  • Bajt (ang. byte) – ma on rozmiar 8 bitów.
  • Słowo (ang. word) – ma rozmiar 16 bitów (2 bajty).
  • Podwójne słowo (ang. dword) – ma rozmiar 32 bitów (4 bajty).
  • Poczwórne słowo (ang. qword) – ma rozmiar 64 bitów (8 bajtów).
  • Ośmiokrotne słowo (ang. octword) – nazywane też podwójne poczwórne słowo i ma rozmiar 128 bitów (16 bajtów).
  • Podwójne ośmiokrotne słowo (ang. double octword) – ma rozmiar 256 bitów (32 bajty).
  • Kilobajt (ang. kilobyte) – ma rozmiar 1024 bajtów.
  • Megabajt (ang. megabyte) – ma rozmiar 1024 kilobajtów.
  • etc.

Skrócone symbole określające poszczególne jednostki to: b – bit, B – bajt, KB – kilobajt, MB – megabajt etc.

3.1. Operacje logiczne na bitach

Chyba w każdym języku programowania można spotkać operatory lub instrukcje logiczne operujące na bitach. Podstawowe operacje, które możemy przeprowadzić przedstawiono poniżej.

Iloczyn logiczny (koniunkcja)

Wynik jest prawdziwy tylko wtedy, gdy dwa operandy są prawdziwe (rysunek 3.2).

And
Rysunek 3.2. Iloczyn logiczny (koniunkcja)

Suma logiczna (alternatywa)

Wynik jest prawdziwy, jeśli chociaż jeden operand jest prawdziwy (rysunek 3.3).

Or
Rysunek 3.3. Suma logiczna (alternatywa)

Suma modulo 2 (alternatywa wykluczająca)

Wynik jest prawdziwy, jeśli jeden i tylko jeden operand jest prawdziwy (rysunek 3.4).

Xor
Rysunek 3.4. Suma modulo 2 (alternatywa wykluczająca)

Zaprzeczenie logiczne (negacja)

Wynik jest odwróceniem operandu (rysunek 3.5).

Not
Rysunek 3.5. Zaprzeczenie logiczne (negacja)

Łączenie operacji logicznych

Operacje logiczne mogą być łączone. Na rysunku 3.6 przedstawiono koniunkcję z zaprzeczonym pierwszym operandem.

Andn
Rysunek 3.6. Koniunkcja logiczna z zaprzeczonym pierwszym operandem (ANDN)

Przykład

Dla przykładu poniżej przedstawiono koniunkcję logiczną dla dwóch liczb binarnych (rysunek 3.7).

AND Przykład
Rysunek 3.7. Koniunkcja logiczna na dwóch przykładowych liczbach binarnych

3.2. Liczby ze znakiem i bez znaku

W przypadku typów danych ze znakiem (ang. signed) przyjęto, że najstarszy bit jest nazywany bitem znaku (rysunek 3.8). Jego wartość decyduje czy dana liczba jest dodatnia czy ujemna. Jeśli najstarszy bit jest ustawiony, to liczba traktowana jest jako ujemna, a w przeciwnym wypadku jako dodatnia. Określenie czy liczba binarna jest ze znakiem czy bez znaku zależne jest od interpretacji. Jeśli w bajcie (rozmiar 8 bitów) ustawimy wszystkie bity: 11111111b to przeliczając do systemu dziesiętnego będzie to wartość 255d bez znaku lub -1d w przypadku interpretacji jako typ ze znakiem.

Bity, bajty, słowa
Rysunek 3.8. Koniunkcja logiczna na dwóch przykładowych liczbach binarnych

Istnieją różne metody kodowania liczb binarnych ze znakiem, ale najbardziej naturalna jest metoda z uzupełnieniem do dwóch (U2). Poszczególne kroki dla przykładowej liczby -14 są następujące:

  • Obliczenie wartości bezwzględnej (ang. absolute value):
    |-14d| = 14d = 1110b
  • Dopisanie zer na początku, aby liczba bitów była wielokrotnością liczby dwa:
    00001110b
  • Zanegowanie logiczne wartości:
    NOT 00001110b = 11110001b
  • Dodanie liczby jeden do rezultatu:
    11110001b + 1b = 11110010b = -14d

Warto wspomnieć też o terminie takim jak „zero ze znakiem”. W niektórych reprezentacjach liczb binarnych (np. uzupełnienie do jeden, czyli U1 czy też formaty zmiennoprzecinkowe np. IEEE 754) możliwe jest otrzymanie liczby zero z ustawionym bitem znaku. Wartość określana jest wtedy jako „ujemne zero” (ang. negative zero).

3.3. Rozszerzenie z zachowaniem znaku

Rozszerzenie z zachowaniem znaku (ang. sign extension) może występować np. przy wpisaniu wartości o rozmiarze bajtu do rejestru lub zmiennej o rozmiarze słowa. Mechanizm jest bardzo prosty. Polega on na powieleniu bitu znaku na pozostałe (starsze) bity (rysunek 3.9).

Na przykład:

  • -14d = 11110010b jako bajt,
  • -14d = 1111111111110010b jako słowo,
  • -14d = 11111111111111111111111111110010b jako podwójne słowo
  • etc.

Sign extension
Rysunek 3.9. Rozszerzenie z zachowaniem znaku

3.4. Dopełnienie zerami

Dopełnienie zerami (ang. zero extension) działa na zasadzie wpisania zer w starsze bity np. przy wpisaniu wartości o rozmiarze bajta do rejestru lub zmiennej większego rozmiaru (rysunek 3.10).

Zero extension
Rysunek 3.10. Dopełnienie zerami

3.5. Przepełnienie zmiennej całkowitej

Przepełnienie zmiennej całkowitej (ang. integer overflow) występuje, gdy wartość rezultatu obliczeń jest poza zakresem możliwym do przechowania przez określony typ danych. Maksymalna wartość jaką można zapisać na jednym bajcie (8 bitach) bez znaku to 255d (0FFh). Co zatem będzie jeśli wykonamy operację np. 253d + 5d? Wynik będzie równy 2d. Można to porównać do „przekręcenia” się licznika np. tak jak w starszych samochodach.

Poniżej trzy przykłady dla operacji na danych o rozmiarze jednego bajta:

  • 255d + 1d = 0d
  • 0d – 2d = 254d
  • 5d – 24d = 237d

Binarnie wyglądałoby to następująco:

  • 11111111b + 00000001b = 00000000b
  • 00000000b – 00000010b = 11111110b
  • 00000101b – 00011000b = 11101101b

3.6. Awansowanie typów zmiennych

Awans zmiennej to proces w którym typ danych, który posiada mniejszy zakres wartości (np. bajt) jest zamieniany na taki o większym zakresie (np. int) podczas operacji arytmetycznej. Dzięki temu operacja nie wywołuje przepełnienia (ang. overflow). Na rysunku 3.11 przedstawiono przykład w Visual C++. Mnożenie dwóch bajtów o wartościach 20 oraz 64 daje w wyniku 1280. Wartość ta nie zmieści się w bajcie, który ma tutaj zakres od 0 do 255. Podczas obliczeń następuje awans zmiennej. Dalej jest podzielenie 1280 przez 10, co daje w wyniku 128. Wartość ta mieści się w zmiennej o rozmiarze bajta i zostaje poprawnie wyświetlona przez funkcję printf.

Awans zmiennej
Rysunek 3.11. Awans zmiennej z BYTE na INT (Visual C++)

3.7. Saturacja wartości

Saturacja polega na ustaleniu limitu, przedziału wartości dla danej zmiennej. Jeśli wynik jest większy niż górny limit (maksimum) to przyjmuje wartość maksymalną. W przypadku, gdy wynik jest mniejszy niż minimum, to przyjmuje wartość minimalną. Pozwala to częściowo uchronić przed błędnym działaniem programu i warto to stosować.

Na przykład jeśli ustalimy dla zmiennej limit wartości od -64 do 64 to poniższe operacje dadzą następujące wyniki:

  • 50 + 20 = 70, po saturacji 64,
  • 60 + 4 = 64, po saturacji też 64,
  • 4 × 25 = 100, przy saturacji 64,
  • 10 – 90 = -80, przy saturacji -64,
  • (4 × 30) – (2 × 10) = 100, przy saturacji 64 – 20 = 44.

3.8. To nie liczba – Not a Number (NaN)

Nie zawsze w obliczeniach komputerowych wynikiem jest liczba. Sądzę, że nawet nieodpowiednią rzeczą byłoby np. zwracanie zawsze zero, jeśli wynik jest nieprawidłowy. Wartość NaN (Not a Number) jest często spotykana w obliczeniach zmiennoprzecinkowych (ang. floating-point). Standard kodowania takich liczb (IEEE 754) definiuje taką wartość jak właśnie NaN, a także inne nietypowe wartości jak np. nieskończoność (±INFINITE). Wartość NaN według formatu IEEE 754 posiada w wykładniku same jedynki, a w mantysie wartość różną od zera.

0x04. Zakończenie

Dziękuję za czas poświęcony na przeczytanie tego wpisu.

Dawid Farbaniec

Wykaz literatury (bibliografia)

  • Advanced Micro Devices Inc., 2017 – AMD64 Architecture Programmer's Manual
  • Intel Corporation, 2019 – Intel 64 and IA-32 Architectures Software Developer's Manual
  • Randall Hyde, 2010 – Asembler. Sztuka programowania. Wydanie II, ISBN: 9788324628544
  • open-std.org, 2019 – Working Draft, Standard for Programming Language C++

Tagi:  inne 

Komentarze czytających

Wszystkie treści umieszczone na tej witrynie są chronione prawem autorskim. Surowo zabronione jest kopiowanie i rozpowszechnianie zawartości tej witryny bez zgody autora. Wszelkie opublikowane tutaj treści (w tym kody źródłowe i inne) służą wyłącznie celom informacyjnym oraz edukacyjnym. Właściciele tej witryny nie ponoszą odpowiedzialności za ewentualne niezgodne z prawem wykorzystanie zasobów dostępnych w witrynie. Użytkownik tej witryny oświadcza, że z zamieszczonych tutaj danych korzysta na własną odpowiedzialność. Wszelkie znaki towarowe i nazwy zastrzeżone zostały użyte jedynie w celach informacyjnych i należą wyłącznie do ich prawnych właścicieli. Korzystając z zasobów witryny haker.info oświadczasz, że akceptujesz powyższe warunki oraz politykę prywatności.