Integer (informatica)

Een integer (Engels voor 'geheel getal') is in de informatica een gegevenstype dat geheeltallige informatie bevat. In het Engels wordt integer uitgesproken als [ˈɪn.tɪ.d͡ʒə(ɹ)]^?, in het Nederlandse taalgebied wordt daarnaast vaak de uitspraak [ˈɪn.tə.ɣər]^? gehoord.

Integers worden in de hardware gerepresenteerd als een aaneengesloten rij bits van een vooraf bepaalde lengte. Het waardenbereik is hierdoor 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 is in elke computer en in de meeste programmeertalen 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

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

Doordat elke bit twee mogelijke waarden heeft (0 en 1), kunnen met $n$ bits $2^{n}$ verschillende combinaties gemaakt worden. Met twee bits kunnen dus hooguit vier verschillende getallen weergegeven worden. Met 32 bits zijn het ruim 4 miljard integers, en met 64 bits ongeveer 18×10¹⁸.

Bij het noteren van de binaire voorstelling van een getal is het gebruikelijk, net als bij decimale getallen, de meest significante bit links te schrijven en de minst significante rechts.

Deze vier binaire getallen kunnen opgevat worden als twee-bits unsigned integers, een tekenloze digitale representatie van een getal in twee bits die alle mogelijke combinaties benut. Op analoge wijze kunnen met bijvoorbeeld 8 bits 256 integers voorgesteld worden. Optellen en aftrekken van dergelijke integers (binaire getallen) kan in principe op dezelfde manier als met decimale getallen. Als voorbeeld de optelling 19 + 7 en de aftrekking 19 − 7 in een representatie met 8 bits.

       111    onthouden (carry)
  0001 0011   =  19
  0000 0111   =   7
 —————————— +    ——
  0001 1010   =  26

     1 1     lenen (borrow)
  0001 0011   =  19
  0000 0111   =   7
 —————————— −    ——
  0000 1100   =  12

De laatste berekening kan ook opgevat worden als de optelling 19 + (−7). Om de optelling op de gewone manier uit te kunnen voeren, moet ze er als volgt uitzien (en begrensd worden tot 8 bits):

  0001 0011   =  19
  1111 1001   =  −7
 —————————— +    ——
  0000 1100   =  12

Het negatieve getal −7 moet dan weergegeven worden door 1111 1001 (¬7 + 1). Deze representatie is de zogenaamde two's complement-representatie. Door het gebruik van deze representatie voor negatieve getallen kan elke aftrekking tot een optelling herleid worden.

Binary Coded Decimal

In de jaren vijftig en zestig van de twintigste 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)

Naast positieve getallen, moeten ook negatieve getallen gecodeerd worden, dat wil zeggen, worden omgezet in een bitrij die voor de CPU begrijpelijk is. Een eenvoudige manier is een extra bit b₃ als tekenbit (signbit) toe te voegen.

   b₃b₂b₁  
   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

Een nadeel is dat de waarde 0 tweemaal voorkomt, als +0 en als −0. Bovendien blijkt deze representatie vrij lastig te implementeren, daar voor optellen en aftrekken verschillende circuits nodig zijn, terwijl aftrekken eigenlijk niet meer is dan het optellen van een negatief getal.

A-B=A+(-B);A,B\in \mathbb {N}

Maar bij de gewone, naïeve optelling, gaat het mis:

   110    = −2
   001    =  1
  ———— +    ——
   111    = −3 ?

One's complement

Een representatie waarmee de rekenoperaties, zij het met een geringe aanpassing, gewoon uitgevoerd kunnen worden, is one's complement of 1-complement. In deze representatie worden positieve integers op de gebruikelijke wijze voorgesteld door de bitrij die hoort bij hun binaire voorstelling voorafgegaan door een 0. Negatieve integers bestaan uit de bitrij van complementaire bits van hun positieve tegengestelde, dus met alle bits geïnverteerd. De bitrij van een negatief getal begint dus met een 1. De meest significante bit fungeert 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.

Met $n$ bits en de bitrij $b_{n}b_{n-1}\ldots b_{2}b_{1}$ de binaire voorstelling van het getal $b$ geldt voor de integers $-2^{n-1}<N<2^{n-1}$ :

De 1-complement-representatie van een positieve integer $N$ is de bitrij met $b=N$ , en dus de meest significante bit $b_{n}=0$ . Een negatieve integer $N$ heeft als 1-complement-representatie de bitrij met $b=2^{n}-1-N$ , en dus de meest significante bit $b_{n}=1$ . Er geldt ook: als $b_{n}b_{n-1}\ldots b_{2}b_{1}$ de 1-complement-representatie is van $N$ , dan is ${\overline {b_{n}}}{\overline {b_{n-1}}}\ldots {\overline {b_{2}}}{\overline {b_{1}}}$ de 1-complement-representatie van $-N$ .

Met 3 bits:

   b₃b₂b₁  
   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

Two's complement

Two's complement of 2-complement is de getalsrepresentatie die in computers algemeen wordt gebruikt. Er is maar één representatie voor '0', de voor de hand liggende. Two's complement heeft alle voordelen van one's complement, maar niet de nadelen, en is dus het eenvoudigst te implementeren in hardware. In two's complement worden positieve integers, net als in one's complement weergegeven door hun binaire voorstelling, voorafgegaan door een 0. Negatieve integers worden weergegeven door bij de voorstelling in one's complement 1 op te tellen.

Met $n$ bits en de bitrij $b_{n}b_{n-1}\ldots b_{2}b_{1}$ de binaire voorstelling van het getal $b$ geldt voor de integers $-2^{n-1}\leq N<2^{n-1}$ :

De 2-complement-representatie van een positieve integer $N$ is de bitrij met $b=N$ , en dus de meest significante bit $b_{n}=0$ . Een negatieve integer $N$ heeft als 2-complement-representatie de bitrij met $b=2^{n}-N$ , en dus de meest significante bit $b_{n}=1$ .

Met 3 bits:

   b₃b₂b₁  
   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

Overflow, underflow en rollover

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

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 64 bitregister verdeeld worden over 8 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

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]
officiële naam	afgekorte naam	aantal bits	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

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

Bronnen

[1] Acht bits, vaak onterecht gelijkgesteld aan een byte. Een byte heeft echter geen vast aantal bits.

[2] Dat wil zeggen dat dit gangbaar is, niet dat het voorgeschreven is.

[3] Sinds ISO-C99

[1]

[2]

[3]