Was ist deine liebste bitweise Technik? [geschlossen]

Vor einigen Tagen erkundigte sich StackExchange-Mitglied Anto nach gültigen Verwendungen für bitweise Operatoren. Ich stellte fest, dass die Verschiebung schneller war als das Multiplizieren und Teilen von ganzen Zahlen durch Zweierpotenzen. StackExchange-Mitglied Daemin konterte mit der Feststellung, dass Rechtsverschiebung Probleme mit negativen Zahlen aufwerfe.

Zu diesem Zeitpunkt hatte ich nie wirklich darüber nachgedacht, die Schichtoperatoren mit vorzeichenbehafteten ganzen Zahlen zu verwenden. Ich habe diese Technik hauptsächlich in der Low-Level-Softwareentwicklung eingesetzt. Daher habe ich immer ganze Zahlen ohne Vorzeichen verwendet. C führt logische Verschiebungen an vorzeichenlosen ganzen Zahlen durch. Beim Durchführen einer logischen Rechtsverschiebung wird dem Vorzeichenbit keine Beachtung geschenkt. Freie Bits werden mit Nullen gefüllt. C führt jedoch eine arithmetische Verschiebeoperation durch, wenn eine Ganzzahl mit Vorzeichen nach rechts verschoben wird. Freie Bits werden mit dem Vorzeichenbit gefüllt. Diese Differenz bewirkt, dass ein negativer Wert gegen Unendlich gerundet wird, anstatt gegen Null abgeschnitten zu werden. Dies ist ein anderes Verhalten als die Ganzzahldivision mit Vorzeichen.

Ein paar Minuten des Nachdenkens führten zu einer Lösung erster Ordnung. Die Lösung wandelt negative Werte vor dem Verschieben bedingt in positive Werte um. Ein Wert wird nach Ausführung der Verschiebung bedingt in seine negative Form zurückgewandelt.

int a = -5;
int n = 1;

int negative = q < 0; 

a = negative ? -a : a; 
a >>= n; 
a = negative ? -a : a; 

Das Problem bei dieser Lösung besteht darin, dass bedingte Zuweisungsanweisungen normalerweise in mindestens einen Sprungbefehl übersetzt werden und Sprungbefehle auf Prozessoren, die nicht beide Befehlspfade decodieren, teuer sein können. Eine Anweisungs-Pipeline zweimal neu vorbereiten zu müssen, wirkt sich positiv auf den Leistungszuwachs aus, der durch Verschieben über Teilen erzielt wird.

Mit dem oben Gesagten bin ich am Samstag mit der Antwort auf das Problem der bedingten Zuweisung aufgewacht. Das Rundungsproblem, das bei der Ausführung einer arithmetischen Verschiebungsoperation auftritt, tritt nur auf, wenn mit der Zweierkomplementdarstellung gearbeitet wird. Es kommt bei der eigenen Komplementdarstellung nicht vor. Die Lösung des Problems besteht darin, den Zweierkomplementwert vor dem Durchführen der Verschiebeoperation in einen Einerkomplementwert umzuwandeln. Wir müssen dann den Einerkomplementwert zurück in einen Zweikomplementwert umrechnen. Überraschenderweise können wir diesen Satz von Operationen ausführen, ohne negative Werte vor dem Ausführen der Verschiebeoperation bedingt zu konvertieren.

int a = -5;
int n = 1;

register int sign = (a >> INT_SIZE_MINUS_1) & 1

a = (a - sign) >> n + sign;   

Der negative Wert des Zweierkomplements wird durch Subtrahieren von Eins in den negativen Wert des Einerkomplements umgewandelt. Auf der anderen Seite wird der negative Wert eines Einerkomplements durch Addieren von Eins in den negativen Wert eines Zweikomplements umgewandelt. Der oben aufgeführte Code funktioniert, weil das Vorzeichenbit zum Konvertieren des Zweierkomplements in das eigene Komplement und umgekehrt verwendet wird . Nur bei negativen Werten werden die Vorzeichenbits gesetzt. Daher ist das variable Vorzeichen gleich Null, wenn a positiv ist.

Können Sie sich mit dem oben Gesagten andere bissige Hacks wie den oben genannten vorstellen, die es in Ihre Trickkiste geschafft haben? Was ist dein liebster bitweiser Hack? Ich bin immer auf der Suche nach neuen leistungsorientierten bitweisen Hacks.

Ich liebe Gospers Hack (HAKMEM # 175), eine sehr raffinierte Art, eine Zahl zu nehmen und die nächste Zahl mit der gleichen Anzahl von gesetzten Bits zu erhalten. Es ist zum Beispiel nützlich, um Kombinationen von kGegenständen aus nfolgenden Elementen zu generieren:

int set = (1 << k) - 1;
int limit = (1 << n);
while (set < limit) {
    doStuff(set);

    // Gosper's hack:
    int c = set & -set;
    int r = set + c;
    set = (((r^set) >>> 2) / c) | r;
}

Die Methode der schnellen inversen Quadratwurzel verwendet die bizarrsten Techniken auf Bitebene, um die Inverse einer Quadratwurzel zu berechnen, die ich je gesehen habe:

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    //    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

Division durch 3 - ohne auf einen Laufzeitbibliotheksaufruf zurückzugreifen.

Es stellt sich heraus, dass die Division durch 3 (dank eines Hinweises auf Stack Overflow) angenähert werden kann als:

X / 3 = [(x / 4) + (x / 12)]

Und X / 12 ist (x / 4) / 3. Hier taucht plötzlich ein Element der Rekursion auf.

Es stellt sich außerdem heraus, dass Sie die Anzahl der erforderlichen Iterationen begrenzen können, wenn Sie den Bereich der Zahlen einschränken, in denen Sie spielen.

Für vorzeichenlose ganze Zahlen <2000 ist der folgende Algorithmus ein schneller und einfacher / 3-Algorithmus. (Für größere Zahlen fügen Sie einfach weitere Schritte hinzu). Compiler optimieren das Ganze so, dass es schnell und klein wird:

statische vorzeichenlose kurze FastDivide3 (const vorzeichenlose kurze arg)
{
  unsigned short RunningSum;
  unsigned short FractionalTwelth;

  RunningSum = arg >> 2;

  FractionalTwelth = RunningSum >> 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  // Weitere Wiederholungen der obigen 2 Zeilen für mehr Präzision

  return RunningSum;
}

Wenn Sie in Erlang suchen, gibt es eine ganze DSL für Bit-Operationen. SO können Sie eine Datenstruktur einfach nach Bits aufteilen, indem Sie Folgendes sagen:

<> = << 1,17,42: 16 >>.

Alle Details finden Sie hier: http://www.erlang.org/doc/reference_manual/expressions.html#id75782