Rekenen met bits, en ze groeperen

Omzetten, optellen, en bits samennemen tot bytes

OpmerkingLeerdoelen

Na deze les kan je:

  • gehele getallen omzetten tussen decimaal en binair, in beide richtingen
  • twee binaire getallen optellen en je resultaat decimaal controleren
  • uitleggen wat een byte is en hoeveel verschillende waarden erin passen
  • omzetten tussen binair en hexadecimaal door per vier bits te groeperen

In de vorige les heb je gezien hoe een binair getal is opgebouwd. Deze les gaan we ermee werken. We lezen binaire getallen uit en schrijven ze op, tellen er twee bij elkaar op, nemen bits samen tot bytes, en leren een kortere schrijfwijze voor lange rijen bits.

1 Van binair naar decimaal en terug

Binair bestaan er maar twee cijfers, dus elke term in de som is ofwel nul (wanneer het bit \(0\) is) ofwel de volledige macht (wanneer het bit \(1\) is). Een binair getal uitlezen komt daarmee neer op het optellen van de machten van twee die op \(1\) staan.

Neem \(110101_2\). Zet bij elke positie de macht die erbij hoort:

positie \(5\) \(4\) \(3\) \(2\) \(1\) \(0\)
macht van twee \(32\) \(16\) \(8\) \(4\) \(2\) \(1\)
bit \(\mathbf{1}\) \(\mathbf{1}\) \(0\) \(\mathbf{1}\) \(0\) \(\mathbf{1}\)

Optellen wat aanstaat geeft \(32 + 16 + 4 + 1 = 53\).

De omgekeerde richting, van decimaal naar binair, verloopt via herhaald delen door twee. Je deelt het getal door \(2\) en noteert de rest, deelt het quotiënt opnieuw door \(2\), en gaat zo door tot het quotiënt \(0\) is. De resten vormen samen het binaire getal, van onder naar boven gelezen.

\[ \begin{aligned} 53 &= 2 \cdot 26 + \mathbf{1}\\ 26 &= 2 \cdot 13 + \mathbf{0}\\ 13 &= 2 \cdot 6 + \mathbf{1}\\ 6 &= 2 \cdot 3 + \mathbf{0}\\ 3 &= 2 \cdot 1 + \mathbf{1}\\ 1 &= 2 \cdot 0 + \mathbf{1} \end{aligned} \]

Van onder naar boven gelezen geeft dat \(110101_2\), en dat is hetzelfde antwoord als hierboven.

Waarom werkt deze methode? De eerste rest is \(0\) of \(1\) en zegt dus of het getal even of oneven is. Dat is precies wat het laatste bit \(a_0\) uitdrukt, zoals je in de vorige les gezien hebt. Het quotiënt van die deling is hetzelfde getal zonder dat laatste bit. Decimaal gebeurt hetzelfde: deel \(5074\) door \(10\) en je krijgt het quotiënt \(507\) met rest \(4\), dus het getal zonder zijn laatste cijfer en dat laatste cijfer apart. Op dat kleinere getal stel je dezelfde vraag opnieuw, en dat levert \(a_1\) op. Zo werk je door tot er niets meer overblijft.

Dezelfde werkwijze gaat op voor elke basis. Wil je naar basis zeven, deel dan telkens door zeven in plaats van door twee, en lees de resten opnieuw van onder naar boven.

Python kan je antwoorden controleren. De functie int leest een tekst als een getal in een gegeven basis, en bin geeft de binaire schrijfwijze van een getal terug als tekst. De cellen hieronder starten niet vanzelf, dus klik op Run Code.

Het voorvoegsel 0b in dat antwoord is de tegenhanger van onze index \(2\).

2 Binair optellen

Optellen verloopt zoals in de lagere school: van rechts naar links, met overdracht naar de volgende kolom. Overdracht is het woord voor wat je gewoonlijk “onthoudt”, namelijk het deel van een som dat niet in zijn eigen kolom past en dus naar de kolom links ervan doorschuift.

Het verschil met decimaal is dat er maar twee cijfers bestaan, waardoor er al bij \(1 + 1\) overdracht ontstaat. Meer regels dan deze vier zijn er niet.

