Bitit ja lukujärjestelmät¶
Osaamistavoitteet: Tämän materiaalin läpikäytyäsi tiedät miten tietokoneen muisti rakentuu biteistä, miten tietokone niitä käsittelee binäärilukuina ja osaat tehdä muunnoksia eri lukujärjestelmien välillä.
Aiemmin ohjelmoinnin kursseilla opimme mitkä ovat tietokoneen ja eri ohjelmointikielten tuntemat lukujärjestelmät: binääri-, kymmen- ja heksadesimaaliluvut. Näistä kymmenjärjestelmä on mukana vain meidän ihmisten, ts. ohjelmoijien ja käyttäjien, takia. Tietokone vaatimattomana laskimena ei tarvitse kuin binääriluvut ja niitä vastaavat bitit. Meidän tulee kuitenkin ymmärtää miten tietokone käsittelee bittejä.
.. mutta mutta, joskus eri lukujärjestelmien kanssa laskeminen saa kummallisia käänteitä (http://www.xkcd.com/571)
Selvitetäänpäs mitä uneton ystävämme oikein laskee ja mitä lampaille yllä tapahtuu..
Bitit tietokoneen muistissa¶
Bitti on (tietotekniikassa) tietoalkion pienin käsiteltävissä oleva osa. Bitillä on kaksi poissulkevaa (loogista) tilaa: 0 ja 1. Yksittäinen bitti siis kertoo aika vähän asioita, mutta kun bittejä asetetaan peräkkäin ja tämä bittijono käsitetään binäärilukuna, voidaankin esittää aika monta tietoalkion tilaa, ts. arvoa.
Edellisellä luennoilla opimme, että suorittimen arkkitehtuuri määrittelee tietoalkion koon bitteinä, joka on samalla myös yhden muistipaikan koko. Näin ollen koko keskusmuisti on "pätkitty" arkkitehtuurin mukaisesti muistipaikkoihin. Ja kun jokaisella muistipaikalla on osoite, voimme löytää muistista jokaisen yksittäisen tietoalkion ja sen yksittäisen bitin arvon.
Tarkastellaan esimerkinomaisesti samaa muistialuetta eri arkkitehtuureissa Kuvan muisteissa osoitelinjoja olisi 4 ja datalinjoja arkkitehtuurin mukaisesti.
Yhdestä 8 bitin binääriluvusta käytetään nimitystä tavu (engl. byte) ja 16/32-bitin luvusta taas nimitystä sana (engl. word) ja 32/64-bitin luvusta nimitystä englanniksi long word (.. pitkä kokonaisluku). Sanan määritelmä vaihtelee arkkitehtuurista toiseen ja se on tyypillisesti joko 16- tai 32-bittiä. C:n standardi ei myöskään sen kokoa määrittele, tästä lisää kohta..
Tietoalkion koko bitteinä kertoo meille sen lukualueen.
2 ^ 8 = 256 // 8-bittinen luku
2 ^ 16 = 65536 // 16-bittinen luku
2 ^ 32 = 4294967296 // ...
2 ^ 64 = 1.8446744*10^19 // ...
2 ^ .. // okei, eiköhän nämä riitä meille
Koska ensimmäinen lukujärjestelmän (ja binääriluvun, jossa kaikki bitit ovat nollia) numero on 0, voimme esittää n:llä bitillä vain 2^n-1 lukua. Eli 8-bittisellä muistipaikalla lukualue on
0..255. Pyrkimys säästeliäisyyteen¶
Miksi nämä tavut ja sanat kiinnostavat meitä.. eikö riittäisi, että käytetään aina vain 64-bittistä muistipaikkaa, kun kerran sinne mahtuu ISO lukualue?
Näin toki voimme tehdä arkkitehtuurin ja muistin määrän asettamissa rajoissa. Koska sulautetuissa järjestelmissä muistia on yleensä vähän tarjolla, joudutaan sen käyttöä optimoimaan esittelemällä ohjelmassa juuri sopivan kokoisia muuttujia. Ts. optimoidaan muuttujien määrää ja kokoa. Miksi käyttää pitkää kokonaislukua (joka vie 8 tavua muistia) jos tarvitsemme kyseisen arvon tallennukseen vain yhden tavun?
Tarkastellaan asiaa esimerkin kautta. Joissain mikrokontrollereissa (ATtiny-sarja) on muistia jopa alle yhden kilotavun (1024 tavua). Jos kilotavun muistissa yhden muistipaikan koko olisi 32 bittiä (4 tavua, a 8 bittiä), muistissa olisi
1024 / (32 / 8) = 256 yksittäistä muistipaikkaa. Jos taas muistipaikan koko on 16-bittiä 1024 / (16 / 8 ) = 512 , muistissa on 512 muistipaikkaa. Jälkimmäiseen muistiin siis mahtuu enemmän yksittäisiä muuttujia, mutta niiden koko on pienempi. Jonoon järjesty!¶
Muistipaikassa olevan binääriluvun ymmärtämisessä on vielä pari mutkaa matkassa, nimittäin bittijärjestys ja tavujärjestys.
Binääriluku muutetaan desimaaliluvuksi kakkosen potenssien kautta:
1011 = 1* 2^0 + 0*2^1 + 1*2^2 + 1*2^3 = 13Ok... mutta mistä tiedämme, että vasemmanreunimmaisin bitti on se, mistä aloitamme? Yhtä hyvin voisimme aloittaa kakkosen potenssit oikeasta reunasta. Jolloin tosin binääriluvun arvo desimaalilukuna on eri..
1011 = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 11.. hups.
Eli, meidän täytyisi tietää mikä bitti on pienin kakkosen potenssi eli vähiten merkitsevä (engl. least significant bit, LSB) ? Tai vastaavasti suurin kakkosen potenssi eli eniten merkitsevä (engl. most significant bit, MSB) ? No, jokaisessa suorittimen arkkitehtuurissa asia on päätetty meille valmiiksi.
Entäs, mistä tiedämme että missä järjestyksessä tavua pitempien tietoalkioiden tavut ovat (engl. big endian vs. little endian)? Vastaavasti tavujärjestys voi vaihdella..
Esimerkiksi 32-bittinen sana, joka koostuu neljästä tavusta?
tavu0,tavu1,tavu2,tavu3 tavu3,tavu2,tavu1,tavu0
Määritellään nyt siis kurssilla, että eniten merkitsevä bitti (MSB) on luvun vasemmanpuoleisin bitti ja eniten merkitsevä on vasemmanpuoleisin tavu.
(Nämä järjestykset mikroprosessorin ja muidenkin digitaalipiirien suunnittelijoiden on täytynyt vain päättää joskus historian hämärässä. Esimerkiksi, x86-64 -arkkitehtuuri on little endian, mutta Sun-työasemissa arkkitehtuuri on big endian. )
Negatiiviset kokonaisluvut¶
Aiemmin on esitetty tapa käyttää bittejä ja binäärilukuja positiivisten lukujen esittämiseen, mutta miten negatiiviset luvut esitetään? Seuraavassa kolme tapaa esittää negatiivisia kokonaislukuja binäärilukuina.
Suora (engl. signed magnitude). Voimme varata biteistä eniten merkitsevän merkkibitiksi, eli osoittamaan etumerkkiä (+ / -), jossa 0 tarkoittaa positiivista lukua ja 1 negatiivista. Huomataan, että tällöin luvulla nolla on kaksi esitystä, 4-bittisenä 0000 ja 1000. Tämä on huono juttu, koska joudutaan (koodissa) huomioimaan molemmat +0 ja -0.
Etumerkin käytössä on huomattava seuraavaa. Nyt 8-bittisen binääriluvun lukualue positiivisena lukuna siis on
0..255. Kun varaamme yhden bitin etumerkkibitiksi, jää meillä itse lukualueeseen 7-bittiä, jolloin positiivinen lukualue tippuu 0..127. Tilalle saammekin etumerkin avulla lisäksi negatiiviset luvut, joiden lukualueeksi muodostuu -128..-1. Tällöin lukualue ikäänkuin "siirtyy" negatiiviseen suuntaan! 1-komplementti Negatiivinen luku saadaan ottamalla positiivisesta negaatio. Esimerkiksi kun luku 3 on 0011 binäärilukuna, niin -3 olisi 1100. Tässäkin esitystavassa on nollalle kaksi esitystä, 0000 ja 1111.
2-komplementti¶
Tämä esitystapa on kaikkien kiinnostavin ja yleisesti tietotekniikassa käytetty. Joten uhrataan sille hieman enemmän aikaa.
Eniten merkitsevä bitti on jälleen merkkibitti: 0 positiivinen ja 1 negatiivinen.
Positiivisella puolella 2-komplementtiluvuissa ei ole mitään erikoista.
Mutta, sitten negatiivisen kokonaisluvun muodostamisessa on oma kommervenkkinsä:
- Positiivisesta binääriluvusta otetaan negaatio: nollat ykkösiksi ja päinvastoin
- Lisätään negaatioon 1.
Esimerkki 4-bittisillä luvuilla.
Luku 1 0001 Luku 2 0010 Luku 8 1000
Negaatio 1110 Negaatio 1101 Negaatio 0111
+1 +1 +1
---- ---- ----
1111 = -1 1110 = -2 1000 = -8
(Numeron 8 tapauksessa siis merkkibitti määrittää arvon alunperinkin negatiiviseksi!)
Takaisin negatiivisesta positiiviseksi mennään samalla menetelmällä.
Luku -1 1111 Luku -2 1110 Luku -8 1000
Negaatio 0000 Negaatio 0001 Negaatio 0111
+1 +1 +1
---- ---- ----
0001 = 1 0010 = 2 1000 = 8
Kuvassa 4-bittiset luvut ilman etumerkkiä ja 2-komplementtiesityksenä.
2-komplementtiluvun muunnos kymmenjärjestelmään ilman laskinta yksinkertaisella yhteenlaskulla. Idea on, että ajatellaan eniten merkitsevän bitin (MSB) lukuarvo (painoarvo) negatiivisena, kun taas muut pysyvät positiivisina. Näin saada muunnettua 2-komplementtiluku kymmenjärjestelmään helposti.
Esimerkki. 8-bittiset luvut 99 (01100011) ja -99 (10011101).
99 = 64 + 32 + 2 + 1 -99 = -128 + 16 + 8 + 4 +1
Lisäksi, 2-komplementtiesitys on siitä kätevä, että 2-komplementtilukujen yhteenlasku toimii samoin, oli operandi positiivinen tai negatiivinen. Tämä helpottaa tietokoneen digitaalilogiikan suunnittelua.
Esimerkki yhteenlaskusta.
Laske 2-komplementtiluvuilla: 2-3 = 2+(-3) = ?
Luku +2 0010
Luku -3 1101
+ 1111
----
-1
(Suorassa menetelmässä ja 1-komplementti-esityksessä tämä ei aina toimi, kokeile löytää esimerkki jossa yhteenlasku ei toimi!)
Muunna 6-bttinen 2-komplementtiluku 101011 kymmenjärjestelmään yhteenlasku-menetelmällä.
Anna palautetta
Koitko tämän tehtävän hyödylliseksi oppimisen kannalta?
Kommentteja tehtävästä?
Heksadesimaaliluvut¶
Toinen C-kielisessä (ja konekielisessä) sulautettujen ohjelmoinnissa usein käytetty kantalukujärjestelmä on 16. Tällöin puhutaan heksadesimaalinumeroista, jotka käsittävät numerot 0-9 ja 10-15, merkitään kirjaimilla A-F.
Huomataan, että jokainen heksadesimaalinumero voidaan esittää 4:llä bitillä. Tämä onkin se syy miksi heksadesimaalilukuja käytetään, kun nyt voidaan yksi tavu esittää kahdella heksadesimaalinumerolla vs. hankalasti biteiksi tulkittava kymmenjärjestelmän kokonaisluku vs. silmille epämukava binääriluku.
Muunnos heksalukujen ja binäärilukujen välillä on helppo. Tiedäme, että jokaista heksanumeroa siis vastaa 4 bittiä, eli tarvitsee vain muuttaa heksanumerot yksi kerrallaan 4-bittisiksi binääriluvuiksi.
Esimerkki. Muunna heksadesimaaliluku 173A4C binääriluvuksi?
1 7 3 A 4 C 0001 0111 0011 1010 0010 1100
Monissa ohjelmointikielissä heksaluvut esitetään käyttäen etuliitettä
0x. Esimerkiksi.0x0123456789ABCDEF 0xA 0x1000 0x001 0xBEEF 0xC0DE 0xBA5EBA11
Lopuksi¶
Ok, jänniä juttuja.. mutta entäs uneton ystävämme ja ne seonneet lampaat?
Nythän meille on selvää, kun vilkaisemme sarjakuvaa uudestaan, että ystävämme laskee lampaita 16-bittisillä 2-komplementtiluvuilla. Kävi vain niin ikävästi unta odotellessa, että positiivinen lukualue loppui kesken ja luvut pyörähti negatiiviselle puolelle merkkibitin muutoksen myötä..
0000000000000001 = 1 +1 0000000000000010 = 2 +1 ... 0111111111111110 = 32766 +1 0111111111111111 = 32767 +1 1000000000000000 = -32768 +1 1000000000000001 = -32767 +1 1000000000000010 = -32766 ...
TKJ-asiaa¶
Tästä eteenpäin materiaali sivun loppuun asti on TKJ-asiaa ja muille varsin hyvä tietää! Tämä asia käydään läpi TKJ-osuudessa, mutta JTKJ-opiskelijat voivat toki siihen perehtyä.
Liukulukuesitys¶
Katsotaan ensin miten binääriluvuille esitetään desimaalit? No, ihan vastaavasti desimaalipilkulla kuten kymmenjärjestelmässäkin. Kuvasta huomaamme, että desimaalipisteen vasemmalla puolella olevat kakkosen potenssit ovat positiivisia ja oikealla puolen negatiivisia.
Esimerkki.
Binääriluku 10.101 = 1*2^1 + 0*2^0 + 1*2^-1 + 0*2^-2 + 1*2^-3 = 2 + 0 + 1/2 + 0 + 1/8 = 2.625 Binääriluku 101.01 = 4 + 0 + 1 + 0 + 1/4 = 5.25 Binääriluku 1010.1 = 8 + 2 + 1/2 = 10.5 Binääriluku 0.111111 on desimaalilukuna 0 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 = 63/64 = 0.984375
Johtuen rajallisesta määrästä bittejä, pääsemme binäärisen desimaaliluvun esityksessä vain tiettyyn tarkkuuteen. Pienin mahdollinen arvo on LSB:tä vastaavan bitin arvo. Tästä syystä luku on aina arvio desimaaliluvusta.
Esimerkki.
Oletetaan 8-bittinen luku, josta on kokonaislukuosa 4 bittiä ja desimaaliosa myös 4 bittiä. Tällöin pienin luku, minkä voimme esittää on 00000001 = 2^-4 = 1/16 = 0.0625
Mutta.. miten esität ylläolevalla tavalla desimaaliluvun, jota ei voi esittää 2:n kokonaislukupotensseilla (2^-n) valitussa tarkkuudessa.. esimerkiksi 1/3? No näissä tapauksissa desimaaliluku on yhtä päättymätön kuin peruskoulun matematiikassakin. Eli bittiesitykseen tulee toistoa, jolloin
1/3 = 0.01010101010101... Jos pisteen paikka on määritelty, eli desimaaleja pisteen jälkeen on aina sovittu määrä, puhutaan fixed-point-aritmetiikasta (suom. kiinteän pilkun..). Nyt taas floating point (liukuva pilkku) -esitys tarkoittaa sitä, että desimaalipisteen paikka "liukuu"!
Jos tietokoneessa ei ole erillistä "matikkapiiriä" (FPU) liukulukujen käsittelyyn osana CPU:ta, kuten usein sulautetuissa järjestelmissä, voidaan hardiksessa käyttää fixed-point -esitystä. Tai rinnalle voidaan tuoda erillinen FPU-piiri, kuten esimerkiksi 80-luvun mikroprosessoreissa.
Pyöristys haluttuun tarkkuuteen¶
Samoin kuin kymmenjärjestelmän desimaalilukuja, binäärilukuja voidaan pyöristää. Menetelmä on seuraava.
Pyöristetään binääriluku lähimpään 1/4:n eli kaksi bittiä desimaaliosaa
.xx. Lähdetään purkamaan bittejä lopusta alkaen ja pidetään binäärilukua 100 "puolivälinä". (Kymmenjärjestelmässä pyöristyksessä vastaava puoliväli on luku 5).- Jos kahden viimeisen bitin edellä oleva bitti on 0, tällöin pyöristetään alaspäin.
- Jos kahden viimeisen bitin edellä oleva bitti on 1, otetaan se mukaan pyöristykseen, nyt
- Jos kolme bittiä ovat < 100, pyöristetään alaspäin
- Jos kolme bittiä ovat > 100, pyöristetään ylöspäin
- Jos kolme bittiä ovat = 100, huomioidaan taas edellä oleva bitti
- Jos neljäs bitti on 1, pyöristetään ylöspäin
- Jos neljäs bitti on 0, pyöristetään alaspäin
Esimerkkejä.
10.00011 // nyt kaksi viimeistä bittiä ovat 11 ja edellä 0, joten pyöristyy alaspäin, eli 10.00 (=2) 10.00110 // pyöristyy ylöspäin, eli 10.01 (=2 1/4) 10.11100 // pyöristyy ylöspäin, eli 11.00 (=3) 10.10100 // pyöristyy alaspäin, eli 10.10 (=2 1/2)
IEEE 754 liukulukustandardi¶
Liukulukuja, ts. desimaalilukuja, on tietokoneissa kahta tyyppiä: yksinkertaisen ja kaksinkertaisen tarkkuuden liukuluvut. Liukulukujen esitys tietokoneen muistissa perustuu IEEE 754-standardiin, jonka esityksen käymme läpi (pääpiirteissään) seuraavassa.
Liukulukuun kuuluu siis kolme osaa
- Etumerkki s, jossa s=0 on positiivinen ja s=1 on negatiivinen.
- Murto-osan (engl. fractional) esitys
M = 1 + xxx = 1.xxx, jossa xxx vastaa murto-osaa.- Murto-osa etsitään binääriluvusta siirtämällä desimaalipistettä (molempiin suuntiin). Kts. esimerkki alla.
- Eksponenttiosa E:n esitys
E = exponent - biasbias = (2^(n-1))-1, jossa n on E:n bittien määrä- Yksinkertaisen tarkkuuden liukuluvuissa bias = 127 ja kaksinkertaisen tarkkuuden liukuluvuissa bias = 1023.
Liukukujen kaksi tyyppiä float (yksinkertaisen tarkkuuden, single precision, 32 bittiä) ja double (kaksinkertaisen tarkkuuden, double precision, 64 bittiä esitetään seuraavasti.
Esimerkki. Muunnetaan desimaaliluku 12345.0 float-tyypin liukuluvuksi.
Luku 12345.0 on binäärilukuna 11000000111001 * 2^0 1. Etsitään M siirtämällä desimaalipistettä vasemmalle: 11000000111001 * 2^0 1100000011100.1 * 2^1 110000001110.01 * 2^2 ... 1.1000000111001 * 2^13 2. Lasketaan murto-osa: Pudotetaan luvun edestä kokonaisosa pois ja saadaan 1000000111001, johon lisätään 10 0-bittiä, koska sen pituus on 23 bittiä, jolloin murto-osa frac = 10000001110010000000000 3. Lasketaan exponentti: Nyt E=13 ja bias=127, eli exponent = E + bias = 13 + 127 = 140 eli 10001100 4. Lopuksi etumerkki s=0, koska kyseessä on positiivinen luku.
Ylläolevan esimerkin tulos on siis:
Yllämainittu liukuluvun esitys on yleinen, esimerkkinä allaoleva pieni ja söötti (jap. kawaii) esitys 8:lla bitillä. Tässä bias = 7.
Erikoistapauksia¶
- Nolla: exp = 000..0 ja frac = 000..0
- Ääretön: exp = 111..1 ja frac = 000..0
- NaN (not a number): exp = 111..1 ja frac erisuuri kuin 000..0
- NaN esittää tapaukset joita ei voi laskea, kuten sqrt(-1), ääretön - ääretön, jne..
Lopuksi¶
Liukuluvun esitys on käyty tarkemmin läpi oppikirjassa. Kurssilla riittää, että osaamme muuntaa liukulukuja esitysmuodosta toiseen.
Anna palautetta
Kommentteja materiaalista?