Podstawowe operacje logiczne
wykonywane przez procesor
Oprócz działań arytmetycznych komputery potrafią wykonywać proste działania logiczne. Reguły rządzące logiką komputera są zdefiniowane przez dział nauki zwany logiką matematyczną (tzw. algebra Boole�a). Elementarne operacje wykonywane przez procesor na bajtach informacji w komputerze: NOT, AND, OR, +, - ,/ , *
Podstawowe operacje logiczne to:
negacja logiczna (zaprzeczenie) NOT,
suma logiczna (alternatywa) OR,
iloczyn logiczny ( koniunkcja ) AND.
Operacje logiczne można wykonywać tylko na zdaniach logicznych. Nie każde zdanie poprawne w języku polskim jest poprawne w sensie logiki matematycznej - na przykład zdanie �Czy jest dzisiaj jest środa?� nie jest zdaniem logicznym, ponieważ nie można mu przyporządkować wartości: PRAWDY lub FAŁSZU. Poprawnym zdaniem logicznym może być następujące zdanie �Dzisiaj jest środa�.
Definicja:
Zdaniem logicznym nazywamy takie zdanie gramatyczne oznajmujące, które może przyjmować jedną z dwóch wartości logicznych PRAWDĘ (1) lub FAŁSZ (0).
Tabelki funkcji logicznych:
negacja logiczna y = NOT x
x |
y = NOT x |
0 |
1 |
1 |
0 |
suma logiczna z = x OR y
x |
y |
z = x OR y |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
iloczyn logiczny z = x AND y
x |
y |
z = x AND y |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
Naturalny system dwójkowy (ang. NBS - Natural Binary System) jest najprostszym systemem pozycyjnym, w którym podstawa p = 2. System posiada dwie cyfry 0 i 1, zatem można je kodować bezpośrednio jednym bitem informacji. Wartość liczby obliczamy zgodnie ze wzorem podanym w rozdziale o systemach pozycyjnych.
|
|
|
|
|
|
|
|
|
|
bn-1bn-2...b2b1b0 = bn-12n-1 + bn-22n-2 + ... + b222 + b121 + b020 gdzie
b - bit, cyfra dwójkowa 0 lub 1 |
|
|
|
|
|
Obliczyć wartość liczby dwójkowej 11100101(2).
11100101(2) = 1 x 27 + 1 x 26 + 1 x 25 + 0 x 24 + 0 x 23 + 1 x 22 + 0 x 21 + 1 x 20
11100101(2) = 1 x 128 + 1 x 64 + 1 x 32 + 0 x 16 + 0 x 8 + 1 x 4 + 0 x 2 + 1 x 1
11100101(2) = 128 + 64 + 32 + 4 + 1
11100101(2) = 229(10)
Jeśli dokładnie przyjrzysz się powyższym obliczeniom, to na pewno zauważysz, iż w systemie binarnym w celu obliczenia wartości liczby wystarczy po prostu zsumować wagi pozycji, na których cyfry przyjmują wartość 1.
101011(2) = 25 + 23 + 21 + 20 = 32 + 8 + 2 + 1 = 43(10)
Jest to znaczne uproszczenie w stosunku do innych systemów, gdzie musimy wykonywać mnożenia cyfr przez wagi pozycji. Tutaj albo dana waga występuje w wartości liczby (cyfra 1), albo nie występuje (cyfra 0). Nie na darmo system binarny jest najprostszym systemem pozycyjnym.
Bardzo ważne dla informatyka i programisty jest nauczenie się na pamięć pierwszych szesnastu liczb binarnych:
dziesiętnie |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
dwójkowo |
0 |
1 |
10 |
11 |
100 |
101 |
110 |
111 |
1000 |
1001 |
1010 |
1011 |
1100 |
1101 |
1110 |
1111 |
Określmy, jaką największą liczbę dwójkową możemy zapisać za pomocą n bitów (czyli cyfr binarnych). Największa liczba musi posiadać same cyfry 1, czyli w wartości liczby muszą uczestniczyć wszystkie wagi pozycji. Zatem:
dla 1b mamy |
1(2) |
= 1(10) |
dla 2b mamy |
11(2) |
= 2 + 1 = 3(10) |
dla 3b mamy |
111(2) |
= 4 + 2 + 1 = 7(10) |
dla 4b mamy |
1111(2) |
= 8 + 4 + 2 + 1 = 15(10) |
... |
|
|
Otrzymujemy kolejne liczby:
dla 1b mamy |
1 |
Liczby te tworzą prosty ciąg potęgowy:
dla 1b mamy |
1 |
= 21 - 1 |
dla 2b mamy |
3 |
= 22 - 1 |
dla 3b mamy |
7 |
= 23 - 1 |
dla 4b mamy |
15 |
= 24 - 1 |
... |
|
|
Wykładnik potęgowy liczby 2 jest równy ilości bitów, zatem dla n bitów otrzymujemy wzór:
|
|
|
|
|
|
|
|
|
|
Z(2) = <0, 2n - 1> |
|
|
|
|
|
Jaką największą liczbę dziesiętną można przedstawić przy pomocy 64 bitów?
Odp.
264 - 1 = 18446744073709551616 - 1 = 18446744073709551615
Schemat Hornera pozwala obliczyć wartość liczby binarnej przy minimalnej ilości operacji arytmetycznych. W systemie binarnym schemat ten jest bardzo prosty:
Schemat Hornera dla systemu binarnego |
Wejście: ciąg cyfr binarnych
krok 1: W |
Operację mnożenia 2 x W możemy zastąpić dodawaniem W + W. Dodawanie komputer wykonuje o wiele szybciej od mnożenia.
Obliczyć schematem Hornera wartość liczby binarnej 111010111101(2)
cyfra 1: W = 1
cyfra 1: W = (1 + 1) + 1 = 3
cyfra 1: W = (3 + 3) + 1 = 7
cyfra 0: W = (7 + 7) + 0 = 14
cyfra 1: W = (14 + 14) + 1 = 29
cyfra 0: W = (29 + 29) + 0 = 58
cyfra 1: W = (58 + 58) + 1 = 117
cyfra 1: W = (117 + 117) + 1 = 235
cyfra 1: W = (235 + 235) + 1 = 471
cyfra 1: W = (471 + 471) + 1 = 943
cyfra 0: W = (943 + 943) + 0 = 1886
cyfra 1: W = (1886 + 1886) + 1 = 3773 - koniec
Kolejne od końca cyfry binarne zapisu liczby w systemie dwójkowym otrzymamy jako reszty z dzielenia tej liczby przez 2. Metoda ta została dokładnie opisana w rozdziale poświęconym przeliczaniu liczb dziesiętnych na zapis w innych systemach liczbowych.
Algorytm wyznaczania cyfr zapisu dwójkowego liczby |
Wejście: W - wartość liczby
krok 1: kolejna cyfra |
Przeliczyć na system dwójkowy liczbę 582642(10).
582642 div 2 = |
291321 |
i reszta 0 |
291321 div 2 = |
145660 |
i reszta 1 |
145660 div 2 = |
72830 |
i reszta 0 |
72830 div 2 = |
36415 |
i reszta 0 |
36415 div 2 = |
18207 |
i reszta 1 |
18207 div 2 = |
9103 |
i reszta 1 |
9103 div 2 = |
4551 |
i reszta 1 |
4551 div 2 = |
2275 |
i reszta 1 |
2275 div 2 = |
1137 |
i reszta 1 |
1137 div 2 = |
568 |
i reszta 1 |
568 div 2 = |
284 |
i reszta 0 |
284 div 2 = |
142 |
i reszta 0 |
142 div 2 = |
71 |
i reszta 0 |
71 div 2 = |
35 |
i reszta 1 |
35 div 2 = |
17 |
i reszta 1 |
17 div 2 = |
8 |
i reszta 1 |
8 div 2 = |
4 |
i reszta 0 |
4 div 2 = |
2 |
i reszta 0 |
2 div 2 = |
1 |
i reszta 0 |
1 div 2 = |
0 |
i reszta 1 - koniec, wynik odczytujemy w kierunku z dołu do góry |
582642(10) = 10001110001111110010(2)