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 2024 ExpyDoc
