Kap 9. Bitoperationen und -strukturen 9.1 Anwendung von Bits Im Gegensatz zu den üblicherweise Byte-orientierten Daten gibt es auch Bit-Anwendungsbeispiele Statusanzeigen bei Ein-/Ausgabe (Stream-Klassen) Zugriffsrechte auf Dateien Abfrage von Ports Status-/Steuerungsangaben für Maschinen oder Anlagen Betriebssystemprogramme/Router/Gerätetreiber Grafik: Bitmaps, Farbtiefe (z.B. bis 8 bpp=Bits per Pixel bei GIF) Konvertierung von Formaten/Komprimierung Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 2 9.2 Bitoperatoren & | ^ ~ << >> UND 0&0 0&1 1&0 1&1 Ergebnis 0 0 0 1 bitweises UND bitweises ODER bitweises exklusives ODER (XOR) Komplement NICHT NICHT Ergebnis Links-Shift ~0 1 Rechts-Shift ~1 0 ODER Ergebnis 0|0 0 0|1 1 1|0 1 1|1 1 XOR 0^0 0 ^1 1^0 1^1 Ergebnis 0 1 1 0 Die Operanden müssen von ganzzahligem Typ sein. Die Bitoperatoren sollte man nicht mit den logischen Operatoren && bzw. || verwechseln, welche stets auf die gesamte Zahl wirken und nicht auf die einzelnen Bits-> Beispiel folgt. Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 3 Operatoren – prinzipielle Wirkungsweise Sei a = 1101 0101 0000 0000 b= 1111 0000 0000 0000 a&b bitweises UND Ergebnis a op b 1101 0000 0000 0000 Nur dort wo in beiden Variablen eine 1 ist, steht auch im Ergebnis eine 1. Sei a = 1010 0011 0000 0000 (entspricht bisher true) b= 0101 1100 0000 0000 (entspricht bisher true) a&b bitweises UND 0000 0000 0000 0000 a&&b logisches UND 0000 0000 0000 0001 Damit entspricht a&b false, wohingegen a&&b true ist !! Die Abfragen if ( a&b) bzw. if ( a&&b) führen in diesem Fall zu unterschiedlichen Ergebnissen !!! -> Tippfehler ist schwer zu entdecken Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 4 Operatoren – prinzipielle Wirkungsweise Sei a = 1101 0101 0000 0000 b= 1111 0000 0000 0000 Ergebnis a op b a|b bitweises ODER 1111 0101 0000 0000 Nur dort wo in beiden Variablen eine 0 ist, steht auch im Ergebnis eine 0. a^b bitweises exklusives ODER (XOR) 0010 0101 0000 0000 Nur dort wo in beiden Variablen unterschiedliche Bits sind, steht auch im Ergebnis eine 1. ~a Komplement NICHT Alle Bits werden invertiert. Dr. Norbert Spangler / Grundlagen der Informatik 0010 1010 1111 1111 11.06.2016 5 Shift-Operatoren – prinzipielle Wirkungsweise Sei a = 1101 0101 0000 0000 a<<2 a>>2 Links-Shift ( um 2 Bits) Rechts-Shift (um 2 Bits) aber auch 0101 0100 0000 0000 0011 0101 0100 0000 1111 0101 0100 0000 Die weggeschobenen Bits entfallen. Beim Links-Shift wird stets mit Nullen aufgefüllt. Beim Rechts-Shift ist entscheidend, ob die Variable - vom Typ unsigned ist: es werden links Nullen aufgefüllt - Vom Typ signed ist : es wird das Vorzeichen aufgefüllt Dies ist jedoch compilerabhängig. Anmerkung: ein Links-Shift um 1 entspricht einer Multiplikation mit 2, ein Rechts-Shift analog einer ganzzahligen Division durch 2. Diese Operationen sind schneller als die übliche Multiplikation. Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 6 Shift-Operatoren – Beispiel void main() { short a=0x8000,b=a>>2;//1 aufgefuellt da negativ cout<<a<<" "<<b<<endl; short c=0x4000,d=c>>2;//0 aufgefuellt da positiv cout<<c<<" "<<d<<endl; unsigned short e=0x8000,f=e>>2;//0 aufgefuellt da unsigned cout<<e<<" "<<f<<endl; } Entspricht Division durch 4 Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 7 9.3 Elementare Aufgaben Typische Aufgaben im Umgang mit Bits sind Ein spezielles Bit einer Variablen a - abfragen - auf 0 setzen - auf 1 setzen - umkehren ( 0-> 1 bzw. 1-> 0) Dies lässt sich erweitern auf mehrere Bits der Variablen. Prinzipielle Vorgehensweise: Man bildet eine Variable maske ( Anzahl der Bits wie bei der Variablen a) und verknüpft die Variablen a und maske mit einem Bitoperator, um das gewünschte Ergebnis zu erhalten: Ergebnis = a op maske Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 8 Konstruktion von Masken Masken lassen sich am besten in hexadezimaler Schreibweise angeben short maske=0xE303; Damit ist maske = 1110001100000011 E 3 0 3 Die Berechnung des Zahlenwerts ist eher mühsam: void main() { short maske=0xE303; cout <<maske<<" entspricht "<< hex <<uppercase<< maske<<endl; } Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 9 Konstruktion von Masken Masken mit nur einer 1 kann man auch leicht durch Shift-Operationen erzeugen. Beispiel: maske mit einer 1 an der Position n von rechts. n ist einzulesen. #include <iostream> #include <iomanip> using namespace std; void main() { int n; cout<<" Position der 1: "; cin>>n; short maske=1<<n; cout <<maske<<" entspricht "<< hex <<setw(4)<<setfill('0')<<uppercase<< maske<<endl; } Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 10 9.4 Bits abfragen Ist x ein Bit so liefert die Operation x&0 stets 0 x&1 stets x Will man also in einer Variablen ein spezielles Bit abfragen, so muss man sich eine Maske für den & Operator konstruieren, welche an der gewählten Position eine 1 hat und an allen anderen eine 0. Wenn also das 3. Bit (von links) abgefragt wird muss maske=0010 0000 0000 0000 sein, also maske = 0x2000 oder maske=1<<13. void main() { int a; cout<<"Zahl eingeben "; cin>>a; short maske=1<<13; if ( a & maske ) cout<<"Stelle ist 1 "<<endl; else cout<<"Stelle ist 0 "<<endl; } Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 11 9.5 Bits 0 setzen Ist x ein Bit so liefert die Operation x&0 stets 0 x&1 stets x Will man also ein spezielles Bit einer Variablen a auf 0 setzen, so muss man sich eine Maske als Operand für den & Operator konstruieren, welche an der gewählten Position eine 0 hat und an allen anderen eine 1. Wenn also das 3. Bit (von links) 0 gesetzt werden soll muss maske=1101 1111 1111 1111 sein. Allgemein: Wo in der Maske eine 0 steht, wird das Bit von a 0 gesetzt Wo in der Maske eine 1 steht, bleibt das Bit von a erhalten Sei a maske a&maske = 1101 0101 0010 0100 = 1111 1111 0000 0000 = 1101 0101 0000 0000 Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 12 9.6 Bits 1 setzen Ist x ein Bit so liefert die Operation x|0 stets x x|1 stets 1 Will man also ein spezielles Bit einer Variablen a auf 1 setzen, so muss man sich eine Maske als Operand für den | Operator konstruieren, welche an der gewählten Position eine 1 hat und an allen anderen eine 0. Wenn also das 3. Bit (von links) 1 gesetzt werden soll muss maske=0010 0000 0000 0000 sein. Allgemein: Wo in der Maske eine 1 steht wird das Bit von a 1 gesetzt Wo in der Maske eine 0 steht bleibt das Bit von a erhalten Sei a maske a|maske = 1101 0101 0010 0100 = 1111 1111 0000 0000 = 1111 1111 0010 0010 Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 13 9.7 Bits invertieren Ist x ein Bit so liefert die Operation x^0 stets x x^1 stets ~x Will man also ein spezielles Bit einer Variablen a invertieren, so muss man sich eine Maske als Operand für den ^ Operator konstruieren, welche an der gewählten Position eine 1 hat und an allen anderen eine 0. Wenn also das 3. Bit (von links) 1 gesetzt werden soll muss maske=0010 0000 0000 0000 sein. Allgemein: Wo in der Maske eine 1 steht wird das Bit von a 1 gesetzt Wo in der Maske eine 0 steht bleibt das Bit von a erhalten Sei a = 1101 0101 0010 0100 maske = 1111 1111 0000 0000 a^maske = 1111 1111 0010 0010 Schreibt man speziell ~ a so werden alle Bits von a invertiert Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 14 Zusammenfassung a & maske setzt alle Bits von a 0, die in maske 0 sind a | maske setzt alle Bits von a 1, die in maske 1 sind a ^ maske invertiert alle Bits von a, die in maske 1 sind ~a invertiert alle Bits von a Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 15 9.8 Sonstige Aufgaben Beispiele Anzeige der Bits eines Typs Berechnung der Anzahl der Bits eines Typs Bestimmung von Parity-Bits (entspricht einer 1-Bit Prüfziffer) damit die Anzahl aller Bits gerade ist ( even Parity) die Anzahl aller Bits ungerade ist ( odd Parity) Dies dient zur Fehlererkennung bei Datenübertragungen Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 16 Anzeige der Bits Es soll eine Funktion bitToString geschrieben werden, welche die Bits eines Typs in einem String bereitstellt. Da der Algorithmus typunabhängig ist empfiehlt sich ein Template. Algorithmus: Eine Schleife die das erste Bit bestimmt im String anhängt das erste Bit beseitigt bis alle Bits verarbeitet sind Erforderlich: Maske mit 1 an vorderster Stelle Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 17 Anzeige der Bits template <typename T> string bitToString(T p) { string bits; int s=sizeof(T);//Anzahl der Bytes von T T m=0x80;//Maske mit 1 an Bit 7 m=m<<(s-1)*8;//1 an erster Stelle for ( int i=0;i<8*s;i++)//alle Bits { if ( m&p )//vorderstes Bit abfragen bits+='1'; else bits+='0'; p=p<<1;// um 1 nach links verschieben } return bits; } Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 18 Anzeige der Bits void main() { char c='5'; short s=5; int i=5,j=-5; cout<<c<<" = "<<bitToString(c)<<endl; cout<<s<<" = "<<bitToString(s)<<endl; cout<<i<<" = "<<bitToString(i)<<endl; cout<<j<<" = "<<bitToString(j)<<endl; } Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 19 Anzahl der Bits einer Zahl void main() { int anzahlBits(unsinged short); short i; cin>>i; cout<<endl<<i<<" hat "<<anzahlBits(i)<<" gesetzte Bits"; } int anzahlBits(unsigned short n) { int summe=0; short maske=1;// entspricht 00…001 while ( n!=0 ) { if ( n & maske )//letztes Bit ist 1 summe++; n=n>>1;//Rechtsshift um 1 } return summe; } Dr. Norbert Spangler / Grundlagen der Informatik 55 = 1101112 11.06.2016 20 Paritybit Es soll eine Funktion parity geschrieben werden, welche das Paritybit (even) für Variablen vom Typ unsigned short bestimmt, d.h. die Zahl aller Bits der Variablen + Parity-Bit ist gerade. Ausgangssituation: kein Bit verarbeitet – Paritybit ist 0 Algorithmus: Solange Bits !=0 vorhanden nächstes Bit prüfen falls Bit=0 -> keine Änderung =1 -> Paritybit invertieren Erforderlich: Maske mit 1 an letzter Stelle Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 21 Paritybit unsigned short parity(unsigned short n) { unsigned short par=0;//Paritybit while ( n!=0 ) // noch Einsen vorhanden { par^=(n & 0x0001); n>>=1; } return par; } Bit(n) par neu 0 0 0 0 1 1 1 0 1 1 1 0 entspricht XOR Zusammengesetzte Operatoren op= Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 22 Paritybit void main() { int parity(unsigned short); unsigned short a=1,b=2,c=3; cout<<a<<" hat Paritybit "<<parity(a)<<endl; cout<<b<<" hat Paritybit "<<parity(b)<<endl; cout<<c<<" hat Paritybit "<<parity(c)<<endl; } Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 23 Paritybit/rekursiv int parity(unsigned short n) { if ( n == 0 ) return 0; else return parity(n>>1) ^ (n & 0x0001); } Dr. Norbert Spangler / Grundlagen der Informatik Rest letztes 0 0 0 1 1 0 1 1 par 0 1 1 0 entspricht XOR 11.06.2016 24 Anzahl der Bits Es soll eine Funktion anzahl geschrieben werden, welche die Anzahl der Einsen für Variablen vom Typ unsigned short bestimmt. Ausgangssituation: kein Bit verarbeitet – anzahl ist 0 Algorithmus: Solange Bits !=0 vorhanden nächstes Bit prüfen falls Bit=1 um 1 erhöhen Erforderlich: Maske mit 1 an letzter Stelle. Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 25 Anzahl der Bits //rekursive Variante int anzahlBit(unsigned short n) { if ( n==0 ) return 0; else return anzahlBit(n>>1) + (n & 0x0001); } Naiver Algorithmus – es gibt bessere Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 26 Anzahl der Bits void main() { unsigned short a=8, b=15, c=1000, d=010; int i=5,j=-5; cout<<a<<" = "<<bitToString(a)<<" Anzahl der Bits "<<anzahlBit(a)<<endl; cout<<b<<" = "<<bitToString(b)<<" Anzahl der Bits "<<anzahlBit(b)<<endl; cout<<c<<" = "<<bitToString(c)<<" Anzahl der Bits "<<anzahlBit(c)<<endl; cout<<d<<" = "<<bitToString(d)<<" Anzahl der Bits "<<anzahlBit(d)<<endl; } Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 27 9.5 Bitstrukturen und -container Ein Nachteil der bitweisen Verarbeitung ganzer Zahlen besteht darin, dass einzelne Bits nur über Masken angesprochen werden können und die Bedeutung für die Anwendung nicht klar wird. So lassen sich zwar in einer Variablen vom Typ char 8 Statusbits „verstecken“, es ist jedoch ohne zusätzliche Angaben nicht klar, was beispielsweise das 5. Bit bedeutet. Dies lässt sich mit Bitfeldern besser beschreiben. Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 28 Bitfelder struct Feld { unsigned unsigned unsigned unsigned unsigned unsinged unsigned }; sensor1 :1; sensor2 :1; switch :1; :4; power :1; status :4; id :4; Bitfelder werden als Datenelemente einer Struktur definiert. Die Struktur hier besteht aus 16 Bits. Die ersten 3 Bitfelder sind sensor1,sensor2 und switch. Sie haben je 1 Bit. Die nächsten 4 Bits werden nicht genutzt; Danach folgt das Bitfeld power ( 1 Bit), dann status ( 4 Bits) und id ( 4 Bits). Vorteil: die einzelnen Bits bzw. Bitteile haben Bezeichnungen und können wie bei Strukturen über den Punkoperator angesprochen werden. Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 29 Bitfelder Deklaration: Feld geraet; Zugriff: if ( geraet.sensor1 ) .... geraet.power=0; usw. Die Maximallänge ist ein Speicherwort ( z.B. 4 Bytes) Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 30 Bitset Es gibt eine Containerklasse bitset ( Headerdatei <bitset>), welche Bitmengen beliebiger Länge ermöglicht inkl. zahlreicher Methoden, z.B. für Ein-/Ausgabe und indizierten Zugriff. #include <iostream> #include <bitset> using namespace std; void main() { bitset <4> b; cin>>b; b[2]= ~ b[2]; cout<<b; } 4 Bits << und >> Operator ist überladen Indexoperator ist überladen Dr. Norbert Spangler / Grundlagen der Informatik 11.06.2016 31
© Copyright 2025 ExpyDoc