C++-ohjelmointi

Luku 8: Bittien käsittely

Tiedon yksiköt

Bitti (bit) on pienin tiedon yksikkö, jonka arvo on joko 0 tai 1. Bitin avulla voi ilmaista, kumpi kahdesta vaihtoehdosta on valittu (tosi/epätosi, kyllä/ei, päällä/pois, jne.).

Tavu (byte) muodostuu 8 bitistä, ja se on tiedon perusyksikkö ohjelmoinnissa. Yhteen tavuun voidaan tallentaa kokonaisluku välillä 0–255.

Binääriluvut

Tavallinen tapa esittää lukuja on käyttää 10-järjestelmää, jolloin numerot ovat 0–9. Tietokone käyttää kuitenkin sisäisesti 2-järjestelmää eli binäärijärjestelmää, jossa ainoat numerot ovat 0 ja 1 eli bitit.

Binääriluvussa 1-bitit kertovat, mitkä 2:n potenssit kuuluvat lukuun. Esimerkiksi luvussa 100101 kohdissa 0, 2 ja 5 (oikealta luettuna) on bitti 1, joten tämä vastaa 10-järjestelmän lukua 2⁰ + 2² + 2⁵ = 1 + 4 + 32 = 37.

Kun käytettävissä on k bittiä, niistä voidaan muodostaa 2^k erilaista yhdistelmää. Tästä seuraa, että k bitin avulla voidaan tallentaa 2^k eri lukua.

Bitit ohjelmoinnissa

C++:ssa int-tyyppinen lukuarvo on yleensä 32-bittinen eli muodostuu neljästä tavusta. Pienin mahdollinen arvo on –2³¹ ja suurin mahdollinen arvo on 2³¹–1.

Esimerkiksi jos int-muuttujassa on luku 37, se on tallennettu näin:

00000000 00000000 00000000 00100101

Tietokoneessa luvun ensimmäinen bitti kertoo sen etumerkin. Jos bitti on 0, luku on positiivinen (tai nolla), ja jos bitti on 1, luku on negatiivinen. Negatiivinen luku tallennetaan kahden komplementtina, jossa luvusta x saa luvun –x muuttamalla ensin kaikki bitit vastakkaisiksi ja lisäämällä sitten lukuun 1.

Esimerkiksi jos int-muuttujassa on luku –37, se on tallennettu näin:

11111111 11111111 11111111 11011011

C++:ssa lukuarvo voi olla joko etumerkillinen (signed) tai etumerkitön (unsigned). Oletuksena lukuarvo on etumerkillinen, jolloin siihen voi tallentaa sekä positiivisen että negatiivisen luvun. Kuitenkin jos lukuarvo on etumerkitön, sen positiivinen arvoalue on kaksinkertainen.

Esimerkiksi seuraava koodi luo etumerkittömän int-muuttujan:

unsigned int x;

Tässä tapauksessa pienin mahdollinen arvo on 0 ja suurin mahdollinen arvo on 2³²–1.

Bittioperaatiot

Operaatio a & b (and) muodostaa luvun, jossa on bitti 1 kaikissa kohdissa, joissa sekä a:ssa että b:ssä on bitti 1. Esimerkiksi 26 & 19 on 18:

    11010 = 26
    10011 = 19
--------------
  & 10010 = 18

Operaatio a | b (or) muodostaa luvun, jossa on bitti 1 kaikissa kohdissa, joissa a:ssa tai b:ssä on bitti 1. Esimerkiksi 26 | 19 on 27:

    11010 = 26
    10011 = 19
--------------
  | 11011 = 27

Operaatio a ^ b (xor) muodostaa luvun, jossa on bitti 1 kaikissa kohdissa, joissa a:ssa ja b:ssä on eri bitti. Esimerkiksi 26 ^ 19 on 9:

    11010 = 26
    10011 = 19
--------------
  ^ 01001 =  9

Seuraava ohjelma esittelee bittioperaatioita:

int a = 26, b = 19;
cout << (a&b) << "\n"; // 18
cout << (a|b) << "\n"; // 27
cout << (a^b) << "\n"; // 9

Vastakkaiset bitit

Operaatio ~x muuttaa kaikki x:n bitit vastakkaisiksi. Tämän operaation tulkinta riippuu siitä, monestako tavusta luku muodostuu ja onko siinä etumerkkiä.

Esimerkiksi jos 37 on int-tyyppinen luku, operaatio toimii näin:

00000000 00000000 00000000 00100101 = 37
11111111 11111111 11111111 11011010 = ~37 = -38

Etumerkillisillä luvuilla ~x on yhtä suuri kuin -x-1.

Bittisiirrot

Operaatio x<<k siirtää x:n bittejä k askelta vasemmalle lisäämällä loppuun nollia. Tämä vastaa kertomista luvulla 2^k. Esimerkiksi 5<<2 on 20 ja vastaavasti bitteinä 101<<2 on 10100.

Operaatio x>>k siirtää x:n bittejä k askelta oikealle poistamalla bittejä lopusta. Tämä vastaa jakamista luvulla 2^k (pyöristäen alaspäin). Esimerkiksi 22>>2 on 5 ja vastaavasti bitteinä 10110>>2 on 101.

Usein kätevä on bittimaski 1<<k, jossa kohdassa k on bitti 1 ja kaikissa muissa kohdissa on bitti 0. Esimerkiksi voimme tulostaa luvun x bittimuodossa näin:

int x = 37;
for (int k = 31; k >= 0; k--) {
    if (x&(1<<k)) cout << "1";
    else cout << "0";
}
cout << "\n";

Ohjelman tulostus on seuraava:

00000000000000000000000000100101

Tie koodariksi