Arytmetyka komputera
Wyjaśnienie zagadnienia z
przykładami
Podstawowe pojęcia
Bit – (ang. binary digit) najmniejsza ilość informacji potrzebna
do określenia, który z dwóch równie prawdopodobnych
stanów przyjął układ. Jest to ednostka logiczna. Bit
przyjmuje jedną z dwóch wartości, które zwykle określa się
jako 0 (zero) i 1 (jeden), choć można przyjąć dowolną inną
parę wartości, np. prawda i fałsz czy -1 i +1. W pierwszym
przypadku bit jest tożsamy z cyfrą w systemie dwójkowym.
• Binarny sposób zapisu informacji związany jest z tym, że
komputer jako urządzenie elektroniczne rozpoznać może
dwa stany prądowe:
• 0 – brak napięcia lub bardzo niskie (mniej niż 10% wartości
wysokiego)
• 1 – wysokie napięcie.
Z tego względu, obliczenia wykonywane przez procesor
opierają się na binarnym (dwójkowym) systemie liczbowym.
Bajt - (ang. byte) najmniejsza adresowalna jednostka pamięci
komputerowej, składająca się z bitów. W praktyce przyjmuje
się, że jeden bajt to 8 bitów, choć to nie wynika z powyższej
definicji. Aby uniknąć niejednoznaczności, jednostka
składająca się z ośmiu bitów zwana jest również oktetem.
Bywa też że "bajt" definiuje się jako 8 bitów, najmniejszą
adresowalną jednostkę pamięci nazywając znakiem.
System liczbowy - to inaczej zbiór reguł do jednolitego
zapisywania i nazywania liczb. Do zapisywania liczb zawsze
używa się pewnego skończonego zbioru znaków - zwanych
cyframi (np. arabskimi lub rzymskimi), które jednak można
zestawiać ze sobą na różne sposoby otrzymując nieskończoną
liczbę kombinacji. Najbardziej prymitywnym systemem
liczbowym, jaki sobie można wyobrazić, to jedynkowy system
liczbowy, w którym występuje tylko jeden znak (np. 1, albo
słowo "hau"). W systemie tym kolejne liczby są tworzone przez
proste powtarzanie tego znaku. Np. 3 w tym systemie jest
równe 111, a pięć 11111. Systemem takim posługują się np.
Pigmeje.
„Najpopularniejsze” systemy
liczbowych w Informatyce
Dwójkowy system liczbowy - (inaczej binarny) to pozycyjny
system liczbowy, w którym podstawą pozycji są kolejne potęgi
liczby 2. Do zapisu liczb potrzebne są więc tylko dwa znaki: 0 i
1. Powszechnie używany w informatyce. Jak w każdym
pozycyjnym systemie liczbowym, liczby zapisuje się tu jako
ciąg cyfr, z których każda jest mnożnikiem kolejnej potęgi
liczby stanowiącej podstawę systemu. Np. liczba zapisana w
dziesiętnym systemie liczbowym jako 10, w systemie
dwójkowym przybiera postać 1010, gdyż:
1x2^3 + 0x2^2 + 1x2^1 + 0x2^0 = 8+2 = 10.
Objaśnienie: zapis 2^3 oznacza 2 do potęgi 3.
Jest to od dawna stosowana forma zapisu potęg przez
programistów i informatyków – spróbuj zapisać (bez daszka)
potęge 2 do 5 na IRC`u albo w zwykłym mailu ;)
Szesnastkowy system liczbowy to pozycyjny system
liczbowy, w którym podstawą pozycji są kolejne potęgi
liczby 16. Często system szesnastkowy jest określany
nazwą Hex od słowa stworzonego przez firmę IBM
hexadecimal. Początkowo chciano używać łacińskiego sexa
zamiast hexa, ale niejednoznacznie się to kojarzyło. Do
zapisu liczb potrzebne jest szesnaście cyfr. Poza cyframi
dziesiętnymi od 0 do 9 używa się pierwszych sześciu liter
alfabetu łacińskiego: A, B, C, D, E, F. Jak w każdym
pozycyjnym systemie liczbowym, liczby zapisuje się tu jako
ciągi cyfr, z których każda jest mnożnikiem kolejnej potęgi
liczby stanowiącej podstawę systemu, np. liczba zapisana w
dziesiętnym systemie liczbowym jako 1000, w hex
przybiera postać 3E8, gdyż:
3x16^2 + 14x16^1 + 8x16^0 = 768 + 224 + 8 = 1000.
Hex jest powszechnie używany w informatyce, ponieważ
wartość pojedynczego bajtu można opisać używając tylko
dwóch cyfr szesnastkowych. W ten sposób można kolejne
bajty łatwo przedstawić w postaci ciągu liczb hex.
Jednocześnie zapis 4 bitów można łatwo przełożyć na jedną
cyfrę hex.
- Arytmetyka komputera -
operacje na bitach
Dzisiejsze komputery korzystają oczywiście z systemu
binarnego, po to właśnie był rozdział o systemach
liczbowych. Wszystko jest zapisane w postaci zer i jedynek,
aby zachować bezawaryjność (łatwiej zapanować nad
dwoma stanami niż dziesięcioma, szczególnie w
elektronice) i „prostotę” budowy podzespołów. Liczby
dziesiętne konwertowane są na dwójkowe. Nawet litery
zapisane są w postaci zer i jedynek (w jaki sposób? Wpisz w
google ASCII ;)). Skoro jesteśmy przy systemie binarnym
nieodzownym staje się poznanie kilku podstawowych pojęć
z zakresu logiki.
- Operacje na bitach -
AND – iloczyn logiczny
Koniunkcja to zdanie złożone mające postać p i q , gdzie p, q są zdaniami.
W rachunku zadań koniunkcję zapisuje się symbolicznie jako: .
Przez koniunkcję rozumie się też zdanie mające postać p(1) i ... i p(n).
Ciekawostka: w językach programowania C/C++ operatorem bitowym
iloczynu logicznego jest pojedynczy znak & (operatorem logicznym jest
&&)
0
0
0
0
1
0
1
0
0
1
1
1
Tabela prawdy AND
Przykłady:
1111 & 0000 = 0000
1010 & 1101 = 1000
1111 & 1001 = 1001
- Operacje na bitach –
OR – suma logiczna
Alternatywa - jedna z możliwości wyboru. Po podjęciu decyzji tylko
jedna z alternatyw staje się decyzją. Działanie to pozostaje w ścisłym
związku z dodawaniem zbiorów. Dlatego zdanie utworzone z innych
zdań przy użyciu alternatywy jest też nazywane sumą logiczną.
Alternatywa jest prawdziwa, jeżeli którekolwiek z jej zdań składowych
jest prawdziwe. W przeciwnym razie alternatywa zdań jest fałszywa.
Ciekawostka: w językach programowania C/C++ operatorem bitowym
sumy logicznej jest pojedynczy znak | (operatorem logicznym jest ||)
p
q
p v q
0
0
0
0
1
1
1
0
1
1
1
1
Tabela prawdy OR
Przykłady:
1111 | 0000 = 1111
1010 | 1101 = 1111
1111 | 1001 = 1111
- Operacje na bitach –
NOT – negacja
Negacja - jednoargumentowe działanie określone w zbiorze zdań, które
każdemu zdaniu p przyporządkowuje zdanie nieprawda, że p.
Negację zdania p uważa się za prawdziwą, gdy zdanie p jest
fałszywe, zaś za fałszywą, gdy zdanie p jest prawdziwe.
Ciekawostka: w językach programowania C/C++ operatorem negacji
jest znak !
p
!p
0
1
1
0
Tabela prawdy NOT
Przykłady:
!1111 = 0000
!1010 = 0101
!0000 = 1111
- Operacje na bitach –
XOR – alternatywa
wykluczająca
Alternatywa wykluczająca – (alternatywa rozłączna), jeden ze spójników
zdaniowych w logice. Alternatywa wykluczająca zdań p i q jest
prawdziwa tylko wtedy, gdy dokładnie jedno ze zdań p bądź q jest
prawdziwe.
Ciekawostka: w językach programowania C/C++ operatorem bitowym XOR
jest znak ^
p
q
p ^ q
0
0
0
0
1
1
1
0
1
1
1
0
Tabela prawdy XOR
Przykłady:
1111 ^ 0000 = 1111
1010 ^ 1101 = 0111
1111 ^ 1001 = 0110
1111 ^ 1111 = 0000
- Operacje na bitach –
SHL, SHR – przesunięcie bitowe
w lewo, w prawo
Są poleceniami procesora (dostępnymi z poziomu każdego
szanującego się języka programowania) nakazującymy
przesunięcie wszystkich bitów w lewo lub w prawo o zadaną
ilość miejsc. Przesunięcie o 1 bit w lewo oznacza pomnożenie
liczby razy 2, o 2 bity – razy 4 itd., przesunięcie w prawo
oznacza dzielenie (zgodnie z kolejnymi potęgami dwójki).
Operacja przesunięcia bitowego trwa bardzo krótko, procesor
dużo szybciej przesuwa o jeden bit w lewo niż mnoży razy dwa
(asm: mul). Przesunięcie o dowolną ilość bitów (nie tak
dowolną w 32bitowych maszynach maksymalne przesunięcie
to własnie 32 bity, związane to jest z rozmiarami
podstawowych rejestrów procesora) trwa z reguły jeden cykl
zegara, mnożenie trwa kilka- kilkanaście, zaś dzielenie aż
kilkadziesiąt!
Ciekawostka: w językach programowania C/C++ operatorem
przesunięcia bitowego w lewo jest << zaś w prawo >>
System zapisu U2,
czyli jak zapisać liczby ujemne
za pomocą samych zer i
jedynek
Kod uzupełnień do dwóch (w skrócie U2 lub ZU2) jest obecnie
najpopularniejszym sposobem zapisu liczb (najczęściej całkowitych)
na bitach. Jego popularność wynika z faktu, że operacje dodawania i
odejmowania są w nim wykonywane tak samo jak dla liczb
binarnych bez znaku. Z tego też powodu oszczędza się na kodach
rozkazów procesora. Nazwa kodu wzięła się ze sposobu obliczania
liczb przeciwnych. Dla jednobitowej liczby wartość przeciwną
obliczamy odejmując daną liczbę od 2 (uzupełniamy jej wartość do
dwóch). Analogicznie, dla liczb n-bitowych wartości przeciwne
uzyskujemy odejmując liczbę od dwukrotnej wagi najstarszego bitu:
2·2^(n–1) = 2n
W analogiczny sposób można stworzyć np. kod uzupełnień do
jedności. Zaletą tego kodu jest również istnienie tylko jednego zera.
Przedział kodowanych liczb nie będzie zatem symetryczny. W U2 na
n bitach da się zapisać liczby z zakresu:
Dla 8 bitów (bajtu) są to liczby od –128 do 127. Liczba –2n–1 nie
posiada swojego przeciwieństwa w n-bitowej reprezentacji kodu U2.