BenBE's humble thoughts Thoughts the world doesn't need yet …

Basierend auf einer wahren Forengeschichte, gibt es heute einmal etwas zum Thema Optimierung von Software. Es war nicht lange her, in einem ruhigen Forum, da tauchte einem seiner Nutzer die Frage auf, wie er die Bits in seinem Computer möglichst effizient bearbeiten konnte. Also brach er auf in die „Algorithmen, Optimierung und Assembler„-Sparte seines geliebten Forums.

Erster Akt: Elegant Bits tauschen

Als erste Herausforderung an die kühnen Helden dieser Sparte ergab sich die Aufgabe, des Tauschens zweier Bitwerte in einem Bitfeld:

Aufgabe: Die Bits X und Y einer Binärzahl tauschen.

Die grundsätzliche Lösung ist klar, das ist auch nicht wirklich schwer. Der Witz ist: wie macht man das möglichst „elegant“ (wenig Befehle/Bitoperationen, kein Assembler).

Und so machten sich die Helden auf, durch das Dickicht der Möglichkeiten und fanden, nach ersten Verwirrungen ob der Bedeutung von „kein Assembler“ auch schnell Ansätze in Pseudo-Code:

Man negiert die „input“ Binärzahl. Das Ergebnis wird mit einer Zahl verknüpft (und) die die Bitstellen repräsentiert ( Bitstelle 3 und 5 ändern == 0010100).

Auch wenn dieser Ansatz auf der Verständnis-Skala von 0 bis 100 Glühbirnen* nur für romantisches Glimmen sorgte, woraufhin sich einige Mitbewerber an anschaulicheren ASCII-Charts versuchten:

Nehmen wir die (Binär-)Zahl 76543210 und die Maske 00010010, dann erhalten wir:

76543210 xor ((not 76543210) and 00010010) =
76543210 xor (000~400~10) = ...

[…]

Wenn ich seinen Post richtig verstanden habe, möchte er anhand der oben gegebenen Maske 76513240 als Ergebnis.

Nach dem diese Illustration scheinbar das Glimmen zu einem Flutlicht der Erleuchtung konvertierte, begann plötzlich eine kambrische Explosion:

meinst Du das so:

procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte);
var
  Maske: Integer;
  Temp: Integer;
begin
  Maske := (1 shl BitX) or (1 shl BitY);
  Temp := (Value and Maske);
  if (Temp <> 0) and (Temp <> Maske)
  then Value := Value xor Maske;
end;

Diese wurde schnell auch von Charles Darwin und seinen Helfern begleitet:

Das Tauschen der Bits muss ja nur vorgenommen werden, wenn die beiden Bits unterschiedlich sind. Sind beide Bits gleich, dann verändert ein Swap die Zahl nicht!

Daher würde ich erst die Bits auf Gleichheit prüfen:

Bit = ( (Value >> BitX) XOR (Value >> BitY) ) AND 1

Nur im Falle von Bit == 1 muss weiter gemacht werden und die Bits geswappt werden:

NewValue = Value XOR ( (1 << BitX) OR (1 << BitY) )

Sofern eine if-Abfrage nicht erlaubt ist, kann man mit dem Wert von Bit Weiter machen, da dieser bei Ungleichheit 1 ist:

Bit = ( (Value >> BitX) XOR (Value >> BitY) ) AND 1;
NewValue = Value XOR ( (Bit << BitX) OR (Bit << BitY) )

Der Aufwand wäre: 4 Shifts, 2 XOR, 1 OR und 1 AND, wobei ich denke diese Formel noch vereinfacht werden kann!

Konservative Ansätze einiger Spaßvögel, die mit Fragen wie

möchte wer meine String-Implemenation ohne AND, XOR usw. sondern nur durch IF…THEN in For-schleifen?

an der (R)Evolution zweifelten wurden aber schnell besiegt:

procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte);
begin
  if ( ( (Value shr BitX) XOR (Value shr BitY) ) AND 1 ) <> 0 then
    Value := Value XOR ( (1 shl BitX) OR (1 shl BitY) );
end;

Aber auch der technische Fortschritt ließ sich nicht mehr stoppen, womit bald darauf jeder unnötige Ast** abgesägt war:

Hmmm, das dürfte sich auch noch ohne If darstellen lassen:

procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte);
begin
    Value := Value XOR ( ((1 shl BitX) OR (1 shl BitY)) * ( ((Value shr BitX) XOR (Value shr BitY)) AND 1 ) ) ;
end;

Womit der erste Akt eigentlich bereits beendet wäre, wäre da nicht die wissenschaftliche Neugierde des Erzählers, der an dieser Stelle kurz zwei Techniken herausgreifen möchte, um die folgenden Akte einfacher verstehbar zu machen, da diese recht analoge Techniken verwenden.