som opschrijven overdracht
\(0 + 0\) \(0\) \(0\)
\(0 + 1\) of \(1 + 0\) \(1\) \(0\)
\(1 + 1\) \(0\) \(\mathbf{1}\)
\(1 + 1 + 1\) \(1\) \(\mathbf{1}\)

Hieronder staat een uitgewerkte som. De bovenste rij bevat de overdrachten, telkens boven de kolom waarin ze meegeteld worden.

  1 1 1
    1 1 1 0
+   0 1 1 1
  ---------
  1 0 1 0 1

De rechtse kolom geeft \(0 + 1 = 1\), zonder overdracht. De volgende geeft \(1 + 1\), dus je schrijft \(0\) en draagt \(1\) over. De derde geeft \(1 + 1 + 1\), dus je schrijft \(1\) en draagt opnieuw \(1\) over. De vierde geeft \(1 + 0 + 1\), dus \(0\) met een overdracht die vooraan als een vijfde bit blijft staan.

Bijgevolg is \(1110_2 + 0111_2 = 10101_2\). Decimaal is dat \(14 + 7 = 21\), en \(10101_2 = 16 + 4 + 1 = 21\).

3 Bits groeperen: de byte

Eén bit apart is te klein om mee te werken. Een computer groepeert ze daarom, gewoonlijk per acht, en zo’n groepje van acht bits heet een byte.

Uit de vorige les volgt meteen hoeveel een byte kan bevatten. Elk van de acht posities heeft twee mogelijkheden, dus er zijn \(2^8 = 256\) verschillende patronen, en die stellen de getallen \(0\) tot en met \(255\) voor. Het grootste is \(11111111_2\), en dat is \(2^8 - 1\), precies één tekort voor \(256\).

De keuze voor acht is een historische afweging die goed uitgevallen is. Acht bits zijn genoeg voor één tekstteken uit het Latijnse alfabet met leestekens erbij, genoeg voor één kleurkanaal van een pixel (de hoeveelheid rood, van \(0\) tot \(255\)), en klein genoeg om zuinig met geheugen om te springen. Alles wat erboven zit, is vervolgens rond veelvouden van acht gebouwd: \(16\), \(32\) en \(64\) bits. Een geheel getal beslaat in de praktijk \(32\) of \(64\) bits, een pixel meerdere bytes, en een geheugenadres in een moderne machine \(64\) bits.

4 Hexadecimaal

Binaire rijen worden snel lang. \(53\) heeft al zes bits nodig, een byte er acht, en een geheugenadres ongeveer vierenzestig. Niemand leest zulke rijen graag, en daarom werken informatici vaak in basis zestien, het hexadecimale stelsel, kortweg hex.

Zestien cijfersymbolen zijn daarvoor nodig. Na de \(9\) gaat men met letters verder: \(A\) is tien, \(B\) is elf, en zo door tot \(F\) voor vijftien. Zo is \(2F_{16} = 2 \cdot 16 + 15 = 47\).

De keuze voor net zestien komt voort uit \(2^4 = 16\). Eén hex-cijfer komt daardoor precies overeen met vier bits. Zo’n groepje van vier heet een nibble. Omzetten tussen binair en hex is dus geen rekenwerk maar groeperen. Neem een rij van \(32\) bits, verdeel ze vanaf rechts in groepjes van vier, en vervang elk groepje door zijn hex-cijfer.

1100 0101 0110 0010 0101 1101 0111 0010
   C    5    6    2    5    D    7    2

Het resultaat is C5625D72: acht tekens in plaats van tweeëndertig, zonder dat er één bit verloren gaat. In de omgekeerde richting vervang je elk hex-cijfer door zijn vier bits.

Dezelfde werkwijze gaat op naar basis acht, met groepjes van drie, aangezien \(8 = 2^3\). Naar decimaal gaat ze niet op, want \(10\) is geen macht van twee. Daar heb je het herhaald delen van hierboven voor nodig.

Python spreekt hex met het voorvoegsel 0x, de tegenhanger van onze index \(16\). De functie hex geeft de hexadecimale schrijfwijze van een getal terug als tekst, en int leest een tekst als een getal in een gegeven basis, net zoals hierboven.

