Online: 0x037 (55)
haker.info  — Etyczny hacking_
Spreading knowledge like a virus.

Podstawy arytmetyki komputerowej

   Dawid Farbaniec    1340 s艂贸w

1. 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 鈥瀊鈥 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

2. 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

3. 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 鈥瀦ero 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 鈥瀠jemne 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 鈥瀙rzekr臋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.

4. Zako艅czenie

Dzi臋kuj臋 za czas po艣wi臋cony na przeczytanie tego wpisu.

Dawid Farbaniec


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.