Erwähnenswert ist hierbei der erste Vorstoß, der auch die kambrische Explosion auslöste. Dieser nutzt, wie im Pseudocode angedeutet, jedoch falsch umgesetzt, ein exklusives Oder, um zwei unterschiedliche Bits zu tauschen. Sind die beiden zu tauschenden Bits identisch, so ergeben diese mit der Maske verknüpft entweder die Maske selbst oder 0 (wenn beide Bits 0 sind). Dieser Weg ist zwar bereits recht schnell auszuführen, benötigt jedoch im Gegensatz zur zweiten Variante, die in späteren Versionen zum Einsatz kommt, keine Shift-Operationen, wenn die Maske bereits vorliegt.

Liegt die Maske jedoch nicht vor, so lässt sich die Entscheidung über das Vertauschen jedoch auch auf andere Art und Weise klären: man Shiftet die zu tauschenden Bits jeweils an die Bit-Position 0 und ignoriert jegliche anderen Bits. Somit erhält man als Aussage entweder eine 0 (beide Bits gleich) oder 1 (Bits sind unterschiedlich).

Da Computer gerne auf 0 und ungleich 0 vergleichen bietet diese Variante somit eine gute Ausgangslage, um effizient eine If-Abfrage damit zu gestalten. Wesentlich besser ist jedoch, den durch eine If-Abfrage erzeugten Sprung komplett zu vermeiden und stattdessen eine verzweigungsfreie Alternative einzusetzen: Einee Multiplikation. Der Trick bei der Multiplikation besteht nun darin, dass die sowieso vom „Vergleichscode“ gelieferte Zahl problemlos mit der Maske multipliziert werden kann, da im Falle einer 0 auch 0 für die Änderungsmaske herausfällt (0 XOR a = a) und im Falle einer 1 die Maske selber herauskommt, also wie gewünscht Maske XOR A gerechnet wird. Zusätzlich ergibt sich hierbei, dass eine Multiplikation immer gleich schnell abgearbeitet wird, d.h. der Code unabhängig von den Eingaben IMMER in identischer Zeit durchlaufen wird, was z.B. beim Einsatz in Verschlüsslungsverfahren von Nöten ist.

Zweiter Akt: Elegant Bits entfernen

Aber damit nicht genug: Denn die Reise unserer Bits ging munter weiter; und sei es, weil jemand „10 kleine Jägermeister“ in binär spielen wollte …

Aufgabe: ein Bit aus einer Binärzahl löschen (analog zu Delete() für Strings, nur eben auf Bitbasis).

Nach dem der naive Ansatz bereits am Anfang durch einen Code-Schnipsel für unwürdig erklärt wurde,

procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte); //nach BenBE
begin
    Value := Value XOR ( ((1 shl BitX) OR (1 shl BitY)) * ( ((Value shr BitX) XOR (Value shr BitY)) AND 1 ) ) ;
end;

procedure DeleteBit(var Value: Cardinal; const Bit : Byte);
var
  i: Integer;
begin
  for i := Bit downto 1 do
  begin
    SwapBits(Value,i, i-1);
  end;
  Value := Value shr 1;
end;

Vorgehen:
das Zielbit ganz nach rechts durchschieben und dann einmal nach rechts shiften.

konnten die tapferen Ritter der Binärzahlen schnell zur Sache kommen:

Mein Ansatz:

procedure DeleteBit(var Value: Cardinal; const Bit: Byte)
var
  Mask, Right: Cardinal;
begin
  Mask := (1 shl Bit) - 1;
  Right := Value and Mask;
  Value := Value shr 1;
  Value := (Value and not Mask) or Right;
end;

Eine weitere Alternative folgte sogleich:

procedure DeleteBit(var Value: Cardinal; const Bit : Byte);
var
  Mask: Cardinal;
begin
  Mask := (1 shl Bit) - 1;
  Value := ( Value and Mask ) or ( ( Value shr 1 ) and ( not Mask ) );
end;

Jedoch ließ sich auch hier eine gewisse Einzeiler-Evolution nicht ganz verhindern, was ziemlich bald erschreckend kurze Lösungen hervorbrachte:

Result := ((Value and not (1 shl Bit)) + Value and ((1 shl Bit)-1)) shr 1;

Obwohl, ich glaub, ich erklär’s heut mal:

Das zu löschende Bit auf Null setzen, alle Bits rechts davon auf die Zahl drauf addieren und das Ergebnis insgesamt ein Bit nach Rechts schieben …

Da dieser Ansatz auf jeden Fall einen Shift beinhaltete, der sich jedoch, da sich die Bits links sammeln, beim Bearbeiten größerer Bitmengen zusammenfassen ließ, entstand nebenbei auch gleich eine Routine zum Eliminieren größerer Bit-Mengen***:

