48 Bits und eine Maske

Nach einer kurzen Pause gibt es jetzt den nächsten Beitrag. Heute geht es nicht etwa um zwei Kästen Bitburger und Batman, sondern um Bitshiften und das Verunden von Zahlen mit Bitmasken. Ich werde heute ein paar Codestücke vorstellen, die mir einst bei einem Codereview untergekommen sind. Nach einer Analyse des Codes und der Suche nach dem eigentlichen Ziel der Implementierung werde ich eine alternative Implementierung vorschlagen. Neben der optischen Verbesserung werde ich durch Zeitmessung auch die Performancesteigerung hervorheben. Genug der Vorworte, auf geht’s.


The beginning

Besagtes Codereview: ich arbeite mich durch die Klasse und stoße auf folgende Zeilen:

Auf den ersten Blick eigentlich ganz harmlos, vier Zeilen, schön aufgeräumt. Allerdings verwundert mich die Tatsache, dass die Variablen “Number” heißen, aber als String gespeichert werden. Verdächtig. Vor allem, da sie ein paar Methoden weiter dann wieder in Integer konvertiert werden. Zudem verstehe ich nicht ganz, was da passiert. Schauen wir uns die einzelnen Schritte der Reihe nach an.


The details
  1. Das Ergebnis einer Methode (MirrorByteArrayBits) wird in einen BitArray gesteckt. Ein BitArray erzeugt einen Array aus true- und false-Werten für die Bits der einzelnen Bytes des Arrays, der übergeben wird. Dazu muss man wissen, dass in diesem Array die Bits der n Bytes an den Indizes n*0 – n*7 gespeichert werden. (siehe dazu auch die Dokumentation von Microsoft.) Das bedeutet, die zwei Bytes

    werden in folgenden Array umgewandelt:

    Warum der Array vorher gespiegelt werden muss, werden wir später sehen.
  2. Nun wird in der nächsten Zeile ein Teil des Bitarrays in eine Zahl umgewandelt, die anschließend in einen String umgewandelt wird, denn, nunja, Strings sind toll. Zum Umwandeln wird die Methode BitArrayToInt verwendet, die wie folgt aussieht:

    Wenn ich mal die ganzen Sicherheitschecks entferne, bleibt folgender Code übrig:

    Eine Variable wird für die Elemente [aStartBit;aStopBit] des BitArrays um 1 Bit nach links geshiftet. Ist das Flag im BitArray an der Stelle i true, so wird die Variable zusätzlich mit 1 verodert. Nehmen wir wieder das BitArray aus dem Beispiel aus Punkt 1. Wir wollen die Zahl zwei extrahieren, also übergeben wir zusätzlich zum Array die Indices 8 (Start) und 15 (Ende).
    Nach Durchlaufen der Schleife, lautet die Ergebniszahl allerdings 64. Dies liegt daran, dass das true-Flag an Index 9 steht und somit sechs Mal nach links geshiftet wird. Und um genau diese Problematik zu umgehen, wurde im ersten Codebeispiel die Methode MirrorByteArrayBits verwendet. Denn danach steht das true-Flag an Index 14 und das Ergebnis der Methode BitArrayToInt lautet – wie gewünscht – 2. Also schauen wir uns diese Methode auch noch an.
  3. In dieser Methode wird ein neuer Bytearray angelegt, in welchem jedes einzelne Byte gespiegelt gespeichert wird. Dieser Array wird anschließend zurückgegeben.
  4. Die dort aufgerufene Methode MirrorBits sieht wie folgt aus:

    Hier wird eine Variable definiert, die acht Mal um je ein Bit nach rechts verschoben wird. Nach jedem Bitshift wird sie mit dem obersten Bit des Eingabebytes verodert. Das Eingabebyte wird im Anschluss um ein Bit nach links geshiftet. Somit wird das Byte einmal komplett gespiegelt. Aus dem Byte 202 (1100 1010) das gespiegelte Byte 83 (0101 0011).

The despair

Nun haben wir alle Methoden analysiert, verarbeitet, verstanden. Und wissen dennoch nicht genau, was eigentlich gerade passiert ist. Einfach zu verstehen ist anders – für mich zumindest. Ich weiß noch immer nicht, was die ersten, ursprünglichen Zeilen eigentlich bedeuten, was der Autor damit beabsichtigt. Nach etwas Recherche habe ich herausgefunden, dass in den sechs Bytes insgesamt 3 Zahlen codiert sind, in den Bytes 27-47, 17-26 und 0-16.
Das lässt sich im Endeffekt auch aus den Zeilen erkennen, wenngleich es nicht ganz offensichtlich ist. Außerdem gefällt es mir nicht, wie das Ergebnis erreicht wird. Schauen wir uns die 48 Bits mal in einer etwas anderen Darstellung an. Rot eingeschlossen sind jeweils die Bits, die eine Zahl darstellen.

Bündelung der Bits für die drei Zahlen

The speed

Um an diese drei Zahlen zu kommen, kann man aber auch folgenden Code verwenden:

Zuerst erstellen wir die oben gezeigte Bitreihe, indem wir eine ganze Zahl (in diesem Fall einen Longwert) aus den Bytes erzeugen. Für die erste Zahl shiften wir unseren Longwert um 27 Bits nach rechts. Für die zweite Zahl schneiden wir die ersten 21 Bits ab, indem wir den Longwert mit 0x7FFFFFF verunden. Das Ergebnis shiften wir dann noch um 17 Bits nach rechts. Und für die dritte Zahl schneiden wir einfach die ersten 31 Bits ab, indem wir unseren Longwert mit 0x1FFFF maskieren.

Dieses Stück Code ist in meinen Augen wesentlich übersichtlicher als die Reihe von Methoden, die wir weiter oben betrachtet haben. Doch es bringt auch wesentliche Performanceverbesserungen mit sich. In meinen Zeitmessungen war meine Lösung mit Shiften und Verunden im Mittel rund 13-17 Mal schneller als der Weg über die Methoden und den BitArray.
Gerne dürft ihr mir eure Meinung, Verbesserungsvorschläge oder ähnliche Ideen in den Kommentaren hinterlassen.

Schönerer Code, schnellerer Code, effizienter Code. Ziel erreicht.

 

Leave a Reply

Your email address will not be published. Required fields are marked *