Traumberuf Bitschubser – Bitverschiebung in Java
Im Prinzip ist das Arbeiten mit Binärcode unter Java keine große Sache. Jedoch stolpere ich – im Internet – immer wieder über Codebeispiele, welche Integer- oder Longwerte erst aufwendig in Einserer und Nuller zerlegen und diese dann in einem String ablegen. Bei solchem Vorgehen bleibt mir die Spucke weg.
Bitverschiebung in Java
Beim beantworten von Forenfragen zum Thema „Zerlegen von Dezimalzahlen in Binärzahln (Dualzahlen)“, stoße ich immer wieder auf die wildesten Antworten.
Ein Klassiker: Das Zerlegen von Zahlen in aufwändigen Schritten und das dann – fatale – speichern in einem String. So macht man schnell aus einem 32 Bit (4 Byte) Integer Wert ein vielfach großen Stringwert.
In Anbetracht dieser Antworten, neigt mein Gedankenverarbeitungs-Thread zum spontanen Stackoverflow! Daher scheint mir das Thema „Bitverschiebung“ prädestiniert für meinen Blog.
Dazu zeige ich dir folgende Punkte:
- Speicherrechnung: Binärzahl speichern in String
- Theorie zur Bitverschiebung
- Praktisches Java Beispiel
Speicherrechnung: Binärzahl halten in String
Achtung: Ich bin verpflichtet hinzuweisen, dass bei Betrachtung des folgenden Beispiels – von wahren Bitschubsern, erhebliche Übelkeitsgefühle auftreten können ;).
Angenommen wir haben ein Integerwert und möchten diesen in eine Binärzahl umwandeln, in einem String speichern, um anschließend das Bit an der fünften Stelle zu lesen. So nimmt der Integerwert für sich immer 32 Bit (4 Byte)in Anspruch. Gehen wir von der Zahl 234 aus und rechnen diese in eine duale Zahl um, ergibt dies „1110 1010“.
Weil wir Ressourcen „sparen“ *derbste Ironie* wollen, speichern wir das Leerzeichen nicht im String mit. So ergeben sich genau 8 Stellen. Gehen wir von 2 Byte (kann in Java variieren) pro Zeichen aus, beläuft sich der Speicherbedarf auf 16 Byte (400 %).
[code language=“java“]
//Ausgangszahl 234
int i = 234; //32 Bit
//konvertiert in Dualzahl
//>1110 1010
String s = dezimalToBinary(i);
//lesen der 5ten Stelle und Ausgabe
System.out.println(s.charAt(4));
[/code]
Anfangs mag das banal erscheinen, doch reizt man den Integerwert voll aus – mit der Obergrenze von 2.147.483.647 (ebenfalls 4 Byte)- ergibt sich ein Speichervolumen im String von 62 Byte (31 Zeichen, 1.500 %). Wer jetzt denkt: „ich habe doch genug Speicher“, wird bei einem einfachen Standardprogramm richtig liegen. Doch wo eine Verschwendung von Speicher hinführen kann, ist in diesem Artikel, zum Javaheap, gut beschrieben.
Auch der Aufwand vom hin- und herkonvertieren darf nicht unterschätzt werden. Denke nur mal daran, wenn du eine Datei von mehreren GigaByte mit einem 32 stelligen Passwort verschlüsseln möchtest. Dabei kann dieses Vorgehen zum echten Performance-Problem werden.
Theorie zur Bitverschiebung
Zur Bitverschiebung in Java gibt es eine eigene Syntax. Ich gebe zu, dass diese anfänglich etwas merkwürdig erscheint, dafür ist sie mehr als praktisch.
[code language=“java“]
//Ausgangswert
int i = 234;
//Rechtsverschiebung
i = i >> 4;
//Linksverschiebung
i = i << 4;
[/code]
Die doppelte Spitzklammer gibt jeweils an, in welche Richtung die Bits verschoben werden sollen. Die Zahl dahinter übermittelt dem Programm, um wie viele Stellen das ganze verschoben werden soll. Wie sieht das genau aus? Nehmen wir die Zahl 234, ist diese umgerechnet in Binär: „1110 1010“. Verschieben wir diese nun mit „>> 4“, um vier Stellen nach rechts – bekommen wir die verschobene Integerzahl 14 zurück – Binär: „0000 1110“.
Wie wir sehen, wurden die ersten vier Stellen einfach abgeschnitten und alle anderen Bits sind nach gerutscht. Das gleiche funktioniert mit mit der Linksverschiebung. Aus 234 (Binär: „1110 1010“) mit „<< 4" wird 3744 (Binär: "1110 1010 0000"). Dabei werden die ersten vier stellen mit Nullen ausgefüllt.
| Wert | Dual | Verschiebung | Wert (verschoben) | Dual (verschoben) |
|---|---|---|---|---|
| 8 | 0000 1000 | >> 3 | 1 | 0000 0000 0001 |
| 8 | 0000 1000 | << 3 | 64 | 0000 0100 0000 |
| 170 | 1010 1010 | >> 1 | 85 | 0000 0101 0101 |
| 170 | 1010 1010 | << 1 | 340 | 0001 0101 0100 |
| 255 | 1111 1111 | >> 4 | 15 | 0000 0000 1111 |
| 255 | 1111 1111 | << 4 | 4080 | 1111 1111 0000 |
Praktisches Java Beispiel
Folgend möchte ich noch ein praktisches Beispiel zeigen. Dazu greifen wir eine Art und Weise auf, wie man das Problem aus dem ersten Punkt „ist ein Bit an einer bestimmten Stelle gesetzt?“, elegant lösen kann.
Betrachten wir eine Binärzahl genauer (von Rechts nach Links gelesen), so entdecken wir, dass diese nur aus geraden Zahlen zusammengesetzt wird. Ausnahme dabei bildet die erste Stelle (ganz Rechts). Denn diese spiegelt den Wert 1 wieder. Das heißt, die erste Stelle allein, entscheidet darüber, ob eine Zahl gerade oder ungerade ist. Folgende Tabelle gibt von Rechts nach Links die Wertigkeiten der Binärzahl an.
| 2^7 | 2^6 | 2^5 | 2^4 | 2^3 | 2^2 | 2^1 | 2^0 |
|---|---|---|---|---|---|---|---|
| 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Weiter gedacht heißt das auch, dass nur die erste Stelle darüber entscheidet ob die Zahl durch zwei teilbar ist oder nicht. Genau diesen Sachverhalt machen wir uns jetzt zunutzen.
[code language=“java“]
/**
* Prüft ob ein einzelnes Bit, an einer bestimmten stelle, gesetzt ist
* @param number
* : Zahl in Dezimal
* @param position
* : Welche Bitposition soll abgefragt werden (Erste Stelle
* entspricht 1)
* @return true = Bit ist gesetzt (1), false = Bit ist nicht gesetzt (0)
*/
public static boolean isBitAvailable(int number, int position) {
// Position fängt intern bei 0 an zu zählen (erste Stelle entspricht
// postion = 0)
position–;
// Bitverschiebung
number = number >> position;
if (number % 2 == 0) {
// Zahl ist gerade
// Bit ist nicht gesetzt
return false;
} else {
// Zahl ist ungerade
// Bit ist gesetzt
return true;
}
}
[/code]
Bitvergleich in drei Schritten
Somit schaffen wir den Bitvergleich in nur drei einfachen Schritten. Am Anfang verschieben wir unseren Integerwert in „number“ um den Wert in „position“ nach rechts. Das heißt, dass am ende der Operation die Stelle, die wir betrachten wollen, ganz rechts steht – die neue Binärzahl wird als Integerwert gespeichert. Anschließend ziehen wir den Modulo (ergibt den Rest von number / 2 ) und Vergleichen den Rückgabewert. Bei Modulo 2 gibt es nur zwei Möglichkeiten der Rückgabe: 0 (die Zahl ist gerade) und 1 (die Zahl ist ungerade). Ist die neue und verschobene Integerzahl nun gerade, wissen wir, dass das Bit – welches wir betrachten wollen – nicht gesetzt ist, ist die Zahl ungerade so muss das Bit gesetzt sein!
Im Anhang findest du, wie immer, den Javasourcecode. Zusätzlich habe ich noch einen JUnit-Test erstellt um die Funktion „isBitAvailable()“ genauer zu testen.
Tool
Um eine schnelle und manuelle Umrechnung von Dezimalzahlen in Binär, Hexadezimal usw. vorzunehmen, kann ich nur den Windows-Taschenrechner empfehlen. Diesen kann man in der Ansicht auf „Programmierer“ stellen. Dort findest du alles was das Programmierer-Herz begehrt. Modulo, Hexadezimal, Oktal-Zahlensystem und logische Operatoren. Um diesen zu starten muss du lediglich in der Eingabezeile im Windowsstartbutton „calc“ eingeben.
Anhang
Java – Bitprüfung und JUnit-Test Bitverschiebung Java-Source
Neueste Kommentare