Je komt hex overal tegen waar ruwe bytes aan mensen getoond worden. Een webkleur als #FF6600 bestaat uit drie bytes na elkaar, met rood op \(255\), groen op \(102\) en blauw op \(0\). Een MAC-adres, het serienummer van een netwerkkaart, bestaat uit zes bytes en wordt geschreven als 00:0C:6E:D2:11:E6. Hetzelfde geldt voor IPv6-adressen, geheugendumps en bestandsformaten.

Probeer het zelf. Kies een kleur en kijk welke twee hex-cijfers bij welk kanaal horen. Zet rood op zijn maximum en de andere twee op nul, en lees af wat er staat.

#FF6600
rood FF = 255
groen 66 = 102
blauw 00 = 0

5 Conclusie

Vier dingen kan je nu met een binair getal: het uitlezen, het opschrijven, er een tweede bij optellen, en het korter noteren in hex. In alle vier gevallen verandert de waarde niet, alleen de vorm waarin ze op papier staat.

Eén ding is intussen wel veranderd tegenover de vorige les. Een byte is acht bits, niet zoveel bits als je nodig hebt. Op papier schrijf je er gewoon een bij wanneer de som te groot wordt, en dat is precies wat een computer niet kan doen. Daar gaat de volgende les over.

6 Begrippen

  • overdracht: wat bij een optelling niet in zijn eigen kolom past en naar de kolom links ervan doorschuift.
  • byte: een groepje van acht bits, goed voor \(256\) verschillende patronen.
  • hexadecimaal: het stelsel met basis zestien, kortweg hex, met de letters \(A\) tot \(F\) als cijfers voor tien tot vijftien.
  • nibble: een groepje van vier bits, precies één hex-cijfer.

7 Oefeningen

  1. Zet \(10110_2\) om naar decimaal.

    \(10110_2 = 16 + 4 + 2 = 22\).

  2. Schrijf \(30\) in basis \(7\) en in basis \(4\).

    Herhaald delen door \(7\) geeft \(30 = 7 \cdot 4 + 2\) en \(4 = 7 \cdot 0 + 4\), van onder naar boven dus \(42_7\). Controle: \(4 \cdot 7 + 2 = 30\). Herhaald delen door \(4\) geeft de resten \(2, 3, 1\), dus \(132_4\). Controle: \(1 \cdot 16 + 3 \cdot 4 + 2 = 30\).

  3. Bereken \(1011_2 + 0110_2\) binair, en controleer decimaal.

    \(1011_2 + 0110_2 = 10001_2\), met een overdracht in drie opeenvolgende kolommen. Controle: \(11 + 6 = 17\) en \(10001_2 = 16 + 1 = 17\).

  4. Aan het laatste bit zie je of een getal even is, dus deelbaar door \(2\). Waaraan zie je of een binair getal deelbaar is door \(4\)? Verklaar met de som uit de vorige les.

    Aan de laatste twee bits: het getal is deelbaar door \(4\) precies wanneer het op \(00\) eindigt. Elke term \(a_i 2^i\) met \(i \geq 2\) bevat de factor \(4\) en is dus deelbaar door \(4\). Wat overblijft is \(a_1 \cdot 2 + a_0\), en dat is enkel \(0\) wanneer beide bits \(0\) zijn.

  5. Zet \(A3\) om naar binair en naar decimaal.

    Per hex-cijfer vier bits: \(A\) is \(1010\) en \(3\) is \(0011\), samen \(10100011_2\). Decimaal is dat \(10 \cdot 16 + 3 = 163\), wat je kan controleren met \(128 + 32 + 2 + 1 = 163\).

  6. Waarom is een webkleur zoals #FF6600 altijd zes hex-cijfers lang, en nooit vijf of zeven?

    Een kleur bestaat uit drie bytes, één per kleurkanaal. Eén byte is acht bits, dus twee nibbles, dus precies twee hex-cijfers. Drie bytes geven daarmee altijd \(3 \cdot 2 = 6\) cijfers.

  7. Hoeveel hex-cijfers heb je nodig voor een getal van \(64\) bits? Verklaar zonder te rekenen met machten van zestien.

    Zestien. Eén hex-cijfer dekt vier bits, en \(64\) bits vallen uiteen in \(64 : 4 = 16\) groepjes van vier.