Operieren mit der kleinsten Informationseinheit, dem Bit
Ein Bit ist die kleinste Informationseinheit in der EDV und kennt lediglich 2 Werte: 1 oder 0. Die nächstgrößte Informationseinheit ist das Byte, dahinter verbergen sich genau 8 Bit. Dieser Artikel befasst sich mit einfachen Rechenoperationen, welche beim Rechnen mit Bits gebräuchlich sind.
1 & 1 - das ist die Schreibweise für bitweises AND, 1 | 1 - das ist die Schreibweise für bitweises OR. Bitweises OR/AND auf einzelne Bits angewandt ergibt:
1 & 1 -> 1
1 | 1 -> 1
1 & 0 -> 0
1 | 0 -> 1
0 & 0 -> 0
0 | 0 -> 0
Bitweises OR/AND sind in dieser Betrachtung sogenannte Bitoperatoren. Im Verlauf dieses Artikels werden noch weitere Bitoperatoren vorgestellt und auch gezeigt, wie diese in der Scriptsprache PERL verwendet werden.
Was die Ausführung von Bit - Operationen betrifft, ist PERL sehr mächtig, gleich ob den Bit - Operatoren einzelne Bits oder ganze Zahlen übergeben werden. Untenstehende Funktion printf() zeigt das sehr anschaulich:
printf(
qq(
Wie PERL ein bitweises AND abarbeitet ( 255 & 10 ):
%08b
%08b
--------
%08b
), 255, 10, ( 255 & 10 )
);
Ausgabe von printf():
Wie PERL ein bitweises AND abarbeitet ( 255 & 10 ):
11111111
00001010
--------
00001010
Es ist nun an der Zeit, die Frage zu stellen: Wozu dies alles!? Die Antwort schlicht und einfach: Mit Bits ist immer dann zu operieren, wenn Zahlen nicht mehr auf Byte - Ebene abgebildet werden sollen, sondern in kleineren, selbst definierten Speichereinheiten, also auf Bit - Ebene.
In Datenbanken wie z.B. PostgreSQL gibt es Datentypen für Integer (Ganzzahlen). Bei PostgreSQL ist der kleinste Integer - Typ: int2 (smallint) und für diesen Datentyp reserviert die DB - Engine 2 Bytes, das sind 2 * 8 Bit => 16 Bit. Wenn 4 Zahlen gespeichert werden sollen, die lediglich jeweils 4 Bit an Platz benötigen, wäre es doch Verschwendung, wenn für jede dieser Zahlen ein eigenes Feld mit 16 Bit reserviert würde, denn diese 4 Zahlen passen komplett ein ein 16 Bit - Feld vom Typ smallint.
Selbst bei der heutzutage verfügbaren Hardware können bei bestimmten Aufgabenstellungen die Grenzen von Massenspeichergeräten erreicht werden, nämlich dann, wenn sehr viele kleine Dateneinheiten über einen längeren Zeitraum gespeichert werden müssen.
Aber nicht nur beim Scripten für Datenbankanwendungen, auch in anderen Fällen können Bit - Operatoren sehr hilfreich sein. Beispielsweise in Berechnungen mit IPv4 - Adressen. Doch davon später.
Die folgende Fallstudie beschränkt sich der Übersicht halber auf einen Workaround für 2 Dezimalzahlen, die in einem Byte, 8 Bit, abgelegt werden sollen.
Angenommen, es bestünde die Aufgabe, in einer Binärzahl die ersten 4 Bits und die letzten 4 Bits mit verschiedenen, oder besser gesagt: unabhängigen Zahlen zu belegen. Schnell einmal mit dem Taschenrechner nachgeprüft: 4 Bit in Dezimal sind 15, in 4 Bit ist also eine Zahl von 0..15 darstellbar, es ergeben sich somit 16 verschiedene Möglichkeiten innerhalb dieser 4 Bit.
Aufgabe: Speichern von 2 unabhängigen Zahlenwerten (angenommen: 7 und 3) in einem Byte (8 Bit).
Für jeden Zahlenwert stehen 4 Bit zur Verfügung:
|
|_|_|_|_|_|_|_|_|
| |
| |____ hier in diesen 4 Bits soll eine dezimale 3 gespeichert werden
|____________ hier in diesen 4 Bits soll eine dezimale 7 gespeichert werden
Beide Zahlen in Dualschreibweise:
7 -> 0111
3 -> 0011
Das Ergebnis hat also wie folgt auszusehen:
01110011 links die 7, rechts die 3
Beispiel mit der PERL - Funktion printf():
printf("04b \n", 7, 3); # 01110011
Wie das Ergebnis auszusehen hat ist nun bekannt. Doch wie kommen die Zahlen in dieses Byte, diese 8 Bit hinein? Dazu sei an dieser Stelle der Shift - Operator vorgestellt.
Zum besseren Verständnis:
Das Ergebnis - Byte ist zunächst mit Nullen gefüllt:
00000000
Nachdem die 7 dazugekommen ist, stehen die 4 Bits jedoch noch nicht am rechten Fleck:
00000111
Um im Ergebnisbyte die 7 an den richtigen Platz zu bekommen, müssen deren Bits um 4 Bit
nach links verschoben werden.
Somit resultiert:
01110000
Und wenn jetzt noch die 3 dazukommt, ergibt sich auch das bereits bekannte Ergebnis:
01110011
Dieses Bitweise verschieben, das funktioniert mit dem Shift - Operator. Es gibt Rechts-Shift >> und Links-Shift << wobei in PERL die Anzahl der bitweisen Verschiebung rechts neben dem Shift - Operator notiert wird. Nun zur praktischen Anwendung der Bit - Operatoren in PERL, es ist nicht schwer, das zu verstehen:
$decZahlA = 7;
$decZahlB = 3;
Das Ergebnisbyte ergibt sich mit (7 shift-left 4) plus 3:
$myByte = ( $decZahlA << 4 ) + $decZahlB;
printf("Kontrollausgabe binary: %08b, decimal: %d \n", $myByte, $myByte);
printf gibt die Binärzahl achtstellig (vorn mit 0 aufgefüllt) und auch die Dezimalzahl aus:
Kontrollausgabe binary: 01110011, decimal: 115
OK, das war die Pflicht. Nun kommt die Kür: Das Zurückermitteln der einzelnen Zahlen aus dem Ergebnisbyte. Dazu wird eine eine geeignete Maske benötigt. Bildlich gesprochen wird diese Maske über das Bitmuster (Ergebnisbyte) gelegt und so ergeben sich die gesuchten Einzelwerte.
Zum Verständnis des Masken - Tricks siehe untenstehende Schemata:
Gesucht wird der Wert aus der rechten Hälfte, hierzu die passende Maske:
00001111
Die Maske wird über das Ergebnisbyte gelegt und die Bits mit AND verknüpft
01110011
00001111
--------
00000011
Überall da, wo in der Maske eine 1 steht, ergibt sich das gesuchte Bit aus dem Ergebnisbyte, wo
die Maske eine 0 hat, werden die Bits ausgeblendet. Daher auch der Begriff Bitmaske.
Was nach dem Anwenden der Maske vom Ergebisbyte übrigbleibt,
ist die Binärzahl 00000011 und das ist die gesuchte 3.
Zum Ermitteln der Zahl aus der linken Hälfte wird die Maske herumgedreht und analog angewandt:
01110011
11110000
--------
01110000
Was hierbei übrig bleibt, ist allerdings nicht das gewünschte Ergebnis.
Um an die gesuchte Zahl zu gelangen, müssen die Bits im Ergebnis 4 Mal nach rechts geschoben werden.
Erst das ergibt dann 00000111, und damit die gesuchte Zahl 7.
Das Ganze in PERL umgesetzt sieht recht einfach aus:
printf("Rechte Haelfte vom Ergebnisbyte: %d \n", (115 & 0x0F)); # 3
printf("Linke Haelfte vom Ergebnisbyte: %d \n", ((115 & 0xF0) >> 4)); # 7
Erläuterungen siehe untenstehend:
printf("Rechte Haelfte vom Ergebnisbyte: %d \n", (115 & 0x0F));
Platzhalter fuer decimal_________| | | |_______ eine 00001111 Maske in Hex
| |___________ bitweises AND
das Ergebnisbyte 01110011 in decimal_______|
Es mag verblüffend aussehen, dass Hex - Zahlen und Dezimalzahlen bunt durcheinander mit
bitweisen AND verknüpft werden. PERL interpretiert das jedoch vollkommen richtig.
Doch warum die Maske in Hex? Die Antwort: Einfache Schreibweise und leicht zu merken!
Beispiele:
Hex -> Binär
0xF -> 1111
0xFF -> 11111111
0x0F -> 00001111
0xF0 -> 11110000
printf("Linke Haelfte vom Ergebnisbyte: %d \n", ((115 & 0xF0) >> 4));
| |_________ 4 shift right
|________________ eine 11110000 Maske in Hex
Dieses printf() genauso wie weiter oben, lediglich, dass hier der Shift-Operator noch dazukommt.
Drei kleine Übungen sollen das Verständnis zum Rechnen mit IP - Adressen und Bit - Operatoren vertiefen helfen: 1. Umrechnen einer IP - Adresse in einen numerischen Wert, 2. das Zurückrechnen der einzelnen Oktetten in die gebräuchliche dezimale Darstellung und als 3. Übung die Ermittelung der Netzadresse aus einer gegebenen IP - Adresse und Netzmaske. Zum Rechnen mit IP - Adressen gibt es mittlerweile eine ganze Reihe von Modulen und Berechnungsmethoden, aber dieser Artikel soll ja die Basics vermitteln.
Gewöhnlich werden IPv4 - Adressen in der Oktetten - Schreibweise dargestellt, das heißt: eine IP - Adresse wie z.B. die 192.168.1.1 ist aufgeteilt in 4 Oktetten => 4 * 8 Bit wobei diese Oktetten der besseren Übersicht wegen mit Punkten getrennt dargestellt werden:
In PERL:
printf("%08b.%08b.%08b.%08b \n", 192, 168, 1, 1);
11000000.10101000.00000001.00000001 # was printf() ausgibt
192. 168. 1. 1 # was es bedeutet...
Zur 1. Übung dient eine IP - Adresse im LAN, nach dem Umrechnen kann so gleich mit dem ping - Kommando geprüft werden, ob richtig gerechnet wurde. Als IP - Adresse sei die 10.0.0.2 angenommen und in PERL notiert:
$ipNum =
( 10 << 24 )
+ ( 0 << 16 )
+ ( 0 << 8 )
+ 2;
print "$ipNum\n"; # 167772162
Probe mit ping:
D:\>ping 167772162
Ping wird ausgeführt für 10.0.0.2 mit 32 Bytes Daten:
Antwort von 10.0.0.2: Bytes=32 Zeit=2ms TTL=64
...
Die Umrechnung erwies sich also als richtig. Die 10 muss, um in die Oktette ganz links zu kommen, 24 mal um ein Bit nach links bewegt werden, die erste 0 um 16 Bit, die zweite 0 um 8 Bit und schließlich kommt noch die die 2 hinzu (10.0.0.2 => 4 Oktetten in 32 Bit).
2. Übung: Welche einzelnen Dezimalzahlen stecken in den 4 Oktetten einer IP - Adresse? Bekannt ist der numerische Wert $ipNum der kompletten IP - Adresse. Zur Anwendung kommen die in der Fallstudie weiter oben gezeigten Bitoperatoren bitweises AND und shift right.
$ipNum = 167772162;
printf("Oktette 1: %d \n", (($ipNum & 0xFF000000) >> 24));
printf("Oktette 2: %d \n", (($ipNum & 0x00FF0000) >> 16));
printf("Oktette 3: %d \n", (($ipNum & 0x0000FF00) >> 8));
printf("Oktette 4: %d \n", ($ipNum & 0x000000FF) );
Oktette 1: 10
Oktette 2: 0
Oktette 3: 0
Oktette 4: 2
Selbstverständlich kann dies alles auch mit einer einzigen printf() - Anweisung ausgegeben werden,
so unübersichtlich ist das nun auch wieder nicht, ganz im Gegenteil:
printf(
"%d.%d.%d.%d\n",
(($ipNum & 0xFF000000) >> 24),
(($ipNum & 0x00FF0000) >> 16),
(($ipNum & 0x0000FF00) >> 8),
( $ipNum & 0x000000FF)
);
Die Festlegung dass die bitweise AND Verknüpfung von IP - Adresse und Netzmaske die Netzwerkadresse ergibt, zeigt die Anwendung des bitweisen AND in der 3. Übung:
$ipad = '10.1.1.1';
$mask = '255.255.255.0';
$n = 10 & 255;
$e = 1 & 255;
$t = 1 & 255;
$z = 1 & 0;
print "Netzadresse: $n.$e.$t.$z \n";
# Netzadresse: 10.1.1.0
Zum Schluss sei noch eine kompakte Funktion vorgestellt, die aus einer gegebenen IP - Adresse und Netzmaske die Netzadresse und die Broadcastadresse ermittelt. Die Funktion netX() ermittelt zunächst aus den übergebenen Argumenten jeweils einen 32 Bit unsigned Integer, also numerische Werte von IP - Adresse und Netzmaske ($u32 und $msk).
Die Netzadresse ergibt sich wie gehabt, als eine bitweise AND - Verknüpfung von IP - Adresse und Netzmaske, die beide numerisch vorliegen. Zum Berechnen der Broadcastadresse werden IP - Adresse und Netzmaske mit einem bitweisen OR verknüpft, wobei die Bits der Netzmaske vor dieser Operation mit dem Komplementäroperator (~ ein weiterer Bit - Operator, siehe Zusammenfassung) negiert wurden.
Infolge einer konsequenten Anwendung der PERL - Funktionen pack() und unpack() ergeben sich im Code weitere Vereinfachungen:
my $ipAddr = '10.0.0.2';
my $netMask = '255.255.255.0';
my ($netAddr, $broadCastAddr) = netX($ipAddr, $netMask);
printf(
qq(
IpAddr: %s
NetMask: %s
NetAddr: %s
BroadCastAddr: %s
),
$ipAddr, $netMask, $netAddr, $broadCastAddr
);
# Beispiel: ($netAddr, $broadCastAddr) = netX($ipAddr, $netMask);
sub netX{
my ($ip,$nm) = @_;
my $u32 = unpack "N", pack "CCCC", split /\./, $ip; # unsigned Integer
my $msk = unpack "N", pack "CCCC", split /\./, $nm; # 32 Bit
return(
join(".", (unpack "CCCC", pack "N", $u32 & $msk)),
join(".", (unpack "CCCC", pack "N", $u32 | ~$msk))
);
}
__END__
IpAddr: 10.0.0.2
NetMask: 255.255.255.0
NetAddr: 10.0.0.0
BroadCastAddr: 10.0.0.255
| & | Bitweise AND |
| | | Bitweise OR |
| << | Left - Shift |
| >> | Right - Shift |
| ~ | Komplement (alle Bits werden negiert) |
| ^ | Exclusiv OR (ausschließendes ODER) |
Datenschutzerklärung: Diese Seite dient rein privaten Zwecken. Auf den für diese Domäne installierten Seiten werden grundsätzlich keine personenbezogenen Daten erhoben. Das Loggen der Zugriffe mit Ihrer Remote Adresse erfolgt beim Provider soweit das technisch erforderlich ist. sos@rolfrost.de.