Integer (informatica)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een integer (Engels voor geheel getal, vaak ook op z'n Engels uitgesproken: ˈɪn.tɪ.d͡ʒə(ɹ) "intidzjer") in de informatica is een gegevenstype dat numerieke, geheeltallige informatie bevat.

Integers worden in de hardware gerepresenteerd als een aaneengesloten rij bits van een vooraf bepaalde lengte, bijgevolg is het waardenbereik eindig. Berekeningen met integers zijn in de regel exact, al kan door het overschrijden van het toegelaten waardenbereik overflow optreden. Al worden ze soms anders genoemd, het concept integer is in elke computer en in iedere programmeertaal aanwezig. Vaak zijn meer soorten integers beschikbaar, die zich onderscheiden door het aantal beschikbare bits (en daarmee het waardenbereik) en het al dan niet bieden van de mogelijkheid negatieve getallen weer te geven. De geïmplementeerde rekentechniek met integers is tot nu toe niet genormeerd en vertoont vaak taal- en zelfs compilerafhankelijke bijzonderheden. Met de Language Independent Arithmetic wordt een poging ondernomen tot normering te komen.

Integers en gehele getallen[bewerken]

Integers zijn de analogie of representatie van de gehele getallen voor gebruik op een computer. Integers onderscheiden zich echter van gehele getallen doordat er in de praktijk slechts eindig veel integers mogelijk zijn. Integers worden namelijk opgeslagen in een eindig aantal (op de meeste personal computers 32 of 64) bits, waardoor het aantal mogelijke waarden beperkt wordt. Hierdoor vormen de integers in elke implementatie een eindige deelverzameling van de verzameling gehele getallen.

Omdat elke bit twee mogelijke waarden heeft (0 en 1), kunnen met n bits \scriptstyle2^n verschillende combinaties gemaakt worden. Het gevolg hiervan is dat met twee bits (n = 2), hooguit vier (= 2²) verschillende getallen weergegeven kunnen worden. Bij het noteren van de binaire voorstelling van een getal is het gebruikelijk om, net als bij decimale getallen, de meest significante bit links te schrijven en de minst significante rechts.

bit1 bit0
0 0 = 0
0 1 = 1
1 0 = 2
1 1 = 3

Dit komt overeen met een twee-bits unsigned integer, een tekenloze ("+" of "−") digitale representatie van een getal in 2 bits die alle mogelijke combinaties benut. Optellen werkt in principe hetzelfde als in het decimale stelsel.

bit2 bit1 bit0
1 1 onthouden (carry)
0 1 1 = 3
0 0 1 = 1
-------------------- +
1 0 0 = 4

Binary Coded Decimal[bewerken]

Nuvola single chevron right.svg Zie BCD-code voor het hoofdartikel over dit onderwerp.

In de jaren vijftig en zestig van de vorige eeuw was BCD een getalsrepresentatie die nogal eens gebruikt werd. Dit had voordelen bij het representeren van data op een display, want een binaire versie hoefde niet meer omgerekend te worden, wat veel elektronica bespaarde. Ook tegenwoordig wordt voor die doeleinden nog vaak BCD gebruikt in de elektronica en in microcontrollers, specifiek in combinatie met elektronische displays.

In BCD worden vier bits per decimaal cijfer gereserveerd, waarbij de toewijzing van de waarde gelijk is aan de binaire versie. Dit betekent echter dat het bereik van een BCD-octet [1] beduidend kleiner is: 0 tot en met 99 in plaats van 0 tot en met 255.

In moderne computers wordt BCD bijna niet meer gebruikt, daar het rekenen vrij omslachtig en nodeloos tijdrovend is.

De tekenbit (signbit)[bewerken]

Het is echter niet genoeg alleen positieve getallen te kunnen uitdrukken, ook negatieve getallen moeten gecodeerd, dat wil zeggen, in een bitrij worden omgezet die voor de CPU begrijpelijk is. Het simpelste is een extra tekenbit (sign bit) toe te voegen.

tekenbit bit1 bit0
0 0 0 = 0
0 0 1 = 1
0 1 0 = 2
0 1 1 = 3
1 0 0 = −0
1 0 1 = −1
1 1 0 = −2
1 1 1 = −3

Het nadeel is natuurlijk dat de waarde 0 tweemaal voorkomt. Bovendien bleek deze representatie vrij lastig te implementeren te zijn, daar voor optellen en aftrekken verschillende circuits nodig zijn, terwijl aftrekken eigenlijk niet meer is dan het optellen van een negatief getal (optellen is associatief).

 A - B = A + (-B) = (-B) + A : A, B \in \N

maar bij een naïeve optelling, zoals bij een unsigned integer, gaat het mis:

tekenbit bit1 bit0
1 1 0 = −2
0 0 1 = 1
------------------ +
1 1 1 = −3

One's complement[bewerken]

Nuvola single chevron right.svg Zie One's complement voor het hoofdartikel over dit onderwerp.

Een representatie die wel associatief is, is One's complement of 1-complement.

Positieve getallen worden daarin weliswaar voorgesteld door een bitrij beginnend met een 0 en negatieve beginnend met een 1, maar het tegengestelde van een getal bestaat uit de bitrij met alle bits geïnverteerd, dus de rij met complementaire bits. Hierbij fungeert de meest significante bit nog steeds als tekenbit. Dit inverteren (ook wel bitwise NOT) is elektronisch een heel eenvoudige bewerking, die nauwelijks tijd, transistors en dus vermogen en kostbare ruimte op de chip kost.

In wiskundige termen geld voor een N-bits, 1-complement getal:

 -A \equiv ( 2^N - 1 ) - A = 2^N - A - 1: A,N \in \N, 0 \leq A < 2^{N-1}
tekenbit bit1 bit0
0 0 0 = 0
0 0 1 = 1
0 1 0 = 2
0 1 1 = 3
1 0 0 = −3
1 0 1 = −2
1 1 0 = −1
1 1 1 = −0

Bij een naïeve optelling, dat wil zeggen net als bij unsigned integers:

tekenbit bit1 bit0
1 onthouden (carry)
1 0 1 = −2
0 0 1 = 1
---------------------------- +
1 1 0 = −1

maar

tekenbit bit1 bit0
1 1 0 = −1
0 0 1 = 1
---------------------------- +
1 1 1 = −0

Formeel beschreven betekent one's complement, dat de bitrij b_nb_{n-1} \cdots b_0 een positief getal voorstelt als de bit bn = 0 en een negatief getal als bn = 1. Het positieve getal 0b_{n-1} \cdots b_0 stelt het binair geschreven getal N voor, en het tegengestelde hiervan, −N, wordt voorgesteld door de bitrij  1\overline{b_{n-1}} \cdots \overline{b_0}, waarin alle bits geïnverteerd zijn. De som van beide levert de bitrij 111...1 op, die dus ook het getal 0 voorstelt.

Het grootste voordeel is dus dat alle optel- en aftrekbewerkingen (signed en unsigned) door hetzelfde circuit gedaan kunnen worden en dat signed en unsigned parameters gemengd kunnen worden gebruikt. Het ene nadeel is dat er nog steeds twee verschillende waarden voor nul zijn, en dit is een probleem want vergelijkingen met 0 komen veel voor, het andere dat zonder speciale maatregelen, dat wil zeggen, extra elektronica, "0+1" of "0−1" nul kunnen opleveren.

Two's complement[bewerken]

Nuvola single chevron right.svg Zie Two's complement voor het hoofdartikel over dit onderwerp.

Two's complement of 2-complement is de getalsrepresentatie die in computers algemeen wordt gebruikt. Het is niet alleen associatief, maar heeft maar één representatie voor '0', de voor de hand liggende. Kort gezegd is 2-complement 1-complement plus een als de tekenbit '1' is (dat wil zeggen, bij negatieve getallen). Het heeft alle voordelen van One's Complement, maar niet de nadelen, en is dus het goedkoopst te implementeren in hardware. Vandaar dat dit de algemeen gangbare integer-representatie is.

In wiskundige termen geld voor een N-bits, 2-complement getal:

 -A \equiv (2^N - A - 1) + 1 = 2^N-A : A,N \in \N, 0 \leq A < 2^{N-1}

De middelste term maakt duidelijk waarom gezegd wordt: "2-complement is 1-complement + 1", want deze increment werkt elegant de "dubbele 0" weg. "−0" ("1 1 1" in het voorbeeld hierboven) wordt "0" ("0 0 0").

tekenbit bit1 bit0
0 0 0 = 0
0 0 1 = 1
0 1 0 = 2
0 1 1 = 3
1 0 0 = −4
1 0 1 = −3
1 1 0 = −2
1 1 1 = −1

Het bereik van een N-bits 2-complement getal x wordt gegeven door:

-2^{N-1} \leq x \leq (2^{N-1} - 1) : N, x \in \N, N \geq 2

Overflow, underflow en rollover[bewerken]

In de informatica is het verschijnsel overflow bekend. Dit betekent dat een getal te groot of te klein is om gerepresenteerd te worden door het beschikbare aantal bits. Zo kan met 8 bits bij een 2-complements getalspresentatie een signed integer van −128 tot en met 127 gecodeerd worden. Mocht het antwoord van een berekening, bijvoorbeeld het optellen van twee positieve getallen, buiten dit interval liggen, dan treedt een overflow op. Bij te lage waarden, bijvoorbeeld als het resultaat onder −128 uitkomt, spreekt men ook wel van underflow. De meeste microprocessors geven deze over- en/of underflow aan in een aparte bit in het statusregister. Indien nodig kunnen computerprogramma's hierop reageren. Als een programma niet of niet juist op een overflow reageert, dan kan het programma onjuiste en (vaak) ongewenste resultaten opleveren.

Bij tellers (zoals gebruikt worden in bijvoorbeeld computer-klokken en timers) kan het zijn dat bewust niet speciaal gereageerd wordt op de overflow, er wordt gerekend modulo het aantal representeerbare getallen. Men spreekt in dit geval ook wel van rollover. Denk hierbij aan de volgnummers die wel gebruikt worden in bijvoorbeeld postkantoren: na nummer 99 komt nummer 00.

Endianness[bewerken]

Nuvola single chevron right.svg Zie Endianness voor het hoofdartikel over dit onderwerp.

Aangezien de woordbreedte van het geheugen nogal kan verschillen van die van de processor, is er een manier nodig om de inhoud van een N-bits integer te verdelen over M geheugenadressen. Bij een huis-tuin-en-keuken PC, bijvoorbeeld, moet de inhoud van een 32 bits register verdeeld worden over 4 bytes (strikt genomen octets). Er zijn voor dit probleem twee gangbare (Big Endian en Little Endian) en een aantal niet zo gangbare systemen in omloop.

Integers in C[bewerken]

De programmeertaal C kent een aantal types integer, waarover, vooral bij hobby-programmeurs en novicen, nogal eens wat misverstanden bestaan. Zo stellen sommigen zonder meer "een long is 32 bits", wat een gevaarlijke misvatting is. Een andere misvatting is dat "signed" integers altijd in 2-complement vorm staan. Dit is weliswaar in de regel het geval, maar het wordt geenszins door de standaard vereist.

officiële naam afgekorte naam aantal bits typische implementaties[2]
8/16 bits 32 bits 64 bits
short int short 16 16 16 16
int minimaal 16 16 32 32
long int long minimaal 32 32 32 64
long long int[3] long long minimaal 64 meestal afwezig 64 128

Een "normale" integer heeft in deze taal een minimale breedte van 16 bits, hoewel de meeste huis-, tuin- en keuken-pc-programmeeromgevingen voor beide typen 32 bits hanteren. Dit heeft aanleiding gegeven tot veel misverstanden onder hobby-programmeurs en de sarcastische slogan "all the world is 32 bit". De fouten die hiermee worden gemaakt, door aan te nemen dat type X altijd N bits telt of dat type X en type Y even breed zijn, komen aan het licht zodra een van beide typen afwijkt, bijvoorbeeld omdat men is overgeschakeld naar een 64-bits implementatie, waar een long integer 64 bits bevat. Dit verschijnsel is een vrij veelvoorkomende bron van bugs. Met de sizeof operator laat zich echter eenvoudig achterhalen welke definities een specifieke compiler gebruikt en kan de software zonder deze aannames geschreven worden.

Bronnen, noten en/of referenties

Noten

  1. Acht bits, vaak onterecht gelijkgesteld aan een byte dat geen vast aantal bits heeft.
  2. Dat wil zeggen dat dit gangbaar is, niet dat het voorgeschreven is.
  3. Sinds ISO-C99

Bronnen