{"id":279,"date":"2009-05-23T15:14:03","date_gmt":"2009-05-23T15:14:03","guid":{"rendered":"http:\/\/blog.benny-baumann.de\/?p=279"},"modified":"2009-05-23T17:24:18","modified_gmt":"2009-05-23T17:24:18","slug":"schnelle-arbeit-auf-bit-ebene","status":"publish","type":"post","link":"http:\/\/blog.benny-baumann.de\/?p=279","title":{"rendered":"Schnelle Arbeit auf Bit-Ebene"},"content":{"rendered":"

Da ich in letzter Zeit doch etwas h\u00e4ufiger auf Bitebene arbeiten musste, und dabei immer wieder \u00e4hnliche Aufgaben anfielen, kam die Frage auf, wie bestimmte Aktionen am Einfachsten zu l\u00f6sen sind. Viele Operationen sind Straight Forward zwar l\u00f6sbar, doch mit Hilfe gewisser Bit Hacks<\/a> l\u00e4sst sich noch so einiges an Performance gewinnen.<\/p>\n

Was ich im Folgenden einmal genauer beschreiben m\u00f6chte, sind effiziente L\u00f6sungen f\u00fcr die folgenden Funktionen:<\/p>\n

inline int util_is_power_of_two(ULONG value);\r\ninline int util_is_power_of_two_nz(ULONG value);\r\ninline ULONG util_get_least_significant_bit(ULONG value);\r\ninline unsigned int util_log2_from_po2(ULONG value);\r\ninline ULONG util_po2_from_log2(unsigned int value);<\/pre>\n
Diese 5 Funktionen sind besonders dann von Nutzen, wenn man eine Bitmaske vor sich hat, in der die Bitreihenfolge eine gewisse Priorit\u00e4t hat.<\/p>\n
Eine h\u00e4ufig in diesem Zusammenhang ben\u00f6tigte Funktion ist das Abfragen, ob genau ein Bit gesetzt ist. Dies l\u00e4sst sich mit der folgenden Funktion realisieren.<\/p>\n
inline int util_is_power_of_two(ULONG value) {\r\n    \/\/Check for Power Of Two given value can be Zero\r\n    return value && (value & (value - 1));\r\n}<\/pre>\n
Der Trick hierbei besteht darin, auf die Bin\u00e4rschreibweise und der von der CPU sowieso implementierten Logik hinzuarbeiten. Eine Zweierpotenz hat in Bin\u00e4rdarstellung n\u00e4mlich die Eigenschaft genau eine 1 zu besitzen, was somit ein h\u00e4ufiges, \u00e4quivalentes Problem darstellt. Nimmt man nun den Vorg\u00e4nger einer Zweierpotenz, so werden sich alle Bits beider Zahlen unterscheiden, da das einzige gesetzte Bit der Zweierpotenz f\u00fcr den \u00dcbertrag der Subtraktion hergenommen wird.<\/p>\n
Wer sich nun wundert, warum explizit auf ungleich 0 gepr\u00fcft wird, wird durch kurzes Einsetzen, dass diese Bedingung f\u00fcr 0 genauso gilt, wie auch f\u00fcr Zweierpotenzen, weshalb sie explizit ausgeschlossen werden muss, wenn man dies nicht m\u00f6chte. Wei\u00df man jedoch, z.B. durch eine vorherige Abfrage, dass value immer ungleich 0 sein wird, so verk\u00fcrzt sich der Quelltext der Funktion auf folgenden:<\/p>\n
inline int util_is_power_of_two_nz(ULONG value) {\r\n    \/\/Check for Power Of Two given value is Non-Zero\r\n    return (value & (value - 1));\r\n}<\/pre>\n
Dieses Zahlenkonstrukt hat jedoch auch noch einen weiteren Vorteil: Man kann damit recht bequem das niedrigste gesetzte Bit einer Zahl ermitteln, weshalb ich explizit auf die Priorisierung innerhalb der Bitsets hinwies, da sich diese recht einfach realisieren l\u00e4sst.<\/p>\n
inline ULONG util_get_least_significant_bit(ULONG value) {\r\n    \/\/Get the least significant bit that was set\r\n    \/\/Always returns a power of two OR zero if value was zero at the start\r\n    return value ^ (value & (value - 1));\r\n}<\/pre>\n
Nachdem man nun eine Bitmaske eines einzelnen Bits hat, ist es sicherlich f\u00fcr die meisten Anwendungen zudem interessant, zu erfahren welchen Index das besagte Bit hat. Auch hier kann man mit ein wenig Arbeit den \u00fcblichen Schleifen-Ansatz schlagen:<\/p>\n
inline unsigned int util_log2_from_po2(ULONG value) {\r\n    \/\/Get Log2 given value is a Power Of Two\r\n    \/\/Returns zero if value is zero, even though value=0 is no valid input\r\n    register unsigned int r = 0;\r\n    r |= (value & 0xFFFF0000) != 0;\r\n    r += r;\r\n    r |= (value & 0xFF00FF00) != 0;\r\n    r += r;\r\n    r |= (value & 0xF0F0F0F0) != 0;\r\n    r += r;\r\n    r |= (value & 0xCCCCCCCC) != 0;\r\n    r += r;\r\n    r |= (value & 0xAAAAAAAA) != 0;\r\n    return r;\r\n}<\/pre>\n
Der Trick besteht dabei darin, dass man mit Hilfe der Bitmasken sich immer genau jene Bits der Zahl raussucht, die eine gewisse Wertigkeit besitzen: In der ersten Zeile alle Bits gr\u00f6\u00dfer 16, in der zweiten all jene, die in ihrer Bitnummer das Bit f\u00fcr die 8 gesetzt haben, u.s.w. Wichtig hierbei ist der Vergleich auf != 0 am Ende jeder Zeile, mit dem sichergestellt wird, dass der Boolean-Wert auf 0\/1 normiert wird, da sonst die Arbeit mit der Bitmaske nicht sauber funktioniert.<\/p>\n
Bliebe noch eine letzte Routine, die in diesem Zusammenhang sicherlich auftauchen wird, \u00fcbrig: Umwandeln einer Bitnummer in die zugeh\u00f6rige Bitmaske. Es existieren hier sicherlich auch Ans\u00e4tze mit Hilfe einer Lookup-Table, wobei dieser Ansatz mit wesentlich weniger Speicher auskommt:<\/p>\n
inline ULONG util_po2_from_log2(unsigned int value) {\r\n    register ULONG r = ~0;\r\n    r &= 0x0000FFFF ^ (- !(value & 0x10));\r\n    r &= 0x00FF00FF ^ (- !(value & 0x08));\r\n    r &= 0x0F0F0F0F ^ (- !(value & 0x04));\r\n    r &= 0x33333333 ^ (- !(value & 0x02));\r\n    r &= 0x55555555 ^ (- !(value & 0x01));\r\n    return r;\r\n}<\/pre>\n
Der Ansatz geht auch hier wieder \u00fcber das Zerlegen von Bitsets, wobei diesmal immer all jene Bits ausgeblendet werden, die f\u00fcr die aktuelle Maske nicht zutreffen k\u00f6nnen. Dieser Ansatz ist im Wesentlichen eine Umkehrung der vorigen Routine, um ein Bitset in seine zugeh\u00f6rige Bitnummer zu \u00fcberf\u00fchren. Wie sich doch Quelltext manchmal gleicht \ud83d\ude09<\/p>\n
\"Flattr<\/a><\/p>","protected":false},"excerpt":{"rendered":"
Da ich in letzter Zeit doch etwas h\u00e4ufiger auf Bitebene arbeiten musste, und dabei immer wieder \u00e4hnliche Aufgaben anfielen, kam die Frage auf, wie bestimmte Aktionen am Einfachsten zu l\u00f6sen sind. Viele Operationen sind Straight Forward zwar l\u00f6sbar, doch mit Hilfe gewisser Bit Hacks l\u00e4sst sich noch so einiges an Performance gewinnen.<\/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,181,180],"class_list":["post-279","post","type-post","status-publish","format-standard","hentry","category-software","tag-bitsets","tag-optimierung","tag-programmierung"],"_links":{"self":[{"href":"http:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/posts\/279","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.benny-baumann.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=279"}],"version-history":[{"count":5,"href":"http:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/posts\/279\/revisions"}],"predecessor-version":[{"id":291,"href":"http:\/\/blog.benny-baumann.de\/index.php?rest_route=\/wp\/v2\/posts\/279\/revisions\/291"}],"wp:attachment":[{"href":"http:\/\/blog.benny-baumann.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=279"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.benny-baumann.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=279"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.benny-baumann.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=279"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}