Visual Basic - Technik, FAQ, Tricks, Beispiele

Home / Allgemein / Bits / Shift

Bit-Schiebereien

Historie
01.12.2001Erste ShiftLeft-Versionen
10.10.2001Korrigiertes ShiftRight für negative Zahlen
03.10.2001Erste ShiftRight-Versionen;
VBspeed Champion

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

© Jost Schwider, 03.10.2001-01.12.2001 - http://vb-tec.de/bitshift.htm