Da ich in letzter Zeit doch etwas häufiger auf Bitebene arbeiten musste, und dabei immer wieder ähnliche Aufgaben anfielen, kam die Frage auf, wie bestimmte Aktionen am Einfachsten zu lösen sind. Viele Operationen sind Straight Forward zwar lösbar, doch mit Hilfe gewisser Bit Hacks lässt sich noch so einiges an Performance gewinnen.
Was ich im Folgenden einmal genauer beschreiben möchte, sind effiziente Lösungen für die folgenden Funktionen:
inline int util_is_power_of_two(ULONG value);
inline int util_is_power_of_two_nz(ULONG value);
inline ULONG util_get_least_significant_bit(ULONG value);
inline unsigned int util_log2_from_po2(ULONG value);
inline ULONG util_po2_from_log2(unsigned int value);
Diese 5 Funktionen sind besonders dann von Nutzen, wenn man eine Bitmaske vor sich hat, in der die Bitreihenfolge eine gewisse Priorität hat.
Eine häufig in diesem Zusammenhang benötigte Funktion ist das Abfragen, ob genau ein Bit gesetzt ist. Dies lässt sich mit der folgenden Funktion realisieren.
inline int util_is_power_of_two(ULONG value) {
//Check for Power Of Two given value can be Zero
return value && (value & (value - 1));
}
Der Trick hierbei besteht darin, auf die Binärschreibweise und der von der CPU sowieso implementierten Logik hinzuarbeiten. Eine Zweierpotenz hat in Binärdarstellung nämlich die Eigenschaft genau eine 1 zu besitzen, was somit ein häufiges, äquivalentes Problem darstellt. Nimmt man nun den Vorgänger einer Zweierpotenz, so werden sich alle Bits beider Zahlen unterscheiden, da das einzige gesetzte Bit der Zweierpotenz für den Übertrag der Subtraktion hergenommen wird.
Wer sich nun wundert, warum explizit auf ungleich 0 geprüft wird, wird durch kurzes Einsetzen, dass diese Bedingung für 0 genauso gilt, wie auch für Zweierpotenzen, weshalb sie explizit ausgeschlossen werden muss, wenn man dies nicht möchte. Weiß man jedoch, z.B. durch eine vorherige Abfrage, dass value immer ungleich 0 sein wird, so verkürzt sich der Quelltext der Funktion auf folgenden:
inline int util_is_power_of_two_nz(ULONG value) {
//Check for Power Of Two given value is Non-Zero
return (value & (value - 1));
}
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ässt.
inline ULONG util_get_least_significant_bit(ULONG value) {
//Get the least significant bit that was set
//Always returns a power of two OR zero if value was zero at the start
return value ^ (value & (value - 1));
}
Nachdem man nun eine Bitmaske eines einzelnen Bits hat, ist es sicherlich für die meisten Anwendungen zudem interessant, zu erfahren welchen Index das besagte Bit hat. Auch hier kann man mit ein wenig Arbeit den üblichen Schleifen-Ansatz schlagen:
inline unsigned int util_log2_from_po2(ULONG value) {
//Get Log2 given value is a Power Of Two
//Returns zero if value is zero, even though value=0 is no valid input
register unsigned int r = 0;
r |= (value & 0xFFFF0000) != 0;
r += r;
r |= (value & 0xFF00FF00) != 0;
r += r;
r |= (value & 0xF0F0F0F0) != 0;
r += r;
r |= (value & 0xCCCCCCCC) != 0;
r += r;
r |= (value & 0xAAAAAAAA) != 0;
return r;
}
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ößer 16, in der zweiten all jene, die in ihrer Bitnummer das Bit für 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.
Bliebe noch eine letzte Routine, die in diesem Zusammenhang sicherlich auftauchen wird, übrig: Umwandeln einer Bitnummer in die zugehörige Bitmaske. Es existieren hier sicherlich auch Ansätze mit Hilfe einer Lookup-Table, wobei dieser Ansatz mit wesentlich weniger Speicher auskommt:
inline ULONG util_po2_from_log2(unsigned int value) {
register ULONG r = ~0;
r &= 0x0000FFFF ^ (- !(value & 0x10));
r &= 0x00FF00FF ^ (- !(value & 0x08));
r &= 0x0F0F0F0F ^ (- !(value & 0x04));
r &= 0x33333333 ^ (- !(value & 0x02));
r &= 0x55555555 ^ (- !(value & 0x01));
return r;
}
Der Ansatz geht auch hier wieder über das Zerlegen von Bitsets, wobei diesmal immer all jene Bits ausgeblendet werden, die für die aktuelle Maske nicht zutreffen können. Dieser Ansatz ist im Wesentlichen eine Umkehrung der vorigen Routine, um ein Bitset in seine zugehörige Bitnummer zu überführen. Wie sich doch Quelltext manchmal gleicht 😉
