http://www.eioba.pl/a2149/naturalny_system_dwojkowy

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:

1. negacja logiczna (zaprzeczenie) NOT,

2. suma logiczna (alternatywa) OR,

3. 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:

1. negacja logiczna y = NOT x

x	y = NOT x
0	1
1	0

2. suma logiczna z = x OR y

x	y	z = x OR y
0	0	0
1	0	1
0	1	1
1	1	1

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

		Wartość dziesiętna liczby zapisanej w naturalnym kodzie binarnym bn-1bn-2...b2b1b0 = bn-12^n-1 + bn-22^n-2 + ... + b22^2 + b12^1 + b02^0 gdzie b - bit, cyfra dwójkowa 0 lub 1 n - liczba bitów w zapisie liczby




 

Obliczyć wartość liczby dwójkowej 11100101₍₂₎.

11100101₍₂₎ = 1 x 2⁷ + 1 x 2⁶ + 1 x 2⁵ + 0 x 2⁴ + 0 x 2³ + 1 x 2² + 0 x 2¹ + 1 x 2⁰
11100101₍₂₎ = 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₍₂₎ = 128 + 64 + 32 + 4 + 1
11100101₍₂₎ = 229₍₁₀₎

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⁵ + 2³ + 2¹ + 2⁰ = 32 + 8 + 2 + 1 = 43₍₁₀₎

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 dla 2b mamy dla 3b mamy dla 4b mamy ...

1 3 7 15

Liczby te tworzą prosty ciąg potęgowy:

dla 1b mamy	1	= 2^1 - 1
dla 2b mamy	3	= 2^2 - 1
dla 3b mamy	7	= 2^3 - 1
dla 4b mamy	15	= 2^4 - 1
...

Wykładnik potęgowy liczby 2 jest równy ilości bitów, zatem dla n bitów otrzymujemy wzór:

		Zakres n bitowej liczby w naturalnym kodzie dwójkowym wynosi Z(2) = <0, 2^n- 1>




 

Jaką największą liczbę dziesiętną można przedstawić przy pomocy 64 bitów?

Odp.

2⁶⁴ - 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 Wyjście: W - wartość liczby reprezentowanej przez ciąg cyfr binarnych krok 1: W pierwsza cyfra krok 2: dopóki są kolejne cyfry wykonujemy operację W 2 x W + kolejna cyfra krok 3: Kończymy

 

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₍₂₎
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 Wyjście: ciąg cyfr binarnych reprezentujących w systemie dwójkowym wartość W krok 1: kolejna cyfra W mod 2, W W div 2 krok 2: jeśli W > 0, wróć do kroku 1 krok 3: Wyprowadź otrzymane cyfry w kolejności odwrotnej do ich otrzymania krok 4: Koniec




 

Przeliczyć na system dwójkowy liczbę 582642₍₁₀₎.

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₍₁₀₎ = 10001110001111110010₍₂₎

---