17 Operaties op bits In hoofdstuk 1 is gezegd dat C oorspronkelijk bedoeld was als systeemprogrammeertaal om het besturingssysteem UNIX te implementeren. Bij dit soort toepassingen komt het voor dat afzonderlijke bitpatronen binnen een woord van de computer moeten worden bewerkt. Deze mogelijkheid biedt C door middel van bitoperatoren.
17.1 Bitoperatoren en bitexpressies Naast de bitvelden in gestructureerde waarden kent C zes operatoren om met bitwaarden van integer typen te werken. De zes bitoperatoren ziet u in tabel 17- 1. Categorie
Bitoperator
Symbool
Bitoperatoren:
(unair) bitsgewijs eencomplement bitsgewijs EN bitsgewijs OF bitsgewijs exclusief OF schuif naar links schuif naar rechts
∼ & | ∧ « »
Schuifoperatoren:
Tabel 17-1 Zoals alle operatoren in C hebben de bitoperatoren een prioriteit en een associativiteit, die bepalen hoe expressies waarin deze en andere operatoren voorkomen, worden uitgewerkt. Verder kunnen alle bitoperatoren, behalve de unaire eencomplement-operator ∼, in combinatie met de toekenningsoperator worden gebruikt. Alle bitoperatoren zijn alleen op integer typen toe te passen. Deze operatoren kunnen dus niet op float of double worden toegepast. Wij zullen ons hier beperken tot een machine met een 16 bits tweecomplement-representatie voor een int van normale lengte. Voor andere architecturen werken de operatoren ongeveer gelijk. De operator ∼, de eencomplement-operator, berekent het bitsgewijze tegendeel van het (enige) operand. Op het operand zijn de gebruikelijke unaire conversies van toepassing. Elke bit in de binaire representatie van het resultaat is het tegendeel of complement van de bit in het operand.
1
Als de variabele t de decimale waarde 12 heeft, is de binaire representatie: 0000000000001100 Dan heeft ∼t de representatie 1111111111110011 De tweecomplementwaarde van dit resultaat is equivalent met de decimale waarde -13. De bitoperatoren EN (&), OF ()en exclusieve OF (∧) zijn operatoren met twee operanden. Elk operand wordt in termen van zijn binaire representatie behandeld. Elke bit van het resultaat wordt berekend door de betreffende operator op de corresponderende bits van de operanden uit te voeren. De semantiek van deze drie operatoren ziet u in tabel 17-2. x 0 0 1 1
y 0 1 0 1
x&y 0 0 0 1
x y 0 1 1 1
x ∧y 0 1 1 0
Tabel 17-2 Uitgaande van de declaraties en initialisaties int p = 123, q = -17; geeft tabel 17-3 een aantal expressies, de binaire representatie van het resultaat van de expressie en de daarmee overeenkomende decimale waarde. Expressie p q p&q pq p∧q
Binaire representatie Decimale waarde 0000 0000 0111 1011 123 1111 1111 1110 1111 -17 0000 0000 0110 1011 107 1111 1111 1111 1111 -1 1111 1111 1001 0100 -108
Tabel 17-3 Om een gewenste groep bits uit de waarde van een expressie te filteren, kan een masker worden gebruikt. De int constante 3 heeft bijvoorbeeld de binaire representatie 0000 0000 0000 0011 2
en kan met de bitoperator EN worden gebruikt om de twee minst significante bits van een int expressie te bepalen. Zo kent de expressie y = x & 3; aan y de meest rechtse (minst significante) twee bits van de waarde van de integer variabele x toe. Als x de waarde 17 heeft (binair 0000000000010001), dan krijgt y de waarde 1 (binair 0000000000000001). Om de waarde van een bepaalde groep bits uit de waarde van een expressie te bepalen, gebruiken we een masker met enen in op de gewenste bitposities en nullen op de andere. De hexadecimale constante 0x30 is bijvoorbeeld een masker voor de bits 5 en 6 van rechts. Om de minst significante byte van een 16-bits integer op nul te zetten, kunnen we het masker 0xFF00 gebruiken. Om ervoor te zorgen dat de code goed werkt, ongeacht de lengte van een integer, kunnen we het bitsgewijze complement gebruiken om het noodzakelijke masker te maken: linker-byte = woord & (-OxFF) Tenslotte zijn er de schuifoperatoren. Het zijn operatoren met twee integer operanden. Het rechter operand wordt naar een int geconverteerd. Het type van het resultaat is gelijk aan dat van het linker operand. De operator « schuift de binaire representatie van het linker operand zoveel plaatsen naar links als het rechter operand aangeeft. Aan de rechterkant wordt het resultaat met nullen aangevuld. De operator » schuift de binaire representatie van het linker operand zoveel plaatsen naar rechts als het rechter operand aangeeft. Hoe de vrijkomende bits aan de linkerkant eruitzien, hangt van de machine af. Als het linker operand geen teken heeft, wordt de linkerkant met nullen aangevuld. Als het linker operand wel een teken heeft, is het aan de implementator te kiezen of er links nullen of enen komen te staan. In sommige implementaties zijn het altijd nullen; in andere zijn het kopieën van de tekenbit geheel links. Het naar rechts schuiven van een waarde met teken is dus zeer slecht overdraagbaar en moet daarom vermeden worden. In tabel 17-4 ziet u een aantal expressies met de binaire representatie van het resultaat en de decimale waarde daarvan. Er is van uitgegaan dat de integer variabele p de decimale waarde 123 heeft. Expressie
Binaire representatie Decimale waarde
p p«4 p»2 (p»2) & 0xF
0000000001111011 0000011110110000 0000000000011110 0000000000001110
123 1968 30 14
Tabel 17-4
3
Bitexpressies kunnen worden gebruikt voor het comprimeren van data, waardoor minder geheugen nodig is. Op een machine waarop een unsigned int 32 bits beslaat, kunnen vier bytes in één woord worden ingepakt. De functie pak gebruikt de bitoperatoren om bytes te in te pakken: unsigned int pak (char a, char b, char c, char d) { unsigned int gepakt; gepakt = a; gepakt = (gepakt « 8) b; gepakt = (gepakt « 8) c; gepakt = (gepakt « 8) d; return (gepakt); } De vier bytes in een ingepakte unsigned integer kunnen weer worden verkregen met de functie pakuit: #define MASKER
0XFF
void pakuit (unsigned p, char *a, char *b, char *c, char *d) { *a = p & MASKER; *b = (p » 8) & MASKER; *c = (p » 16) & MASKER; *d = (p » 24) & MASKER; }
4
18.3 De goto-statement We besluiten onze behandeling van de programmeertaal C met de enige statement die nog over is. Met de goto-statement kunnen we de besturing van het ene naar het andere deel van een functie laten gaan. De goto-statement heeft de syntaxis goto label; waarin label een identifier is en goto een gereserveerd sleutelwoord. Labels worden niet gedeclareerd zoals variabelen. De label-identifier in een gotostatement moet gelijk zijn aan een label bij een statement in dezelfde functie. Een label wordt in feite gedeclareerd bij de statement waarbij de label hoort. In een gelabelde statement staat de label vóór de statement, ervan gescheiden door een dubbele punt: label : statement Als een goto-statement wordt uitgevoerd, gaat de besturing onmiddellijk naar de statement waar de gelijke label voor staat. Voorbeelden van gelabelde statements zijn: telop : a = b + c + d; fout : printf("Fout tijdens uitvoering\n"); Voor een statement kunnen meerdere labels staan: fout : herstel : breekaf : exit(1); Dankzij het vrije formaat van C kunnen we dit voorbeeld ook zo schrijven: fout : herstel : breekaf :
exit(1);
Ook de lege statement kan gelabeld worden: niets : /* lege statement */ ; We hebben alle programma's in dit boek kunnen schrijven met alleen de besturingsstructuren opeenvolging, selectie en iteratie. Toch kunnen er situaties zijn die bepaalde aspecten van het programmaontwerp moeilijk maken als alleen deze drie structuren kunnen worden gebruikt. Een goed voorbeeld daarvan is het controleren van de geldigheid van invoer. Neem bijvoorbeeld een functie om de elementen van een driedimensionale integer array uit een file te lezen. Zonder controle op de invoer kan de functie er zo uitzien:
5
void input3d(fp, matrix, rijen, kolommen, vlakken) FILE *fp; int matrix[][KOLOMMEN][VLAKKEN]; int rijen, kolommen, vlakken; { int i, j, k; for (i = 0; i < rijen; i++) for (j = 0; j < kolommen; j++) for (k = 0; k < vlakken; k++) fscanf (f p, "%d", &matrix[ i l[j][k]); } Een robuust programma controleert zijn invoer en doet iets speciaals als er een fout wordt gedetecteerd. In ons voorbeeld kunnen we bijvoorbeeld controleren of het eind van de file is bereikt. De functie fscanf levert EOF af als het eind van de file is bereikt. Met deze waarde, een logische vlag en extra condities in de for-statement komen we tot een nieuwe versie voor het programma. Als het eind van de file wordt aangetroffen, wordt er een foutrnelding gegenereerd en eindigt het programma. void input3d(fp, matrix, rijen, kolommen, vlakken) FILE *fp; int matrix[] [KOLOMMEN] [VLAKKEN]; int rijen, kolommen, vlakken; { int i, j, k; Boolean eof_vlag = FALSE; for (i = 0; i < rijen && !eof _vlag; i++) for (j = 0; j < kolommen && !eof_vlag; j++) for (k = 0; k < vlakken && !eof_vlag; k++) eof_vlag = (fscanf(fp, "%d", &matrix[il[j][k]) == EOF); if (eof_vlag) fprintf(stderr, "Onverwachte eof\n"); exit(1); } Door de extra controles ziet de oplossing er wat onhandig uit. Een fatsoenlijker beëindiging krijgen we door vanuit de geneste lussen met een goto-statement naar een punt in de functie te springen waar iets aan de fout kan worden gedaan.
6
void input3d(fp, matrix, rijen, kolommen, vlakken) FILE *fp; int matrix[] [KOLOMMEN] [VLAKKEN]; int rijen, kolommen, vlakken; { int i, j, k; for (i = 0; i < rijen; i++) for (j = 0; j < kolommen; j++) for (k = 0; k < vlakken; k++) if (fscanf(fp, "%d”, &matrix[i][j][k]) == EOF) goto breekaf; return; breekaf : fprintf(stderr, "Onverwachte eof\n"); exit(1); } Met een goto-statement kan in C de besturing naar elke andere statement in dezelfde functie worden overgedragen. Bepaalde manieren van springen kunnen bijzonder verwarrend zijn en moeten daarom worden vermeden. Een voorbeeld is springen naar een plek ergens midden in een samengestelde statement, waarbij de initialisatie van variabelen die boven aan de samengestelde statement worden gedeclareerd, worden overgeslagen: … … goto midden; … … { int som = 0; deler = l; … … midden: … … }
7
Andere vormen van springen die beter kunnen worden vermeden, zijn: 1. springen naar een plaats in het then-deel of het else-deel van een if-statement van buiten de if -statement; 2. springen naar een plaats in de body van een switch-statement; 3. springen naar een plaats in de body van een iteratiestatement. Het ongebreideld gebruik van de goto-statement moet worden vermeden. Het feit dat selectie en herhaling kunnen worden nagemaakt met if - en goto-statements, betekent niet dat dit een betere manier is. De sleutelwoorden while, for en do maken duidelijk dat het om herhaling gaat; if en switch duiden op selectie. Als we deze woorden in een programma zien staan, weten we onmiddellijk om welke vorm van besturing het gaat. Kijkt u bijvoorbeeld eens naar programma 18-5, dat hetzelfde doet als programma 6-14. U ziet dat de herhaling nu is geïmplementeerd met een combinatie van if en goto, evenals de tests. De logica van het programma is veel minder duidelijk geworden. Programma 18-5 Een stuk tekst bestaat uit een reeks karakters die over een aantal regels loopt en door een punt wordt afgesloten. Tel het aantal 'woorden' in de tekst. Een woord is een karakterstring, van andere woorden gescheiden door witruimte (spaties, tabs en newlines). #include
<stdio.h>
#define #define #define #define
PUNT SPATIE TAB NEWLINE
‘.’ ‘‘ ‘\t’ ‘\n’
#define #define
FALSE TRUE
0 1
main() { char c; int woorden int inwoord
0; FALSE;
loop: c = getchar(); if (c == PUNT)
/* /* /*
invoerkarakter regelteller woordindicator
*/ */ */
/* /*
haal volgend karakter afsluiten?
*/ */ 8
goto einde;
/*
ja - beëindig programma
if (c == SPATIE c TAB c == NEWLINE){ /* witruimte? inwoord = FALSE; /* buiten een woord goto lus; /* haal volgend karakter } if (! inwoord){ /* binnen een woord? inwoord = TRUE; /* nu in een woord woorden++; /* verhoog teller } goto lus; /* opnieuw voor volgend karakter
*/
*/ */ */ */ */ */
einde: printf("Aantal woorden is %d\n", woorden); } Doordat de goto-statement de programmeur in staat stelt de structuur die wordt aangebracht door while, if, enzovoort, te vernielen, is het een gevaarlijke statement. De goto-statement dient alleen in uitzonderlijke omstandigheden te worden gebruikt, als de vereiste vorm van besturing niet redelijk kan worden geformuleerd met de in hoofdstuk 6 ingevoerde besturingsprimitieven. Dit komt zo zelden voor, dat de goto-statement vrijwel kan worden vergeten. Dat voorkomt ook de uit deze statement voortvloeiende problemen.
9