Ach ja, als kleine Ergänzung für mehrere Bits anhand einer Maske:

procedure DeleteBitsEx(var Value: Cardinal; Mask: Cardinal);
var
    TMask: Cardinal;
    BC: Byte;
begin
    BC := 0;
    While Mask <> 0 do
    Begin
        //Count bits ...
        Inc(BC);

        //Make obvious we can reuse partial/intermediate results here ...
        //C: TMask ^= Mask = (TMask = Mask) & (Mask-1);
        TMask := Mask;
        Mask := Mask and (Mask - 1);
        TMask := Mask xor TMask;

        //Remove the current selected Bit from Value ...
        Value := (Value and not TMask) + Value and (TMask - 1);
    end;

    //Move the zeros to the left ... (Actually also a ROR would do)
    Value := Value shr BC;
end;

Doch auch hier gibt es einige technische Feinheiten, die ggf. einer Erwähnung wert sind, obgleich sie eigentlich sofort ins stechen dürften: Das Tauschen von Bits solange, bis man am Ende angekommen ist, ist zwar in seiner naiven Version recht offensichtlich, erzeugt aber relativ viel Overhead. Allerdings lässt sich durch einen kleinen Trick die Verschiebe-Methode aus dem vorigen Kapitel stark beschleunigen:

Mask := Value xor (Value shr 1);
Mask := Mask and not ((1 shl Bit) - 1);
Value := Value xor Mask;

Hierbei erhält Mask in der ersten Zeile einen Wert, der überall dort eine 1 enthält, wo unterscheidende Bits benachbart sind. Anhand der Maske in Zeile zwei wird diese Maske auf die Bits links des zu entfernenden Bits beschränkt und schließlich in der dritten Zeile eine Änderung aller zu kippenden Bits ausgeführt. Diese Variante ist jedoch nicht sinnvoll auf mehrere Bits zu übertragen.

Ganz im Gegenteil zur Einzeiler-Variante, die in ihre Einzelteile zerlegt drei Algorithmen enthält:

1. Zählen von gesetzten Bits
2. Prüfen auf eine Zweierpotenz / Erkennen des niedrigsten, gesetzten Bits
3. Das Entfernen eines Bits durch Multiplikation mit 2 via Addition

Da der Grundalgorithmus Null-Bits beim LSb einfügt, muss durch einen abschließenden Shift eine entsprechende Umsortierung erfolgen. Diese ist jedoch, relativ kostengünstig zu haben 😉

Dritter Akt: Elegant Bits einfügen (Original Art)

Nach dem der mutige Protagonist der vorigen Akte jedoch nicht mehr wollte – nein, sogar genug Eleganz für die Woche hatte – blieb diese Trilogie bisher unvollendet, auch wenn gerade das Einfügen eines Bits in diesem Zusammenhang von erhöhtem Interesse sein dürfte. Auch hier bietet sich ein naiver Ansatz an:

procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte); //nach BenBE
begin
    Value := Value XOR ( ((1 shl BitX) OR (1 shl BitY)) * ( ((Value shr BitX) XOR (Value shr BitY)) AND 1 ) ) ;
end;

procedure InsertBit(var Value: Cardinal; const Bit : Byte; const BitValue: Byte;);
var
  i: Integer;
begin
  Value := Value or ((not MaxInt) * BitValue);
  for i := 31 downto Bit+1 do
  begin
    SwapBits(Value, i, i-1);
  end;
end;

Aber auch hier lässt sich der Ansatz aus dem vorigen Abschnitt, zum Zusammenfassen der Vertausch-Operationen ansetzen:

procedure InsertBit(var Value: Cardinal; const Bit : Byte; const BitValue: Boolean);
var
  Mask1, Mask2: Integer;
begin
  Mask1 := 1 shl Bit;
  Mask2 := not (Mask1 - 1);
  Value := Value + (Value and Mask2) + Mask1 * Ord(BitValue);
end;

Dieser Code lässt sich durch einfaches weglassen der Variablen auch noch prima vereinzeilern:

procedure InsertBit(var Value: Cardinal; const Bit : Byte; const BitValue: Boolean);
begin
  Value := Value + (Value and not ((1 shl Bit) - 1)) + (1 shl Bit) * Ord(BitValue);
end;

Was jedoch nicht zwangsläufig seiner Lesbarkeit zu Gute kommt 😉

Und die Moral der Geschichte?

Manche Trilogien werden ohne Bezug zum Original weitergeschrieben und manchmal hilft ein bisschen Bit Twiddling gewaltig weiter, um Code zu optimieren …

*Nein, Energiesparlampen sind bei der Verständnisskala zum Missfallen der EU nicht vorgesehen
**Puns intended
***Nein, dieses Thema ist alkoholfrei