Integer (informatica)

Een integer (spreek uit: "intidzjer", van Engels: geheel getal) in de informatica is een element uit de beschikbare deelverzameling van de gehele getallen.

Inhoud

1 Het principe integer
2 Integerrepresentatie
3 Rekenregels
- 3.1 Basisoperaties
- 3.2 Overflow en underflow
4 Zie ook

[bewerk] Het principe integer

In principe komt de verzameling van integers dus overeen met de verzameling der gehele getallen. De integers zijn de analogie van de gehele getallen voor gebruik op een computer.

De integers onderscheiden zich echter op een tweetal wezenlijke, praktische punten van de gehele getallen. Dit onderscheid maakt het interessant om de integers als een aparte verzameling te zien en te beschouwen.

Deze twee verschillen zijn:

Door de manier waarop integers gebruikt worden (in een computer), gelden voor integers wat andere rekenregels dan voor "normale" getallen.
Omdat integers op een computer bestaan, is de verzameling der integers altijd eindig. Bepaalde getallen die bestaan als geheel getal, zijn als integer niet gedefinieerd. Bovendien heeft dit ook weer zijn uitwerking op de bewerkingen die op integers uitgevoerd kunnen worden. In enkele programmeertalen, zoals Java, is het mogelijk om een bitreeks, meestal de maximumwaarde van een integer, te reserveren als constante voor het getal "oneindig".

[bewerk] Integerrepresentatie

Een integer wordt in een computer voorgesteld door een rij bits, die opgevat wordt als de binaire voorstelling van de integer, zij het dat de meest significante bit vaak als tekenbit wordt gebruikt om een deel van de beschikbare integers als negatief te bestempelen.

Omdat een computer een eindig medium is, zal ook de lengte van de bitrij die een integer voorstelt eindig zijn, en dus ook de omvang van de in een specifieke computer beschikbare verzameling integers.

Iedere computer en iedere programmeertaal specificeert altijd wat er voor die computer of taal bedoeld wordt met een integer. Dat wil zeggen, iedere computer en taal specificeert het aantal bits die gebruikt worden om een integer voor te stellen. Dit aantal kan voor iedere computer of taal anders zijn, maar in de meeste gevallen is die lengte 8, 16, 32 of 64. In een enkel geval zelfs 128. Andere waarden komen nauwelijks voor. Veel talen kennen ook verschillende soorten integers met aparte benamingen. Visual Basic kent bijvoorbeeld de typen Byte (8 bits), Integer (16 bits) en Long (32 bits). Voor nog langere integers kan de programmeur zelf een klasse definiëren door Integer Uitbreiding.

[bewerk] Signed versus unsigned

Een ander, praktisch verschil tussen computers en mensen is dat in een computer (die intern alleen bitjes kent) geen concept heeft als het teken "-" (als in -3, -64, -7). Een computer kan dus niet met een expliciet teken onderscheid maken tussen positief en negatief, omdat de enige tekens die een computer kent (1 en 0) ook gebruikt worden voor de representatie van getallen.

Om bij integers onderscheid te maken tussen positief en negatief is het dus nodig om iets anders te verzinnen, een afspraak te maken. De normale afspraak is dat de meest significante van alle bits apart gezet wordt en dienst doet als teken. Dit levert echter meteen een onderscheid op in soorten integers: integers waarbij een teken-bit hoort en integers waarbij alle bits tot het getal behoren. In talen waar een dergelijk onderscheid gemaakt wordt (zoals C) spreekt met van signed en unsigned integers.

[bewerk] Tekenbit

Het hierboven aangeduide onderscheid gaat over het onderscheid in de interpretatie van (bijvoorbeeld) de bitrijen

01001101

11001101

Beschouwen we de bitrij in zijn geheel als waardevormende tekenrij, dan duidt de bovenste rij het getal 77 aan en de onderste het getal 205. Vatten we de meest significante bit op als tekenbit, dan is een van de rijen 77 en de andere -77. Het is daaarbij gebruikelijk om de bitrijen waarvan de meest significante bit de waarde 1 heeft, als negatief op te vatten.

