{"id":485,"date":"2010-01-30T03:44:32","date_gmt":"2010-01-30T02:44:32","guid":{"rendered":"http:\/\/blog.benny-baumann.de\/?p=485"},"modified":"2010-03-27T22:01:04","modified_gmt":"2010-03-27T21:01:04","slug":"the-elegant-bits-trilogy","status":"publish","type":"post","link":"https:\/\/blog.benny-baumann.de\/?p=485","title":{"rendered":"The Elegant Bits Trilogy"},"content":{"rendered":"

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\u00f6glichst effizient bearbeiten konnte. Also brach er auf in die „Algorithmen, Optimierung und Assembler<\/a>„-Sparte seines geliebten Forums.<\/p>\n

Erster Akt: Elegant Bits tauschen<\/a><\/h2>\n

Als erste Herausforderung an die k\u00fchnen Helden dieser Sparte ergab sich die Aufgabe, des Tauschens zweier Bitwerte in einem Bitfeld:<\/p>\n

Aufgabe: Die Bits X und Y einer Bin\u00e4rzahl tauschen.<\/p>\n

Die grunds\u00e4tzliche L\u00f6sung ist klar, das ist auch nicht wirklich schwer. Der Witz ist: wie macht man das m\u00f6glichst „elegant“ (wenig Befehle\/Bitoperationen, kein Assembler).<\/p><\/blockquote>\n

Und so machten sich die Helden auf, durch das Dickicht der M\u00f6glichkeiten und fanden, nach ersten Verwirrungen ob der Bedeutung von „kein Assembler“ auch schnell Ans\u00e4tze in Pseudo-Code<\/a>:<\/p>\n

Man negiert die „input“ Bin\u00e4rzahl. Das Ergebnis wird mit einer Zahl verkn\u00fcpft (und) die die Bitstellen repr\u00e4sentiert ( Bitstelle 3 und 5 \u00e4ndern == 0010100).<\/p><\/blockquote>\n

Auch wenn dieser Ansatz auf der Verst\u00e4ndnis-Skala von 0 bis 100 Gl\u00fchbirnen* nur f\u00fcr romantisches Glimmen sorgte, woraufhin sich einige Mitbewerber an anschaulicheren ASCII-Charts<\/a> versuchten:<\/p>\n

Nehmen wir die (Bin\u00e4r-)Zahl 76543210 und die Maske 00010010, dann erhalten wir:<\/p>\n

76543210 xor ((not 76543210) and 00010010) =\r\n76543210 xor (000~400~10) = ...<\/pre>\n
[…]<\/p>\n
Wenn ich seinen Post richtig verstanden habe, m\u00f6chte er anhand der oben gegebenen Maske 76513240 als Ergebnis.<\/p><\/blockquote>\n
Nach dem diese Illustration scheinbar das Glimmen zu einem Flutlicht der Erleuchtung konvertierte, begann pl\u00f6tzlich eine kambrische Explosion<\/a>:<\/p>\n
meinst Du das so:<\/p>\n
procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte);\r\nvar\r\n  Maske: Integer;\r\n  Temp: Integer;\r\nbegin\r\n  Maske := (1 shl BitX) or (1 shl BitY);\r\n  Temp := (Value and Maske);\r\n  if (Temp <> 0) and (Temp <> Maske)\r\n  then Value := Value xor Maske;\r\nend;<\/pre>\n<\/blockquote>\n
Diese wurde schnell auch von Charles Darwin und seinen Helfern begleitet<\/a>:<\/p>\n
Das Tauschen der Bits muss ja nur vorgenommen werden, wenn die beiden Bits unterschiedlich sind. Sind beide Bits gleich, dann ver\u00e4ndert ein Swap die Zahl nicht!<\/p>\n
Daher w\u00fcrde ich erst die Bits auf Gleichheit pr\u00fcfen:<\/p>\n
Bit = ( (Value >> BitX) XOR (Value >> BitY) ) AND 1<\/pre>\n
Nur im Falle von Bit == 1 muss weiter gemacht werden und die Bits geswappt werden:<\/p>\n
NewValue = Value XOR ( (1 << BitX) OR (1 << BitY) )<\/pre>\n
Sofern eine if-Abfrage nicht erlaubt ist, kann man mit dem Wert von Bit Weiter machen, da dieser bei Ungleichheit 1 ist:<\/p>\n
Bit = ( (Value >> BitX) XOR (Value >> BitY) ) AND 1;\r\nNewValue = Value XOR ( (Bit << BitX) OR (Bit << BitY) )<\/pre>\n
Der Aufwand w\u00e4re: 4 Shifts, 2 XOR, 1 OR und 1 AND, wobei ich denke diese Formel noch vereinfacht werden kann!<\/p><\/blockquote>\n
Konservative Ans\u00e4tze einiger Spa\u00dfv\u00f6gel<\/a>, die mit Fragen wie<\/p>\n
m\u00f6chte wer meine String-Implemenation ohne AND, XOR usw. sondern nur durch IF…THEN in For-schleifen?<\/p><\/blockquote>\n
an der (R)Evolution zweifelten wurden aber schnell besiegt:<\/p>\n
\n
procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte);\r\nbegin\r\n  if ( ( (Value shr BitX) XOR (Value shr BitY) ) AND 1 ) <> 0 then\r\n    Value := Value XOR ( (1 shl BitX) OR (1 shl BitY) );\r\nend;<\/pre>\n<\/blockquote>\n
Aber auch der technische Fortschritt lie\u00df sich nicht mehr stoppen, womit bald darauf jeder unn\u00f6tige Ast** abges\u00e4gt<\/a> war:<\/p>\n
Hmmm, das d\u00fcrfte sich auch noch ohne If darstellen lassen:<\/p>\n
procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte);\r\nbegin\r\n    Value := Value XOR ( ((1 shl BitX) OR (1 shl BitY)) * ( ((Value shr BitX) XOR (Value shr BitY)) AND 1 ) ) ;\r\nend;<\/pre>\n<\/blockquote>\n
Womit der erste Akt eigentlich bereits beendet w\u00e4re, w\u00e4re da nicht die wissenschaftliche Neugierde des Erz\u00e4hlers, der an dieser Stelle kurz zwei Techniken herausgreifen m\u00f6chte, um die folgenden Akte einfacher verstehbar zu machen, da diese recht analoge Techniken verwenden.<\/p>\n
Erw\u00e4hnenswert ist hierbei der erste Vorsto\u00df, der auch die kambrische Explosion ausl\u00f6ste. 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\u00fcpft entweder die Maske selbst oder 0 (wenn beide Bits 0 sind). Dieser Weg ist zwar bereits recht schnell auszuf\u00fchren, ben\u00f6tigt jedoch im Gegensatz zur zweiten Variante, die in sp\u00e4teren Versionen zum Einsatz kommt, keine Shift-Operationen, wenn die Maske bereits vorliegt.<\/p>\n
Liegt die Maske jedoch nicht vor, so l\u00e4sst sich die Entscheidung \u00fcber das Vertauschen jedoch auch auf andere Art und Weise kl\u00e4ren: man Shiftet die zu tauschenden Bits jeweils an die Bit-Position 0 und ignoriert jegliche anderen Bits. Somit erh\u00e4lt man als Aussage entweder eine 0 (beide Bits gleich) oder 1 (Bits sind unterschiedlich).<\/p>\n
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\u00fcr die \u00c4nderungsmaske herausf\u00e4llt (0 XOR a = a) und im Falle einer 1 die Maske selber herauskommt, also wie gew\u00fcnscht Maske XOR A gerechnet wird. Zus\u00e4tzlich ergibt sich hierbei, dass eine Multiplikation immer gleich schnell abgearbeitet wird, d.h. der Code unabh\u00e4ngig von den Eingaben IMMER in identischer Zeit durchlaufen wird, was z.B. beim Einsatz in Verschl\u00fcsslungsverfahren von N\u00f6ten ist.<\/p>\n
Zweiter Akt: Elegant Bits entfernen<\/a><\/h2>\n
Aber damit nicht genug: Denn die Reise unserer Bits ging munter weiter; und sei es, weil jemand „10 kleine J\u00e4germeister“ in bin\u00e4r spielen wollte …<\/p>\n
Aufgabe: ein Bit aus einer Bin\u00e4rzahl l\u00f6schen (analog zu Delete() f\u00fcr Strings, nur eben auf Bitbasis).<\/p><\/blockquote>\n
Nach dem der naive Ansatz bereits am Anfang durch einen Code-Schnipsel f\u00fcr unw\u00fcrdig erkl\u00e4rt<\/a> wurde,<\/p>\n
\n
procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte); \/\/nach BenBE\r\nbegin\r\n    Value := Value XOR ( ((1 shl BitX) OR (1 shl BitY)) * ( ((Value shr BitX) XOR (Value shr BitY)) AND 1 ) ) ;\r\nend;\r\n\r\nprocedure DeleteBit(var Value: Cardinal; const Bit : Byte);\r\nvar\r\n  i: Integer;\r\nbegin\r\n  for i := Bit downto 1 do\r\n  begin\r\n    SwapBits(Value,i, i-1);\r\n  end;\r\n  Value := Value shr 1;\r\nend;<\/pre>\n
Vorgehen:
\ndas Zielbit ganz nach rechts durchschieben und dann einmal nach rechts shiften.<\/p><\/blockquote>\n
konnten die tapferen Ritter der Bin\u00e4rzahlen<\/a> schnell zur Sache kommen:<\/p>\n
Mein Ansatz:<\/p>\n
procedure DeleteBit(var Value: Cardinal; const Bit: Byte)\r\nvar\r\n  Mask, Right: Cardinal;\r\nbegin\r\n  Mask := (1 shl Bit) - 1;\r\n  Right := Value and Mask;\r\n  Value := Value shr 1;\r\n  Value := (Value and not Mask) or Right;\r\nend;<\/pre>\n<\/blockquote>\n
Eine weitere Alternative<\/a> folgte sogleich:<\/p>\n
\n
procedure DeleteBit(var Value: Cardinal; const Bit : Byte);\r\nvar\r\n  Mask: Cardinal;\r\nbegin\r\n  Mask := (1 shl Bit) - 1;\r\n  Value := ( Value and Mask ) or ( ( Value shr 1 ) and ( not Mask ) );\r\nend;<\/pre>\n<\/blockquote>\n
Jedoch lie\u00df sich auch hier eine gewisse Einzeiler-Evolution nicht ganz verhindern, was ziemlich bald erschreckend kurze L\u00f6sungen<\/a> hervorbrachte:<\/p>\n
\n
Result := ((Value and not (1 shl Bit)) + Value and ((1 shl Bit)-1)) shr 1;<\/pre>\n
Obwohl, ich glaub, ich erkl\u00e4r’s heut mal:<\/p>\n
Das zu l\u00f6schende Bit auf Null setzen, alle Bits rechts davon auf die Zahl drauf addieren und das Ergebnis insgesamt ein Bit nach Rechts schieben …<\/p><\/blockquote>\n
Da dieser Ansatz auf jeden Fall einen Shift beinhaltete, der sich jedoch, da sich die Bits links sammeln, beim Bearbeiten gr\u00f6\u00dferer Bitmengen zusammenfassen lie\u00df, entstand nebenbei auch gleich eine Routine zum Eliminieren gr\u00f6\u00dferer Bit-Mengen***:<\/p>\n
Ach ja, als kleine Erg\u00e4nzung f\u00fcr mehrere Bits anhand einer Maske:<\/p>\n
procedure DeleteBitsEx(var Value: Cardinal; Mask: Cardinal);\r\nvar\r\n    TMask: Cardinal;\r\n    BC: Byte;\r\nbegin\r\n    BC := 0;\r\n    While Mask <> 0 do\r\n    Begin\r\n        \/\/Count bits ...\r\n        Inc(BC);\r\n\r\n        \/\/Make obvious we can reuse partial\/intermediate results here ...\r\n        \/\/C: TMask ^= Mask = (TMask = Mask) & (Mask-1);\r\n        TMask := Mask;\r\n        Mask := Mask and (Mask - 1);\r\n        TMask := Mask xor TMask;\r\n\r\n        \/\/Remove the current selected Bit from Value ...\r\n        Value := (Value and not TMask) + Value and (TMask - 1);\r\n    end;\r\n\r\n    \/\/Move the zeros to the left ... (Actually also a ROR would do)\r\n    Value := Value shr BC;\r\nend;<\/pre>\n<\/blockquote>\n
Doch auch hier gibt es einige technische Feinheiten, die ggf. einer Erw\u00e4hnung wert sind, obgleich sie eigentlich sofort ins stechen d\u00fcrften: 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\u00e4sst sich durch einen kleinen Trick die Verschiebe-Methode aus dem vorigen Kapitel stark beschleunigen:<\/p>\n
Mask := Value xor (Value shr 1);\r\nMask := Mask and not ((1 shl Bit) - 1);\r\nValue := Value xor Mask;<\/pre>\n
Hierbei erh\u00e4lt Mask in der ersten Zeile einen Wert, der \u00fcberall dort eine 1 enth\u00e4lt, wo unterscheidende Bits benachbart sind. Anhand der Maske in Zeile zwei wird diese Maske auf die Bits links des zu entfernenden Bits beschr\u00e4nkt und schlie\u00dflich in der dritten Zeile eine \u00c4nderung aller zu kippenden Bits ausgef\u00fchrt. Diese Variante ist jedoch nicht sinnvoll auf mehrere Bits zu \u00fcbertragen.<\/p>\n
Ganz im Gegenteil zur Einzeiler-Variante, die in ihre Einzelteile zerlegt drei Algorithmen enth\u00e4lt:<\/p>\n
    \n
  1. Z\u00e4hlen von gesetzten Bits<\/li>\n
  2. Pr\u00fcfen auf eine Zweierpotenz \/ Erkennen des niedrigsten, gesetzten Bits<\/li>\n
  3. Das Entfernen eines Bits durch Multiplikation mit 2 via Addition<\/li>\n<\/ol>\n
    Da der Grundalgorithmus Null-Bits beim LSb einf\u00fcgt, muss durch einen abschlie\u00dfenden Shift eine entsprechende Umsortierung erfolgen. Diese ist jedoch, relativ kosteng\u00fcnstig zu haben \ud83d\ude09<\/p>\n
    Dritter Akt: Elegant Bits einf\u00fcgen (Original Art)<\/h2>\n
    Nach dem der mutige Protagonist der vorigen Akte jedoch nicht mehr wollte – nein, sogar genug Eleganz f\u00fcr die Woche hatte – blieb diese Trilogie bisher unvollendet, auch wenn gerade das Einf\u00fcgen eines Bits in diesem Zusammenhang von erh\u00f6htem Interesse sein d\u00fcrfte. Auch hier bietet sich ein naiver Ansatz an:<\/p>\n
    procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte); \/\/nach BenBE\r\nbegin\r\n    Value := Value XOR ( ((1 shl BitX) OR (1 shl BitY)) * ( ((Value shr BitX) XOR (Value shr BitY)) AND 1 ) ) ;\r\nend;\r\n\r\nprocedure InsertBit(var Value: Cardinal; const Bit : Byte; const BitValue: Byte;);\r\nvar\r\n  i: Integer;\r\nbegin\r\n  Value := Value or ((not MaxInt) * BitValue);\r\n  for i := 31 downto Bit+1 do\r\n  begin\r\n    SwapBits(Value, i, i-1);\r\n  end;\r\nend;<\/pre>\n
    Aber auch hier l\u00e4sst sich der Ansatz aus dem vorigen Abschnitt, zum Zusammenfassen der Vertausch-Operationen ansetzen:<\/p>\n
    procedure InsertBit(var Value: Cardinal; const Bit : Byte; const BitValue: Boolean);\r\nvar\r\n  Mask1, Mask2: Integer;\r\nbegin\r\n  Mask1 := 1 shl Bit;\r\n  Mask2 := not (Mask1 - 1);\r\n  Value := Value + (Value and Mask2) + Mask1 * Ord(BitValue);\r\nend;<\/pre>\n
    Dieser Code l\u00e4sst sich durch einfaches weglassen der Variablen auch noch prima vereinzeilern:<\/p>\n
    procedure InsertBit(var Value: Cardinal; const Bit : Byte; const BitValue: Boolean);\r\nbegin\r\n  Value := Value + (Value and not ((1 shl Bit) - 1)) + (1 shl Bit) * Ord(BitValue);\r\nend;<\/pre>\n
    Was jedoch nicht zwangsl\u00e4ufig seiner Lesbarkeit zu Gute kommt \ud83d\ude09<\/p>\n
    Und die Moral der Geschichte?<\/h2>\n
    Manche Trilogien werden ohne Bezug zum Original weitergeschrieben und manchmal hilft ein bisschen Bit Twiddling<\/a> gewaltig weiter, um Code zu optimieren …<\/p>\n
    *Nein, Energiesparlampen sind bei der Verst\u00e4ndnisskala zum Missfallen der EU nicht vorgesehen
    \n**Puns intended
    \n***Nein, dieses Thema ist alkoholfrei<\/p>\n
    \"Flattr<\/a><\/p>","protected":false},"excerpt":{"rendered":"
    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\u00f6glichst effizient bearbeiten konnte. Also brach er auf in die „Algorithmen, Optimierung und Assembler„-Sparte seines geliebten […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0,"footnotes":""},"categories":[29],"tags":[182,98,181],"class_list":["post-485","post","type-post","status-publish","format-standard","hentry","category-software","tag-bitsets","tag-developement","tag-optimierung"],"_links":{"self":[{"href":"https:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/posts\/485","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.benny-baumann.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=485"}],"version-history":[{"count":5,"href":"https:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/posts\/485\/revisions"}],"predecessor-version":[{"id":601,"href":"https:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/posts\/485\/revisions\/601"}],"wp:attachment":[{"href":"https:\/\/blog.benny-baumann.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=485"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.benny-baumann.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=485"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.benny-baumann.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=485"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}