| Historie | |
| 01.12.2001 | Erste ShiftLeft-Versionen |
| 10.10.2001 | Korrigiertes ShiftRight für negative Zahlen |
| 03.10.2001 | Erste ShiftRight-Versionen; |
Einleitung
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
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.
Konventionelle Lösung: Division durch 2
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.
Potenz-Operator von VB benutzen
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!
Eigene Potenz-Funktion benutzen
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.
Statisches Array benutzen
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).
Triviale Fall-Unterscheidung
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)!
Triviale Fall-Unterscheidung (korrigiert)
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
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.
Statisches Array benutzen
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
Triviale Fall-Unterscheidung
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