Merk op dat deze manier van representeren in computers eigenlijk niet gebruikt wordt. Daar wordt normaal gesproken gekozen voor andere representaties, waar we hieronder op in zullen gaan.

Merk ook op dat deze representatie twee representaties van het getal 0 kent: 00000000 (0) en 10000000 (-0). Of dit erg kwalijk is, hangt af van de toepassing. In computers zijn twee getalsrepresentaties in algemeen gebruik, waarbij de ene twee representaties van 0 heeft en de andere niet: de one's-complement representatie en de two's-complement representatie.

[bewerk] One's complement

One's complement is een van de twee getalsrepresentaties die in computers algemeen in omloop zijn.

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 complemantaire bits. Het positieve getal 79 bijvoorbeeld wordt (met 8 bits) voorgesteld door 01001111 en -79 door 10110000. Men kan de voorstelling van -79 verkrijgen door de bitrij van 79 af te trekken van de rij met alleen 1-en: 11111111. Hiervan komt de naam: complement van 1-en. Deze representatie kent twee bitrijen die 0 voorstellen: 00000000 en 11111111.

Formeel beschreven betekent one's complement, dat de bitrij $b_nb_{n-1} \cdots b_0$ een positief getal voorstelt als de bit b_n = 0 en een negatief getal als b_n = 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.

Anders gezegd: vermenigvuldiging van een bitrij met -1 in one's complement komt overeen met het vervangen van iedere 0 door een 1 en iedere 1 door een 0.

Het gebruik van one's complement heeft enige gevolgen voor het uitvoeren van rekenkundige operaties. Hierop gaan we verderop in.

[bewerk] Two's complement

Two's complement is een van de twee getalsrepresentaties in computers die algemeen in omloop zijn. Het is ook de meest gebruikte representatie ten tijde van dit schrijven.

Positieve getallen worden ook hierin voorgesteld door een bitrij beginnend met een 0 en negatieve beginnend met een 1, maar het tegengestelde bestaat nu uit de bitrij die verkregen wordt als het verschil met de bitrij met allemaal 0-en en een 1 als extra bit ervoor geplaatst. Deze bitrij stelt dan het getal 2ⁿ voor bij een representatie met n bits. De representatie komt neer op het rekenen modulo 2ⁿ. Het positieve getal 79 bijvoorbeeld wordt (met 8 bits) voorgesteld door 01001111 en -79 door 11010001. Tellen we beide op, dan krijgen we als som de rij 100000000, die overigens zelf in de representatie niet voorkomt.

Uit het bovenstaande kan afgeleid worden dat de representatie in two's complement verkregen wordt door bij de representatie in one's complement 1 op te tellen: -79 in one's complement (8 bits) 10110000; tel er 1 bij op: 10110000 + 00000001 = 10110001, de voorstelling van -79 in two's complement.

Net als bij one's complement wordt bij two's complement de meest significante bit gebruikt om aan te geven of een getal positief is of negatief. Deze meest significante bit heeft echter een andere betekenis dan bij one's complement: in plaats van de rol van een soort minteken te vervullen, staat de meest significante bit (zeg, bit nummer n) voor $- 1 * 2 n$ . De rest van de bits worden "normaal" geïnterpreteerd en een negatief getal wordt dan ook gevormd door de positieve waarde van de minder significante bits op te tellen bij $- 1 * 2 n$ .

Door deze definitie van getallen is de hoogste waarde die gerepresenteerd kan worden met een bitrij waarvan het meest significante bit de waarde 1 heeft, de waarde -1. In tegenstelling tot one's complement is er dus niet zoiets als -0 in two's complement notatie. Bijgevolg is het aantal representeerbare, negatieve waarden in two's complement ook een groter dan het aantal representeerbare, positieve waarden: van $- 1 * 2 n$ tot en met $2 n - 1$ .

De relatie tussen positieve en negatieve waarden is dan ook als volgt:

Zij b = $0b_{n-1} \cdots b_{0}$ een bitrij die de waarde N representeert. Dan is (met dezelfde definitie voor complement van een bit als bij one's complement) de bitrij die -N representeert gelijk aan $1b_{n-1}^* \cdots b_{0}^* + 1$ .

Het idee is als volgt: stel dat je met een bitrij de waarden $- 1 * 2 n + 1$ tot en met $2 n - 1$ zou kunnen representeren in two's complement notatie (dus dan zou de interpretatie van de meest significante bit $- 1 * 2 n + 1$ zijn in plaats van $- 1 * 2 n$ ). Voor iedere representeerbare negatieve waarde -N geldt dan: $- N = ( - 1 * 2 n + 1) + (2 n - 1 - N)$ . Gegeven een waarde N, vinden we de waarde $(2 n - 1 - N)$ door van alle bits behalve de meest significante het complement te nemen. Tellen we deze waarde op bij $- 1 * 2 n + 1$ (door ook de meest significante bit 1 te maken), dan vinden we $( - 1 * 2 n + 1) + (2 n - 1 - N) = - N$ . Echter, we hadden afgesproken dat de waarde van de meest significante bit $- 1 * 2 n$ is en niet $- 1 * 2 n + 1$ . Om die ontbrekende 1 te compenseren, moet er 1 bij de de complement-notatie opgeteld worden om bij N de waarde -N te vinden.

Als voorbeeld vinden we -77 uit 77 in two's complement als volgt:

  77  = 01001101₂      
  255 = 11111111₂         alles inverteren ( is xor )
 ---------------- xor
  -78 = 10110010₂         
    1 = 00000001₂         1 erbij optellen
  ---------------- +
  -77 = 10110011₂         en we hebben het two's complement

Een andere uitleg is:

   77  = 01001101₂      
   77* = 00110010₂ = 50    alles inverteren behalve de tekenbit
 
  -128 = 10000000₂         de tekenbit inverteren
   50  = 00110010₂         optellen bij het geïnverteerde getal
  ---------------- +
   -78 = 10110010₂         nu zijn alle bits geïnverteerd
     1 = 00000001₂         1 erbij optellen
  ---------------- +
   -77 = 10110011₂         en we hebben het two's complement

Dus in het kort is two's complement gelijk aan one's complement (inverteer alle bits) met daarbij 1 opgeteld. De two's complement representatie van een integer is vooral zinvol in verband met het optellen van getallen in hardware. Als two's complement gebruikt wordt, maakt het uit of een of beide operanden negatief zijn. Hierdoor is een optelschakeling op een computerchip eenvoudiger te implementeren dan voor andere representaties. Een aparte schakeling om een getal van een ander getal af te trekken hoeft niet te worden gemaakt. In dat geval wordt een van de operanden negatief gemaakt alvorens deze op te tellen.

[bewerk] Little endian en Big endian

Hierboven zijn integers besproken van 8 bits hetgeen gelijk is aan 1 byte. Meestal zijn integers echter meerdere bytes lang. Nu zijn er twee mogelijkheden om dit te representeren in een computergeheugen. De meest significante byte kan in de hoogste van de gebruikte geheugenplaatsen gezet worden met de minst significante byte in de laagste geheugenplaats. Dit heet big endian. Indien dit andersom is spreken we van little endian.

Zie ook Endianness

[bewerk] Rekenregels

[bewerk] Basisoperaties

De basisoperaties die op een integer toegepast kunnen worden zijn

[bewerk] Overflow en underflow

In de informatica is het verschijnsel overflow bekend. Dit betekent dat een getal te groot of te klein is om te gerepresenteerd te worden door het beschikbare aantal bits. Zo kan met 8 bits een signed integer van -128 tot en met 127 gecodeerd worden. Mocht het antwoord van een berekening buiten dit interval liggen, dan treedt een overflow op. Of deze overflow als fout gezien wordt hangt af van de situatie. De meeste microprocessors geven deze overflow aan in een aparte bit in het statusregister.

Bij het optellen van twee positieve getallen waarbij het antwoord buiten het bereik van de integer ligt, zal een overflow als fout aangemerkt worden. Bij goede programmering zal de software hierop adequaat reageren.

Indien twee te grote negatieve getallen bij elkaar opgeteld worden, zal ook overflow worden aangegeven. In dit geval spreekt men ook wel van underflow.

[bewerk] Zie ook

Categorieën: Informatica | Getal