Bit-Manipulation
Bei Bit-Manipulationen spart man sich viele Abfragen oder Statusvariablen und eignet sich zum Beispiel gut für Vergleiche.
Die Theorie:
Ein Integer besteht aus 32 Bit. Diese Bits können in Binär oder Hexadezimal sehr schön dargestellt werden.
Binär : 11110000111100001111000011110000 Hexadezimal: 0xF0F0F0F0 Dezimal : 4042322160
Im Binärsystem seht jede Ziffer für ein Bit. 1 bedeutet das Bit ist gesetzt und 0 nicht gesetzt. Im Hexadezimalsystem werden vier Bits in einer Ziffer dargestellt. 0x symbolisiert lediglich, dass es sich um eine Hexadezimalzahl handelt.
Folgende Bit – Operatoren werden wir benötigen:
Links schieben : << Rechts schieben: >> UND verknüpfen : & ODER verknüpfen: | Exclusive ODER : ^ Einerkomplement: ~
Links schieben:
Anweisung in Dezimal:
var foo:int = 1<<1;
Die Variable foo hat den Wert 2 nach der Operation, es wird praktisch mal zwei genommen. Aus Binärsicht wird einfach eine 0 von RECHTS hineingeschoben.
Binäredarstellung:
0001 0010
Rechts schieben:
Anweisung in Deziemal:
var foo:int = 2>>1;
Die Variable foo hat den Wert 1 nach der Operation, es wird praktisch durch zwei geteilt. Aus Binärsicht wird einfach eine 0 von LINKS hineingeschoben.
Binäredarstellung:
0010 0001
Hätten wir 1>>1 genommen, wäre die 1 rechts rausgefallen und hätten dann 0 und nicht 0.5, da wir im Integer Bereich arbeiten.
UND verknüpfen:
Anweisung in Dezimal:
var foo:int = 3&1;
Die Variable foo hat den Wert 1 nach der Operation. Bei UND Verknüpfungen ist 1 UND 1 wahr, 1 UND 0 falsch, und 0 UND 0 ebenfalls falsch. D. h. 1&1 = 1, 1&0 = 0 und 0&0 = 0.
Binärdarstellung:
0011 // Dez: 3 0001 // Dez: 1 ---- 0001 // Dez: 1
ODER verknüpfen:
Anweisung in Dezimal:
var foo:int = 2|1;
Die Variable foo hat den Wert 3 nach der Operation. Im Gegensatz du der UND-Verknüpfung ist es immer wahr, sobald eins der Bits 1 ist.
Binärdarstellung:
0010 // Dez: 2 0001 // Dez: 1 ---- 0011 // Dez: 3
Exclusive ODER verknüpfen:
Anweisung in Dezimal:
var foo:int = 6^5;
Die Variable foo hat den Wert 3 nach der Operation. Bei exlusive ODER ist es nur wahr wenn die Bits unterschiedlich sind.
Binärdarstellung:
0110 // Dez: 6 0101 // Dez: 5 ---- 0011 // Dez: 3
Einerkomplement:
Anweisung in Dezimal:
var foo:int = 3&~1;
Die Variable foo hat den Wert 2 nach der Operation. Hierbei sind zwei Schritte erforderlich. Die Bits der 1 müssen zunächst invertiert werden, die 0 wird zu 1 und die 1 zu 0. Anschließend werden die invertierten Bits UND verknüpft.
Binärdarstellung:
0011 // Dez: 3 0001 // Dez: 1 0011 1110 // invertiertes 0001 ---- 0010 // Dez: 2
Die Praxis:
Nehmen wir an, wir müssen ein Spiel oder eine Anwendung erstellen, in dem wir verschiedenfarbige Briefumschläge haben und ein Umschlag kann eine oder mehrere Sachen beinhalten. Es gibt also grüne, blaue, gelbe und rote Umschläge und als Sache Buch, Rechnung und CD. Vielleicht gibt es auch noch intern, öffentlich, private oder geschäftlich.
Wir definieren uns in einer Klasse, z.B. Envelope, folgende Konstanten und setzen unsere Bits. Zu dem benötigen wir noch eine Variable, die den Brieftyp beinhaltet.
public static const GREEN:uint = 1<<0; public static const BLUE:uint = 1<<1; public static const YELLOW:uint = 1<<2; public static const RED:uint = 1<<3; public static const BOOK:uint = 1<<20; public static const INVOICE:uint = 1<<21; public static const CD:uint = 1<<22; public static const INTERN:uint = 1<<28; public static const PUBLIC:uint = 1<<29; public static const PRIVATE:uint = 1<<30; public static const COMMERCIAL:uint = 1<<31; private var _type:uint;
Das setzen der richtigen Bits übernimmt zum Glück der Computer für uns und müssen lediglich rechts schieben. Warum wir nicht einfach die Werte 1, 2,3, 4, 5…. geben, liegt daran, dass wir nicht die Zahlen vergleichen werden, sondern den Vergleich auf Bit ebene vornehmen. D. h. wenn das erste Bit von _type gesetzt ist, ist der Umschlag grün. Man könnte ihn auch grün, rot machen, in dem man das erste und das vierte Bit setzt.
Die Bits der Farben sind also wie folgt gesetzt:
0001 // GREEN 0010 // BLUE 0100 // YELLOW 1000 // RED
An diesem Beispiel sehen wir auch, was passiert, wenn wir den public static const YELLOW:uint = 3; gesagt hätten. Die Dezimalzahl 3 ist in Binär 0011 und es hieße für uns, dass der Umschlag grün und blau ist. Spätestens wenn wir den ODER und UND Operator verwenden, dürfte dies jedem klar werden.
Einen roten Umschalg zu setzen und zu testen, ob dieser eine bestimmte Farbe hat, ist an dieser Stelle nich wirklich spannend.
_type = RED; // roter Umschlag
// auf Farbe testen
if (_type == RED)
{
// Umschlag ist rot
}
Bits von _type: 1000
Spannender wird es wenn wir nun einen roten Umschlag mit einem Buch haben wollen, d. h. wir müssen das vierte und fünfte Bit setzen und genau jetzt kommt unser ODER Operator ins Spiel. Mit ODER können wir die Bits setzen.
_type = RED | BOOK;
In Binär:
00001000 // RED 00010000 // BOOK -------- 00011000 // ODER verknüpft
Siehe da, wir haben im _type das Bit für RED und BOOK gesetzt. Ab jetzt können wir nicht mehr ganz so einfach auf auf RED testen, da 00011000 nicht 000010000 ist. Um auf einen Wert zu prüfen, benötigen wir den UND Operator.
if (_type&RED > 0)
{
// ist rot
}
else
{
// ist nicht rot
}
if (_type&BOOK > 0)
{
// hat Buch
}
Schauen wir uns mal die Binärzahlen an, was mit der UND verknüpfung passiert:
00011000 // BOOK|RED Dez: 24 00001000 // RED Dez: 4 -------- 00001000 // RED Dez: 4
Dadurch, dass man die Bits UND verknüpft, fallen alle nicht überinstimmenden Bits weg und wir bekommen als Ergebnis das UND verknüpfte oder 0, wenn dies nicht gesetzt wurde. Siehe folgendes Beispiel
00011000 // BOOK|RED Dez: 24 00000001 //GREEN Dez: 1 -------- 00000000 // Dez: 0
Es gibt viele verschiedene Kombinationen mit denen man prüfen kann. Möchte man wissen, ob der Umschlag überhaupt eine Farbe hat.
00011000 // BOOK|RED Dez: 24 00001111 // GREEN|BLUE|YELLOW|RED Dez: 15 00001000 // RED Dez: 4
Beide if – Anweisungen sind binär gesehen identisch
if (_type &(GREEN|BLUE|YELLOW|RED) > 0) ... if (_type&(0xF) >0) ...
0xF ist eine Hexadezimalzahl, man könnte sie auch mit führender 0 schreiben 0x0F und ist in Binär 00001111
Merke:
Mehrere Bits werden mit ODER gesetzt und mit UND überprüft.
BIT|BIT und BIT&BIT
Wenn wir einen blauen Umschlag mit einer CD und einer Rechnung haben, wollen aber gerne die Rechnung entfernen, so müssen wir einfach den Bit für die Rechnung löschen. Gelöscht wird mit dem Einerkomplement.
_type = CD|BLUE|INVOICE; _type &=~INVOICE; // ist das gleiche wie _type = _type&~INVOICE;
Schauen wir uns das Ganze in Binär an
11000000000000000000010 // CD|BLUE|INVOICE 01000000000000000000000 // INVOICE 10111111111111111111111 // ~INVOICE (invertiert)
_type &=~INVOICE 11000000000000000000010 // _type 10111111111111111111111 // UND verknüpfen ~INVOICE -------------------------------------- 10000000000000000000010 // CD|BLUE
Hier sehen wir sehr schön, dass das Bit für INVOICE entfernt wurde, bzw. auf 0 gesetzt wurde.
Zum Schluss zeige ich noch wie man höhere Bits eines Bereiches löschen kann. Wir haben zum Beispiel die beiden höchsten Bits gesetzt und wollen gerne die vier höchsten Bits löschen, also müssen wir eine UND Verknüpfung durchführen, in dem die obersten Bits auf 0 gesetzt sind.
_type = BLUE|INVOICE|PRIVATE|COMMERCIAL;
_type &= 0x0FFFFFFF;
11000000001000000000000000000010 // BLUE|INVOICE|PRIVATE|COMMERCIAL 00001111111111111111111111111111 // 0x0FFFFFFF oder ~(PRIVATE|PUBLIC|INTERN|COMMERCIAL) 00000000001000000000000000000010 // BLUE|INVOICE
_type &=~(PRIVATE|PUBLIC|COMMERCIAL|INTERN) würde zum gleichen Ergebnis führen.
Merke:
Bits werden gelöscht in dem der Einerkomplement UND verknüpft wird
BIT & ~BIT
Wollt ihr zwei Typen vertauschen, also a nach b und b nach a kopieren, gelingt euch das am schnellsten ohne temporäre Variablen anzulegen, mit dem exclusive ODER.
_type1 = BLUE; _type2 = RED; _type1 ^= _type2; _type2 ^= _type1; _type1 ^= _type2;
In Binär sieht das so aus, ihr nehmt Stift und Zettel und schreibt die Binärzahlen auf und rechnet dies wie in der Theorie gezeigt aus.
TIPS:
Wenn ihr die Eins Zweiundreisig mal links schiebt (1<<32) fängt es wieder bei 1 an, da ein Integer nur 32 Bit hat.
Das exclusive ODER tauschen funktioniert mit jedem Integer.
var a:int = 5; var b:int = 2; trace(a + " und " + b) // output: 5 und 2 a ^= b; b ^= a; a ^= b; trace(a + " und " + b) // output: 2 und 5
Wen ihr herausfinden wollt, wie oft eine Zahl nach links geschoben wurde, müssen wir logarithmieren. Das Schieben nach links ist nichts anderes als y = 2x, dann ist x = log2(y).
1<<2 = 2² 1<<3 = 2³
Da in den meisten Programmiersprachen nur der logarithmus naturalis (ln) zur Verfügung steht, müssen wir diesen umrechnen. Unsere Formel lautet dem nach x = loge(y) / loge(2)
In ActionScript 3 ist unser natürlicher Logarithmus zur Basis e Math.log().
var x:int = Math.log(y)/Math.log(2);
Da die Klasse Math den Math.log(2) als Konstante ausgerechnet hat, können wir uns ein wenig Rechenzeit sparen und scheiben
var x:int = Math.log(y) / Math.LN2;
Zu Beachten ist auch, dass wir in einigen Fällen Nachkommastellen haben. Das passiert, wenn wir einen ODER verknüpften Wert nehmen. Es gibt verschiedene Möglichkeiten abzurunden, da wir uns in der Bitmanipulation befinden, benutzen wir doch gleich rechts schieben. Einmal nach rechts schieben entspricht Division durch 2 mit Abrunden.
var x:int = Math.log(y) / Math.LN2 >> 0;
