Kontakt
DSVGO
Historie | |
01.12.2001 | Erste ShiftLeft-Versionen |
10.10.2001 | Korrigiertes ShiftRight für negative Zahlen |
03.10.2001 | Erste ShiftRight-Versionen; |
Leider kennt VB keine Funktionen, um schnell Bits verschieben zu können. Nachfolgend werden daher Schritt für Schritt Shift-Funktionen realisiert, welche wirklich schnell sind.
Die Quelltexte der optimalen Funktionen sind übrigens hier zu finden: ShiftRight, ShiftLeft.
ShiftRight schiebt alle Bits um eine bestimmte Anzahl von Stellen (0-31) nach rechts. Als Füll-Bit wird das Vorzeichen-Bit (Bit 31) von links nachgeschoben. In C oder Java gibt es dafür den >>-Operator.
Die Grundidee der ShiftRight-Operationen ist diese: Eine Verschiebung um eine Stelle nach rechts entspricht einer Division durch 2. Genau dies wird in folgender Funktion gemacht:
Public Function ShiftRightDiv( _ ByVal Value As Long, _ ByVal Shift As Long _ ) As Long If Shift >= 0 Then For Shift = 1 To Shift Value = Value \ 2 Next Shift ShiftRightDiv = Value End If End Function
Diese Funktion macht genau das gewünschte. Man beachte, dass die Funktion durch die Verwendung der Ganzzahlen-Division optimiert wurde.
Um die obige Schleife zu vermeiden, wird hier der Potenz-Operator genutzt; da 2^31 zu einem Überlauf führen würde, wird dieser Fall extra behandelt:
Public Function ShiftRightPot( _ ByVal Value As Long, _ ByVal Shift As Long _ ) As Long Select Case Shift Case 0 To 30 ShiftRightPot = Value \ 2 ^ Shift Case 31 ShiftRightPot = Value \ &H80000000 End Select End Function
So sieht der Code sehr elegant aus, nicht wahr? In der IDE (Entwicklungsumgebung) ist ShiftRightPot etwa 2,7-mal schneller - ein gutes Ergebnis!
Wirklich wichtig für die Praxis ist aber die kompilierte Version; Bei voller Compiler-Optimierung ergibt sich ein überraschendes Ergebnis: Dann ist ShiftRightPot nämlich um den Faktor 5 langsamer als ShiftRightDiv!
Die Schwachstelle von ShiftRightPot ist der Potenz-Operator, welche zu den Fließkomma-Funktionen gehört. Diese sind deutlich langsamer als Ganzzahlen-Funktionen. Daher benutzt die folgende ShiftRight-Variante eine eigene Potenz-Funktion, die ausschließlich mit Ganzzahlen arbeitet:
Public Function ShiftRightPow( _ ByVal Value As Long, _ ByVal Shift As Long _ ) As Long Select Case Shift Case 0 To 30 ShiftRightPow = Value \ Pow2(Shift) Case 31 ShiftRightPow = Value \ &H80000000 End Select End Function
Der Code sieht wieder sehr elegant aus. In der IDE ergibt sich gegenüber ShiftRightDiv eine Beschleunigung um den Faktor 3,2. Kompiliert ist ShiftRightPow immer noch 1,8-mal so schnell!
Hier nun die gerade benutzte Pow2-Funktion:
Public Static Function Pow2(ByVal Value As Long) As Long Dim i As Long Dim aPow2(0 To 30) As Long If i Then Pow2 = aPow2(Value) Else '2er-Potenzen vorberechnen: aPow2(0) = 1 For i = 1 To 30 aPow2(i) = aPow2(i - 1) * 2 Next i Pow2 = aPow2(Value) End If End Function
Die Pow2-Funktion berechnet beim ersten Aufruf alle 2er-Potenzen "auf Vorrat", d.h. sie werden in einem statischen Array (aPow2) zum Abruf abgelegt.
Das Prinzip der Pow2-Funktion könnte man ja auch direkt in die ShiftRight-Funktion integrieren, d.h. statt erst eine externe Potenz-Funktion aufzurufen, werden beim ersten Aufruf von ShiftRight alle 2er-Potenzen in einem privaten, statischen Array abgelegt. Dadurch kann sogar der Sonderfall Shift=31 gleich mit berücksichtigt werden.
Eine weitere Optimierung in folgender Funktion ist der Check des Shift-Parameters - da nur Werte zwischen 0 und 31 erlaubt sind (also maximal die niedrigsten 5 Bits gesetzt sein dürfen), kann der Select Case-Block durch eine einfache And-Operation ersetzt werden:
Public Static Function ShiftRightArr( _ ByVal Value As Long, _ ByVal Shift As Long _ ) As Long Dim i As Long Dim Pow2(0 To 31) As Long If Shift And &HFFFFFFE0 Then Else If i Then ShiftRightArr = Value \ Pow2(Shift) Else '2er-Potenzen vorberechnen: Pow2(0) = 1 For i = 1 To 30 Pow2(i) = 2 * Pow2(i - 1) Next i Pow2(31) = &H80000000 ShiftRightArr = Value \ Pow2(Shift) End If End If End Function
Die Meßwerte können sich sehen lassen: Sowohl in der IDE (Faktor 5) als auch kompiliert (Faktor 2) ist diese Funktion schneller (Faktoren bzgl. ShiftRightDiv).
Eine ganz andere Möglichkeit zeigt die folgende Funktion - statt umständlich 2er-Potenzen zu berechnen, werden einfach alle möglichen Fälle in einem großen Select Case-Block aufgelistet:
Public Function ShiftRightCase( _ ByVal Value As Long, _ ByVal Shift As Long _ ) As Long Select Case Shift Case 0&: ShiftRightCase = Value Case 1&: ShiftRightCase = Value \ &H2& Case 2&: ShiftRightCase = Value \ &H4& Case 3&: ShiftRightCase = Value \ &H8& Case 4&: ShiftRightCase = Value \ &H10& Case 5&: ShiftRightCase = Value \ &H20& Case 6&: ShiftRightCase = Value \ &H40& Case 7&: ShiftRightCase = Value \ &H80& Case 8&: ShiftRightCase = Value \ &H100& Case 9&: ShiftRightCase = Value \ &H200& Case 10&: ShiftRightCase = Value \ &H400& Case 11&: ShiftRightCase = Value \ &H800& Case 12&: ShiftRightCase = Value \ &H1000& Case 13&: ShiftRightCase = Value \ &H2000& Case 14&: ShiftRightCase = Value \ &H4000& Case 15&: ShiftRightCase = Value \ &H8000& Case 16&: ShiftRightCase = Value \ &H10000 Case 17&: ShiftRightCase = Value \ &H20000 Case 18&: ShiftRightCase = Value \ &H40000 Case 19&: ShiftRightCase = Value \ &H80000 Case 20&: ShiftRightCase = Value \ &H100000 Case 21&: ShiftRightCase = Value \ &H200000 Case 22&: ShiftRightCase = Value \ &H400000 Case 23&: ShiftRightCase = Value \ &H800000 Case 24&: ShiftRightCase = Value \ &H1000000 Case 25&: ShiftRightCase = Value \ &H2000000 Case 26&: ShiftRightCase = Value \ &H4000000 Case 27&: ShiftRightCase = Value \ &H8000000 Case 28&: ShiftRightCase = Value \ &H10000000 Case 29&: ShiftRightCase = Value \ &H20000000 Case 30&: ShiftRightCase = Value \ &H40000000 Case 31&: ShiftRightCase = Value \ &H80000000 End Select End Function
Nun, kann das überhaupt schnell sein? In der IDE ist diese Version tatsächlich "nur" 3-mal so schnell wie ShiftRightDiv, also deutlich langsamer als z.B. ShiftRightArr. Das war ja auch zu befürchten, da ja VB mühselig den richtigen Fall suchen muss.
Betrachtet man allerdings die kompilierte Version (Praxis-relevant!), so sieht das Ergebnis überraschenderweise ganz anders aus: Hier ist ShiftRightCase 5,6-mal schneller als ShiftRightDiv, unabhängig vom Shift-Parameter! Offensichtlich macht der Compiler seine Sache wirklich gut (vermutlich Umsetzung durch binäre Suche)!
Leider funktionieren die bisher vorgestellten Routinen für negative Zahlen nicht 100%-ig korrekt, da die Ganzzahlen-Division nicht wie gewünscht/erwartet abrundet (aus -7 \ 4 wird -1 statt -2). Daher muss der "Nachkomma-Teil" via And-Operator ausgeblendet werden:
Public Function ShiftRight( _ ByVal Value As Long, _ ByVal Shift As Long _ ) As Long Select Case Shift Case 0&: ShiftRight = Value Case 1&: ShiftRight = (Value And &HFFFFFFFE) \ &H2& Case 2&: ShiftRight = (Value And &HFFFFFFFC) \ &H4& Case 3&: ShiftRight = (Value And &HFFFFFFF8) \ &H8& Case 4&: ShiftRight = (Value And &HFFFFFFF0) \ &H10& Case 5&: ShiftRight = (Value And &HFFFFFFE0) \ &H20& Case 6&: ShiftRight = (Value And &HFFFFFFC0) \ &H40& Case 7&: ShiftRight = (Value And &HFFFFFF80) \ &H80& Case 8&: ShiftRight = (Value And &HFFFFFF00) \ &H100& Case 9&: ShiftRight = (Value And &HFFFFFE00) \ &H200& Case 10&: ShiftRight = (Value And &HFFFFFC00) \ &H400& Case 11&: ShiftRight = (Value And &HFFFFF800) \ &H800& Case 12&: ShiftRight = (Value And &HFFFFF000) \ &H1000& Case 13&: ShiftRight = (Value And &HFFFFE000) \ &H2000& Case 14&: ShiftRight = (Value And &HFFFFC000) \ &H4000& Case 15&: ShiftRight = (Value And &HFFFF8000) \ &H8000& Case 16&: ShiftRight = (Value And &HFFFF0000) \ &H10000 Case 17&: ShiftRight = (Value And &HFFFE0000) \ &H20000 Case 18&: ShiftRight = (Value And &HFFFC0000) \ &H40000 Case 19&: ShiftRight = (Value And &HFFF80000) \ &H80000 Case 20&: ShiftRight = (Value And &HFFF00000) \ &H100000 Case 21&: ShiftRight = (Value And &HFFE00000) \ &H200000 Case 22&: ShiftRight = (Value And &HFFC00000) \ &H400000 Case 23&: ShiftRight = (Value And &HFF800000) \ &H800000 Case 24&: ShiftRight = (Value And &HFF000000) \ &H1000000 Case 25&: ShiftRight = (Value And &HFE000000) \ &H2000000 Case 26&: ShiftRight = (Value And &HFC000000) \ &H4000000 Case 27&: ShiftRight = (Value And &HF8000000) \ &H8000000 Case 28&: ShiftRight = (Value And &HF0000000) \ &H10000000 Case 29&: ShiftRight = (Value And &HE0000000) \ &H20000000 Case 30&: ShiftRight = (Value And &HC0000000) \ &H40000000 Case 31&: ShiftRight = CBool(Value And &H80000000) End Select End Function
ShiftLeft schiebt alle Bits um eine bestimmte Anzahl von Stellen (0-31) nach links. Als Füll-Bit wird eine Null (0) von rechts nachgeschoben. In C oder Java gibt es dafür den <<-Operator.
Das Prinzip wurde ja bereits für ShiftRight erläutert.
Public Static Function ShiftLeftArr( _ ByVal Value As Long, _ ByVal ShiftCount As Long _ ) As Long Dim i As Long Dim Pow2(0 To 31) As Long Dim Mask As Long Select Case ShiftCount Case 1 To 31 'Ggf. 2er-Potenzen berechnen: If i = 0 Then Pow2(0) = 1 For i = 1 To 30 Pow2(i) = 2 * Pow2(i - 1) Next i End If 'Los gehts: Mask = Pow2(31 - ShiftCount) If Value And Mask Then ShiftLeftArr = (Value And (Mask - 1)) * Pow2(ShiftCount) Or &H80000000 Else ShiftLeftArr = (Value And (Mask - 1)) * Pow2(ShiftCount) End If Case 0 ShiftLeftArr = Value End Select End Function
Das Prinzip wurde ja bereits für ShiftRight erläutert. Bei ShiftLeft ergibt sich wegen des potenziellen Überlaufs und der speziellen Beachtung des Vorzeichens (Bit 31) ein extrem langer (aber sehr schneller!) Code:
Public Function ShiftLeft( _ ByVal Value As Long, _ ByVal ShiftCount As Long _ ) As Long Select Case ShiftCount Case 0& ShiftLeft = Value Case 1& If Value And &H40000000 Then ShiftLeft = (Value And &H3FFFFFFF) * &H2& Or &H80000000 Else ShiftLeft = (Value And &H3FFFFFFF) * &H2& End If Case 2& If Value And &H20000000 Then ShiftLeft = (Value And &H1FFFFFFF) * &H4& Or &H80000000 Else ShiftLeft = (Value And &H1FFFFFFF) * &H4& End If Case 3& If Value And &H10000000 Then ShiftLeft = (Value And &HFFFFFFF) * &H8& Or &H80000000 Else ShiftLeft = (Value And &HFFFFFFF) * &H8& End If Case 4& If Value And &H8000000 Then ShiftLeft = (Value And &H7FFFFFF) * &H10& Or &H80000000 Else ShiftLeft = (Value And &H7FFFFFF) * &H10& End If Case 5& If Value And &H4000000 Then ShiftLeft = (Value And &H3FFFFFF) * &H20& Or &H80000000 Else ShiftLeft = (Value And &H3FFFFFF) * &H20& End If Case 6& If Value And &H2000000 Then ShiftLeft = (Value And &H1FFFFFF) * &H40& Or &H80000000 Else ShiftLeft = (Value And &H1FFFFFF) * &H40& End If Case 7& If Value And &H1000000 Then ShiftLeft = (Value And &HFFFFFF) * &H80& Or &H80000000 Else ShiftLeft = (Value And &HFFFFFF) * &H80& End If Case 8& If Value And &H800000 Then ShiftLeft = (Value And &H7FFFFF) * &H100& Or &H80000000 Else ShiftLeft = (Value And &H7FFFFF) * &H100& End If Case 9& If Value And &H400000 Then ShiftLeft = (Value And &H3FFFFF) * &H200& Or &H80000000 Else ShiftLeft = (Value And &H3FFFFF) * &H200& End If Case 10& If Value And &H200000 Then ShiftLeft = (Value And &H1FFFFF) * &H400& Or &H80000000 Else ShiftLeft = (Value And &H1FFFFF) * &H400& End If Case 11& If Value And &H100000 Then ShiftLeft = (Value And &HFFFFF) * &H800& Or &H80000000 Else ShiftLeft = (Value And &HFFFFF) * &H800& End If Case 12& If Value And &H80000 Then ShiftLeft = (Value And &H7FFFF) * &H1000& Or &H80000000 Else ShiftLeft = (Value And &H7FFFF) * &H1000& End If Case 13& If Value And &H40000 Then ShiftLeft = (Value And &H3FFFF) * &H2000& Or &H80000000 Else ShiftLeft = (Value And &H3FFFF) * &H2000& End If Case 14& If Value And &H20000 Then ShiftLeft = (Value And &H1FFFF) * &H4000& Or &H80000000 Else ShiftLeft = (Value And &H1FFFF) * &H4000& End If Case 15& If Value And &H10000 Then ShiftLeft = (Value And &HFFFF&) * &H8000& Or &H80000000 Else ShiftLeft = (Value And &HFFFF&) * &H8000& End If Case 16& If Value And &H8000& Then ShiftLeft = (Value And &H7FFF&) * &H10000 Or &H80000000 Else ShiftLeft = (Value And &H7FFF&) * &H10000 End If Case 17& If Value And &H4000& Then ShiftLeft = (Value And &H3FFF&) * &H20000 Or &H80000000 Else ShiftLeft = (Value And &H3FFF&) * &H20000 End If Case 18& If Value And &H2000& Then ShiftLeft = (Value And &H1FFF&) * &H40000 Or &H80000000 Else ShiftLeft = (Value And &H1FFF&) * &H40000 End If Case 19& If Value And &H1000& Then ShiftLeft = (Value And &HFFF&) * &H80000 Or &H80000000 Else ShiftLeft = (Value And &HFFF&) * &H80000 End If Case 20& If Value And &H800& Then ShiftLeft = (Value And &H7FF&) * &H100000 Or &H80000000 Else ShiftLeft = (Value And &H7FF&) * &H100000 End If Case 21& If Value And &H400& Then ShiftLeft = (Value And &H3FF&) * &H200000 Or &H80000000 Else ShiftLeft = (Value And &H3FF&) * &H200000 End If Case 22& If Value And &H200& Then ShiftLeft = (Value And &H1FF&) * &H400000 Or &H80000000 Else ShiftLeft = (Value And &H1FF&) * &H400000 End If Case 23& If Value And &H100& Then ShiftLeft = (Value And &HFF&) * &H800000 Or &H80000000 Else ShiftLeft = (Value And &HFF&) * &H800000 End If Case 24& If Value And &H80& Then ShiftLeft = (Value And &H7F&) * &H1000000 Or &H80000000 Else ShiftLeft = (Value And &H7F&) * &H1000000 End If Case 25& If Value And &H40& Then ShiftLeft = (Value And &H3F&) * &H2000000 Or &H80000000 Else ShiftLeft = (Value And &H3F&) * &H2000000 End If Case 26& If Value And &H20& Then ShiftLeft = (Value And &H1F&) * &H4000000 Or &H80000000 Else ShiftLeft = (Value And &H1F&) * &H4000000 End If Case 27& If Value And &H10& Then ShiftLeft = (Value And &HF&) * &H8000000 Or &H80000000 Else ShiftLeft = (Value And &HF&) * &H8000000 End If Case 28& If Value And &H8& Then ShiftLeft = (Value And &H7&) * &H10000000 Or &H80000000 Else ShiftLeft = (Value And &H7&) * &H10000000 End If Case 29& If Value And &H4& Then ShiftLeft = (Value And &H3&) * &H20000000 Or &H80000000 Else ShiftLeft = (Value And &H3&) * &H20000000 End If Case 30& If Value And &H2& Then ShiftLeft = (Value And &H1&) * &H40000000 Or &H80000000 Else ShiftLeft = (Value And &H1&) * &H40000000 End If Case 31& If Value And &H1& Then ShiftLeft = &H80000000 Else ShiftLeft = &H0& End If End Select End Function
© Jost Schwider, 03.10.2001-01.12.2001 - http://vb-tec.de/bitshift.htm