50. Reprezentacja liczb w pozycyjnym systemie liczbowym. Systemy
50. Reprezentacja liczb w pozycyjnym systemie liczbowym. Systemy
50. Reprezentacja liczb w pozycyjnym systemie liczbowym. Systemy
dwójkowy i szesnastkowy oraz ich zastosowania.
dwójkowy i szesnastkowy oraz ich zastosowania.
System dwójkowy
System dwójkowy (czyli binarny) to pozycyjny system liczbowy, którego podstawą są kolejne potęgi
System dwójkowy (czyli binarny) to pozycyjny system liczbowy, którego podstawą są kolejne potęgi
System dwójkowy (czyli binarny) to pozycyjny system liczbowy, którego podstawą są kolejne potęgi
dwójki. Został spopularyzowany przez Wilhelma Gotfrieda Leibniza w wieku XVII.
dwójki. Został spopularyzowany przez Wilhelma Gotfrieda Leibniza w wieku XVII. Liczby naturalne
przedstawiane są jako suma potęg bazy (2) z odpowiednimi wagami reprezentowanymi przez cyfry
przedstawiane są jako suma potęg bazy (2) z odpowiednimi wagami reprezentowanymi przez cyfry 
w tym przypadku tylko dwie: 0 i 1. Każda liczba naturalna dodatnia ma zatem reprezentację postaci:
w tym przypadku tylko dwie: 0 i 1. Każda liczba naturalna dodatnia ma zatem reprezentację postaci:
w tym przypadku tylko dwie: 0 i 1. Każda liczba naturalna dodatnia ma zatem reprezentację postaci:
, gdzie
Powszechnie używany w elektronice cyfrowej, gdzie minimalizacja liczby stanów (do dwóch) pozwala
elektronice cyfrowej, gdzie minimalizacja liczby stanów (do dwóch) pozwala
na prostą implementację sprzętową odpowiadającą zazwyczaj stanom wyłączony i włączony oraz
mentację sprzętową odpowiadającą zazwyczaj stanom wyłączony
zminimalizowanie przekłamań danych. Co za tym idzie, przyjął się też w informatyce.
zminimalizowanie przekłamań danych. Co za tym idzie, przyjął się też w informatyce
Jak w każdym pozycyjnym systemie liczbowym, liczby zapisuje się tu jako cyfr, z których każda
Jak w każdym pozycyjnym systemie liczbowym, liczby zapisuje się tu jako ciągi cyfr
jest mnożnikiem kolejnej potęgi podstawy systemu.
jest mnożnikiem kolejnej potęgi podstawy systemu.
Np. liczba zapisana w dziesiętnym systemie liczbowym , w systemie dwójkowym przybiera
dziesiętnym systemie liczbowym jako 10, w systemie dwójkowym przybiera
postać 1010, gdyż:
Liczby w systemach niedziesiętnych oznacza się czasami indeksem dolnym zapisanym w systemie
Liczby w systemach niedziesiętnych oznacza się czasami indeksem dolnym zapisanym w systemie
dziesiętnym, a oznaczającym podstawę danego systemu. W celu podkreślenia, że liczba jest
dziesiętnym, a oznaczającym podstawę danego systemu. W celu podkreślenia, że liczba jest
dziesiętnym, a oznaczającym podstawę danego systemu. W celu podkreślenia, że liczba jest
dziesiętna można również napisać obok niej indeks. Np.
dziesiętna można również napisać obok niej indeks. Np.
W systemie dwójkowym można przedstawiać również . Na przykład liczby
W systemie dwójkowym można przedstawiać również liczby rzeczywiste. Na przykład
dziesiętne o podstawie 2 można zapisać j
o podstawie 2 można zapisać jako:
Ułamek zwykły zapisujemy:
Jak w prosty sposób znajdować reprezentacje dwójkowe liczb naturalnych? Są dwie proste metody.
Jak w prosty sposób znajdować reprezentacje dwójkowe liczb naturalnych? Są dwie proste metody.
Jak w prosty sposób znajdować reprezentacje dwójkowe liczb naturalnych? Są dwie proste metody.
Załóżmy, że chodzi nam o przedstawienie dwójkowe liczby
Załóżmy, że chodzi nam o przedstawienie dwójkowe liczby .
·ð Znajdujemy najwiÄ™kszÄ… liczbÄ™ jedynkÄ™, odejmujemy
Znajdujemy największą liczbę nieprzekraczającą . Piszemy jedynkę, odejmujemy
od wartość , a następnie kolejno dla wszystkich mniejszych potęg dwójki sprawdzamy, czy
, a następnie kolejno dla wszystkich mniejszych potęg dwójki sprawdzamy, czy
, a następnie kolejno dla wszystkich mniejszych potęg dwójki sprawdzamy, czy
mieszczą się one w tym, co zostało z . Jeśli dana potęga dwójki nie mieści się, to dopisujemy
mieszczą się one w tym, co zostało z . Jeśli dana potęga dwójki nie mieści się, to dopisujemy
zero, a jeśli mieści się, to dopisujemy jedynkę i odejmujemy tę wartość od tego, co zostało z .
zero, a jeśli mieści się, to dopisujemy jedynkę i odejmujemy tę wartość od tego, co zostało z
Przykładowo dla
zostało z potega dwójki wypisano
zostało z
13 8 1
5 4 11
1 2 110
1 1 1101
0
·ð Zaczynamy od liczby , a nastÄ™pnie dopóki m jest wiÄ™ksze od zera dzielimy przez 2, zapisujÄ…c
, a następnie dopóki m jest większe od zera dzielimy
kolejno otrzymywane reszty. Ciąg reszt odczytany od końca da nam poszukiwaną reprezentację.
otrzymywane reszty. Ciąg reszt odczytany od końca da nam poszukiwaną reprezentację.
otrzymywane reszty. Ciąg reszt odczytany od końca da nam poszukiwaną reprezentację.
Przykładowo dla tego samego
Przykładowo dla tego samego
zostało z po dzieleniu przez 2 reszta z dzielenia przez 2
po dzieleniu przez 2 przez 2
13 1
6 0
3 1
1 1
0
Ciąg reszt z ostatniej kolumny czytany od dołu do góry , czyli reprezentację
Ciąg reszt z ostatniej kolumny czytany od dołu do góry daje właśnie , czyli reprezentację
dwójkową .
W odwrotną stronę trudno podać lepszą metodę niż proste dodanie kolejnych potęg dwójki, zatem
W odwrotną stronę trudno podać lepszą metodę niż proste dodanie kolejnych potęg dwójki, zatem
W odwrotną stronę trudno podać lepszą metodę niż proste dodanie kolejnych potęg dwójki, zatem
np. 10101, to
System szesnastkowy
System szesnastkowy to system różny od tego, którego używamy na co dzień. Różni się o tyle, że
System szesnastkowy to system różny od tego, którego używamy na co dzień. Różni się o tyle, że
bazuje na liczbie 16, a więc potrzebuje 16 znaków za pomocą, których można zapisać dowolną liczbę.
bazuje na liczbie 16, a więc potrzebuje 16 znaków za pomocą, których można zapisać dowolną liczbę.
bazuje na liczbie 16, a więc potrzebuje 16 znaków za pomocą, których można zapisać dowolną liczbę.
Szesnastkowy system liczbowy jest właściwy komputerom, ponieważ pozwala na zapis większych
Szesnastkowy system liczbowy jest właściwy komputerom, ponieważ pozwala na zapis większych
Szesnastkowy system liczbowy jest właściwy komputerom, ponieważ pozwala na zapis większych
liczb w mniejszych przestrzeniach pamięci.
liczb w mniejszych przestrzeniach pamięci.
W systemie szesnastkowym wyróżniamy 16 cyfr:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
Cyfry 0-9 mają te same wartości co w systemie dziesiętnym, natomiast litery odpowiadają
następującym wartościom: A = 10, B = 11, C = 12, D = 13, E = 14 oraz F = 15.
Zapis liczby całkowitej w systemie heksadecymalnym ma postać:
ai-1ai-2 ... a2 a1 a0 = ai-1 · 16i-1 + ai-2 · 16i-2 + ... + a2 · 162 + a1 · 161 + a0 · 160
Konwersji (zamiany) liczby w systemie dziesiętnym na system heksadecymalny można dokonać
poprzez wielokrotne dzielenie przez 16 i spisywanie reszt z dzielenia. Przy ilorazie równym zero
należy spisać ostatnią resztę i odczytać ciąg utworzony z reszt zaczynając od ostatniej, kończąc na
pierwszej. Utworzony w ten sposób ciąg jest reprezentacją szesnastkową liczby dziesiętnej.
Np. liczba zapisana w dziesiętnym systemie liczbowym jako 1000, w systemie szesnastkowym
przybiera postać 3E8, gdyż:
Szesnastkowy system liczbowy stosuje siÄ™ w informatyce, w przypadku programowania
niskopoziomowego, sterowania hardwarem, wyboru adresów.
Adresy IP np. w wersji 6 sÄ… podawane w pozycyjnym systemie szesnastkowym np.:
3ffe:0902:0012:0000:0000:0000:0000:0000/48.
W języku składu stron internetowych i/lub programach edycji stron WWW system szesnastkowy
stosowany jest do oznaczania kolorów.
51. Podstawowe prawa algebry Boole'a.
Algebra Boole'a  struktura algebraiczna stosowana w matematyce, informatyce teoretycznej oraz
elektronice cyfrowej. Jej nazwa pochodzi od nazwiska angielskiego matematyka, filozofa i logika
George'a Boole'a.
Typowymi przykładami algebr Boole'a są: rodzina wszystkich podzbiorów ustalonego zbioru wraz
działaniami na zbiorach jako operacjami algebry oraz dwuelementowa algebra wartości logicznych
{0, 1} z działaniami koniunkcji, alternatywy i negacji.
Algebra Boole'a to struktura algebraiczna , w której i sÄ… dziaÅ‚aniami dwuargumentowymi, Ü jest
operacją jednoargumentową, a 0 i 1 są wyróżnionymi różnymi elementami zbioru , spełniająca
następujące warunki dla wszystkich :
łączność
rozdzielność
przemienność
absorpcja
pochłanianie
Algebra Boole'a jest to struktura matematyczna złożona z trzech działań binarnych:
Algebra Boole'a jest to struktura matematyczna złożona z trzech działań binarnych:
Algebra Boole'a jest to struktura matematyczna złożona z trzech działań binarnych:
- (" (lub, or, alternatywa)
- '" (i, and, koniunkcja)
- ~ (nie, not, przeczenie logiczne, negacja
, negacja)
oraz wyróżnionych elementów 0 (fałsz), 1 (prawda)
ionych elementów 0 (fałsz), 1 (prawda).
Negacja
To zdanie mające postać nieprawda, że p rachunku zdań negacja zapisywana
nieprawda, że p, gdzie p jest zdaniem. W rachunku zdań
jest jako: (lub ). Negację można zdefiniować ściślej jako jednoargumentowe działanie
). Negację można zdefiniować ściślej jako jednoargumentowe działanie
określone w zbiorze zdań, które każdemu zdaniu p przyporządkowuje zdanie nieprawda, że p.
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 jest fałszywe, zaś za fałszywą, gdy
uważa się za prawdziwą, gdy zdanie p jest fałszywe, zaś za fałszywą, gdy
zdanie p jest prawdziwe.
Symbol negacji jako bramki logicznej
bramki logicznej:
p Ź p
0 1
1 0
Alternatywa lub suma logiczna
suma logiczna
To w logice matematycznej:
1. Działanie dwuargumentowe rze zdań bądz
w zbiorze funkcji
Działanie dwuargumentowe określone w dowolnym zbiorze zdań bądz
w zbiorze funkcji
zdaniowych, które zdaniom (funkcjom zdaniowym) rzypisuje zdanie (funkcję zdaniową)
zdaniowych, które zdaniom (funkcjom zdaniowym) p i q przypisuje zdanie (funkcję zdaniową)
prawdziwe wtedy i tylko wtedy gdy prawdziwe jest przynajmniej jedno ze zdań (funkcji)
prawdziwe wtedy i tylko wtedy gdy prawdziwe jest przynajmniej jedno ze zdań (funkcji)
prawdziwe wtedy i tylko wtedy gdy prawdziwe jest przynajmniej jedno ze zdań (funkcji) p i q
2. Dwuargumentowy spójnik zdaniowy, oznaczany o znaczeniu odpowiadającemu
Dwuargumentowy spójnik zdaniowy, oznaczany o znaczeniu odpowiadającemu
wyżej zdefiniowanemu działaniu określonemu w zbiorze . Od poprzedniej
yżej zdefiniowanemu działaniu określonemu w zbiorze . Od poprzedniej
definicji różni się tym, że jest definiowany na poziomie syntaktycznym, dzięki czemu unika
definicji różni się tym, że jest definiowany na poziomie syntaktycznym, dzięki czemu unika
definicji różni się tym, że jest definiowany na poziomie syntaktycznym, dzięki czemu unika
się określania jego dziedziny.
się określania jego dziedziny.
3. Zdanie logiczne postaci , gdzie p i q sÄ… zdaniami.
Alternatywa pozostaje w ścisłym związku z algebra zbiorów). Dlatego
Alternatywa pozostaje w ścisłym związku z dodawaniem zbiorów (patrz algebra zbiorów
zdanie utworzone z innych zdań przy użyciu alternatywy jest też nazywane sumą logiczną.
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
, jeżeli którekolwiek z jej zdań składowych jest prawdziwe. W przeciwnym
, jeżeli którekolwiek z jej zdań składowych jest prawdziwe. W przeciwnym
razie alternatywa zdań jest fałszywa
fałszywa.
Symbol alternatywy jako bramki logicznej
bramki logicznej:
p q p
p (" q
0 0 0
0 1 1
1 0 1
1 1 1
Koniunkcja
To zdanie złożone mające postać koniunkcję zapisuje
złożone mające postać p i q , gdzie p, q są zdaniami. W rachunku zdań koniunkcję zapisuje
się symbolicznie jako: . Przez koniunkcję rozumie się też zdanie mające postać
. Przez koniunkcję rozumie się też zdanie mające postać
. Przez koniunkcję rozumie się też zdanie mające postać p(1) i ... i p(n).
Koniunkcję można zdefiniować precyzyjniej jako dwuargumentowe działanie określone w zbiorze
Koniunkcję można zdefiniować precyzyjniej jako dwuargumentowe działanie określone w zbiorze
Koniunkcję można zdefiniować precyzyjniej jako dwuargumentowe działanie określone w zbiorze
zdań, które zdaniom p, q przyporządkowuje zdanie
przyporzÄ…dkowuje zdanie p i .
Działanie to pozostaje w ścisłym związku z działaniem algebra zbiorów).
Działanie to pozostaje w ścisłym związku z działaniem przekroju zbiorów (patrz algebra zbiorów
Dlatego zdanie utworzone z innych zdań za pomocą koniunkcji jest też nazywane
Dlatego zdanie utworzone z innych zdań za pomocą koniunkcji jest też nazywane
Dlatego zdanie utworzone z innych zdań za pomocą koniunkcji jest też nazywane iloczynem
logicznym. Koniunkcję zdań uznaje się za prawdziwą wtedy i tylko wtedy, gdy oba zdania
. Koniunkcję zdań uznaje się za prawdziwą wtedy i tylko wtedy, gdy oba zdania
. Koniunkcję zdań uznaje się za prawdziwą wtedy i tylko wtedy, gdy oba zdania p, q są
prawdziwe.
Symbol koniunkcji jako bramki logicznej
bramki logicznej:
0 0 0
0 1 0
1 0 0
1 1 1
52. Reprezentacja w pamięci danych typów prostych i złożonych.
52. Reprezentacja w pamięci danych typów prostych i złożonych.
52. Reprezentacja w pamięci danych typów prostych i złożonych.
Typem prostym nazywamy wartość, która nie może być rozłożona na prostsze wartości. Typ prosty
nazywamy wartość, która nie może być rozłożona na prostsze wartości.
jest to typ, który przyjmuje wartości proste
jest to typ, który przyjmuje wartości proste.
Wartością złożoną nazywamy wartość, która może być rozłożona na prostsze wartości. Typ złożony
jest to typ, który przyjmuje wartości złożone.
Dane w pamięci komputera czy też w plikach zapisane są w postaci ciągu tzw. bajtów. Każdy bajt
składa się z ośmiu cyfr systemu dwójkowego (0 lub 1), zwanych bitami. Pojedynczy bajt może
przyjmować jeden z 28 = 256 stanów. Powstaje konieczność zakodowania liczb w postaci ciągu
bajtów, tak aby komputery mogły je przetwarzać. Można to zrobić na wiele sposobów, jednak w
praktyce używanych jest kilka standardów:
Liczby naturalne
Typ obejmujący przedział liczb naturalnych z zerem zwany jest w informatyce liczbami bez
znaku (ang. unsigned integers).
Liczby naturalne z przedziału 0-255 można po prostu zakodować jako wartość jednego bajta.
Na dwóch bajtach można już zapisać liczby naturalne z przedziału 0-65535 (mamy do
dyspozycji 65536 = 2562 stanów). Każdą taką liczbę można zapisać w postaci x = 256h + l,
gdzie horaz l to wartości tzw. starszego bajta i młodszego bajta, z przedziału od 0 do 255 każda.
Wartości te można zapisać w pamięci na dwa sposoby: albo pierwszy jest starszy bajt, a drugi
młodszy (tzw. notacja big endian), albo odwrotnie (little endian).
Na czterech bajtach można zapisać liczby z przedziału 0  4 294 967 295. Analogicznie jak poprzednio,
przedstawienie danej liczby w systemie 256-kowym pozycyjnym jakox = 2563a3 + 2562a2 +
256a1 + a0 uzyskuje się cztery bajty a3,a2,a1,a0. Kolejność ich zapisu w pamięci, tak jak poprzednio,
zależy od procesora  w przypadku little endian od bajta a0 do a3, w przypadku big endian 
odwrotnie.
Do niektórych zastosowań konieczne są jeszcze większe liczby naturalne, np. zapisywane na 8 bajtach
(w rodzinie C oznaczane unsigned _int64 lub unsigned long long int).
Liczby całkowite
Typ obejmujący przedział liczb całkowitych zwany jest w informatyce liczbami ze
znakiem (ang. signed integers).
Stosuje się tzw. kod uzupełnień do dwóch (U2). Liczba x, która ma zostać zapisana w postaci n bajtów
jest przekształcana w następujący sposób:
Następnie liczba x' jest zapisywana jako liczba naturalna. W ten sposób na jednym bajcie można
jest zapisywana jako liczba naturalna. W ten sposób na jednym bajcie można
jest zapisywana jako liczba naturalna. W ten sposób na jednym bajcie można
zapisywać liczby z przedziału od - 128 , i ogólnie nan bajtach
- 128 do 127, na dwóch od - 32768 do 32767, i ogólnie na
liczby od - 28n - 1 do 28n - 1 - 1 włącznie.
włącznie.
Liczby rzeczywiste
Liczby rzeczywiste mogą być zapisywane jako:
Liczby rzeczywiste mogą być zapisywane jako:
żð liczby staÅ‚oprzecinkowe, kiedy liczba mnożona jest przez pewnÄ… ustalonÄ… z góry staÅ‚Ä…, po
, kiedy liczba mnożona jest przez pewną ustaloną z góry stałą, po
, kiedy liczba mnożona jest przez pewną ustaloną z góry stałą, po
czym zaokrąglana do najbliższej liczby całkowitej i jako taka zapisywana;
do najbliższej liczby całkowitej i jako taka zapisywana;
żð liczby zmiennoprzecinkowe, gdy staÅ‚a dobierana jest w zależnoÅ›ci od kodowanej liczby, co czyni
, gdy stała dobierana jest w zależności od kodowanej liczby, co czyni
, gdy stała dobierana jest w zależności od kodowanej liczby, co czyni
tÄ™ metodÄ™ uniwersalniejszÄ….
Powszechnie stosuje siÄ™ zmiennoprzecinkowy zapis liczby rzeczywistej w standardzie
Powszechnie stosuje siÄ™ zmiennoprzecinkowy zapis liczby rzeczywistej w standardzie
Powszechnie stosuje siÄ™ zmiennoprzecinkowy zapis liczby rzeczywistej w standardzie IEEE 754.
Przybliżenie liczby rzeczywistej jest zapisywane w postaci ,
Przybliżenie liczby rzeczywistej jest zapisywane w postaci
gdzie jest nazywany  mantysÄ….
jest nazywany znakiem, w  wykładnikiem, a
Zero, które można by zakodować na wiele sposobów jest kodowane jako w = 0,m = 0.
Zero, które można by zakodować na wiele sposobów jest kodowane jako s = + 1,w
Znak jest zapisywany jako jeden bit, równy 0 dla . Wykładnik jest zapisywany jak
Znak jest zapisywany jako jeden bit, równy 0 dla s = + 1 i 1 dla s = - 1. Wykładnik jest zapisywany jak
każda inna liczba całkowita w kodzie uzupełnień do dwóch. Mantysa jest mnożona przez
każda inna liczba całkowita w kodzie uzupełnień do dwóch. Mantysa jest mnożona przez
każda inna liczba całkowita w kodzie uzupełnień do dwóch. Mantysa jest mnożona przez 2f, gdzie f to
liczba bitów przeznaczona na nią i zapisywana jako liczba naturalna.
liczba bitów przeznaczona na nią i zapisywana jako liczba naturalna.
Całość zajmuje kolejnych 4, 8 albo 16 bajtów (w zależności od wymaganej precyzji). Ich kolejność
Całość zajmuje kolejnych 4, 8 albo 16 bajtów (w zależności od wymaganej precyzji). Ich kolejność
umieszczenia w pamięci jest zależna od procesora, identycznie jak w przypadku liczb naturalnych i
umieszczenia w pamięci jest zależna od procesora, identycznie jak w przypadku liczb naturalnych i
umieszczenia w pamięci jest zależna od procesora, identycznie jak w przypadku liczb naturalnych i
całkowitych.
Znaki
Typ znakowy  jeden z podstawowych językach programowania, mający na
jeden z podstawowych typów danych w wielu językach programowania
celu przechowywanie pojedynczego
pojedynczego znaku tekstu.
W językach C i C++ typ ten jest po prostu (może być ona ze znakiem, w
typ ten jest po prostu jednobajtową liczbą całkowitą (może być ona ze
przypadku signed char; lub bez znaku, dla ; w przypadku nie podania
; lub bez znaku, dla unsigned char; w przypadku nie podania
kwalifikatora signed/unsigned rodzaj liczby zależy od implementacji)
rodzaj liczby zależy od implementacji)
Typ string jest często reprezentowany w postaci tablicy char
ntowany w postaci tablicy char ów.