Schnelles Vorzeichen einer ganzen Zahl in C

Lesezeit: 4 Minuten

Benutzeravatar von Alex
Alex

Es gibt eine Vorzeichenfunktion in C:

int sign(int x)
{
    if(x > 0) return 1;
    if(x < 0) return -1;
    return 0;
}

Leider sind die Vergleichskosten sehr hoch, daher muss ich die Funktion ändern, um die Anzahl der Vergleiche zu reduzieren.

Folgendes habe ich versucht:

int sign(int x)
{
    int result;
    result = (-1)*(((unsigned int)x)>>31);

    if (x > 0) return 1;

    return result;
}

In diesem Fall bekomme ich nur einen Vergleich.

Gibt es überhaupt eine Möglichkeit Vergleiche zu vermeiden?

BEARBEITEN Mögliches Duplikat gibt keine Antwort auf eine Frage, da alle Antworten C++ sind, verwendet Vergleiche (die ich vermeiden sollte) oder kehrt nicht zurück -1, +1, 0.

  • Siehe stackoverflow.com/questions/1903954/…

    – xanatos

    29. Januar 2013 um 9:50 Uhr

  • Oder genauer gesagt diese Antwort: stackoverflow.com/a/1904074/253056

    – PaulR

    29. Januar 2013 um 9:51 Uhr

  • Ich denke, nach der Kompilierung wird die ursprüngliche Variante mit nur einem Test und zwei bedingten Sprüngen viel schneller sein

    – qPCR4vir

    29. Januar 2013 um 9:53 Uhr

  • Ein guter Compiler sollte die Originalversion ohnehin auf einen verzweigungslosen Befehlsstrom optimieren.

    – PaulR

    29. Januar 2013 um 9:53 Uhr

  • “Vergleichskosten sind sehr hoch” : wieso? Der Vergleich mit Null ist normalerweise billig oder kostenlos, da bei jeder Architektur, die ich kenne, die Statusregisterbits SIGN und ZERO automatisch gesetzt werden.

    – Roddy

    30. Januar 2013 um 19:49 Uhr

Benutzeravatar von NPE
NPE

Zunächst einmal ist der Ganzzahlvergleich sehr billig. Es ist Verzweigung das kann teuer werden (aufgrund des Risikos falscher Vorhersagen in der Verzweigung).

Ich habe Ihre Funktion auf einer Sandy Bridge-Box mit gcc 4.7.2 getestet, und es dauert ungefähr 1,2 ns pro Anruf.

Folgendes ist etwa 25 % schneller, bei etwa 0,9 ns pro Aufruf:

int sign(int x) {
    return (x > 0) - (x < 0);
}

Der Maschinencode für das Obige ist völlig verzweigungslos:

_sign:
    xorl    %eax, %eax
    testl   %edi, %edi
    setg    %al
    shrl    $31, %edi
    subl    %edi, %eax
    ret

Zwei Dinge sind erwähnenswert:

  1. Das Grundleistungsniveau ist sehr hoch.
  2. Das Eliminieren von Verzweigungen verbessert hier zwar die Leistung, aber nicht dramatisch.

Benutzeravatar von Chris Dodd
Chris Dodd

int sign(int x)
{
    // assumes 32-bit int and 2s complement signed shifts work (implementation defined by C spec)
    return (x>>31) | ((unsigned)-x >> 31);
}

Der erste Teil (x>>32) gibt Ihnen -1 für negative Zahlen und 0 für 0 oder positive Zahlen. Der zweite Teil gibt Ihnen 1, wenn x > 0 oder gleich INT_MIN ist, und sonst 0. Oder gibt Ihnen die richtige endgültige Antwort.

Es gibt auch die kanonische return (x > 0) - (x < 0);, aber leider verwenden die meisten Compiler Verzweigungen, um Code dafür zu generieren, obwohl es keine sichtbaren Verzweigungen gibt. Sie können versuchen, es manuell in verzweigungslosen Code umzuwandeln, wie folgt:

int sign(int x)
{
    // assumes 32-bit int/unsigned
    return ((unsigned)-x >> 31) - ((unsigned)x >> 31);
}

Das ist wohl besser als das obige, da es nicht vom implementierungsdefinierten Verhalten abhängt, aber einen subtilen Fehler hat, da es 0 für INT_MIN zurückgibt.

  • Das ist sehr nett. Sie könnten dem INT_MIN-Bug entkommen, indem Sie setzen x|=x>>1 vor der Rückkehr. INT_MIN ist 10000… INT_MIN | INT_MIN>>1 ist 11000 … was sicher negiert werden kann.

    – dodo

    9. Februar 2015 um 19:16 Uhr

  • -x hat den Signed-Overflow UB eingeschaltet INT_MIN. Zuerst werfen, -(unsigned)xwürde dies vermeiden und das gleiche binäre Ergebnis auf einer Zweierkomplementmaschine liefern.

    – Peter Cordes

    17. Dezember 2022 um 17:51 Uhr


int sign(int x) {    
    return (x>>31)|(!!x);
}  

  • Er verwendet den bitweisen Verschiebungsoperator. In manchen Sprachen handelt es sich um eine „Sign-Propagating Right Shift“ (z. B. in JavaScript), was bedeutet, dass sich das Vorzeichen nicht ändert. Verschieben Sie also ALLE Bits eines 32-Bit-Gleitkommas mit x>>31 hinterlässt nur das Zeichen. !!x konvertiert in wahr oder falsch (1 oder 0), dann verknüpft er sie bitweise mit “ODER” (kombiniert die Bits).

    – James Wilkins

    30. September 2017 um 20:59 Uhr

  • Das Verschieben von vorzeichenbehafteten Ganzzahlen nach rechts ist undefiniertes Verhalten! Sie müssen es in einen vorzeichenlosen Integer-Typ umwandeln: return ((unsigned)x>>31)|(!!x)

    – osven

    28. Oktober 2017 um 16:46 Uhr


  • Nicht nur das, sondern davon ausgehen int ist 32 Bit ist völlig nicht portabel – Sie können wahrscheinlich erwarten, dass es so ist sizeof (int) * CHAR_BIT Bits. Eine Sache, die Sie nicht annehmen können, ist, dass negative Zahlen eine bestimmte Codierung haben; Vorzeichengröße, Einerkomplement und Zweierkomplement sind wohlbekannte Möglichkeiten, aber C beschränkt Implementierungen nicht darauf, eine davon zu sein.

    – Toby Speight

    10. April 2018 um 14:41 Uhr

  • @osvein Tut mir leid, deine Variante gibt fälschlicherweise zurück 1 auf alle negativen Werte für x. Das ist nicht das, was der ursprüngliche Poster wollte.

    – Kai Petzke

    8. Oktober 2020 um 17:00 Uhr

Benutzeravatar von anatolyg
anatolyg

Wenn s(x) ist eine Funktion, die das Vorzeichen-Bit von zurückgibt x (Sie haben es implementiert von ((unsigned int)x)>>31), können Sie kombinieren s(x) und s(-x) irgendwie. Hier ist eine “Wahrheitstabelle”:

x > 0: s(x) = 0; s(-x) = 1; Ihre Funktion muss 1 zurückgeben

x < 0: s(x) = 1; s(-x) = 0; Ihre Funktion muss -1 zurückgeben

x = 0: s(x) = 0; s(-x) = 0; Ihre Funktion muss 0 zurückgeben

Sie können sie also wie folgt kombinieren:

s(-x) - s(x)

int i = -10;
if((i & 1 << 31) == 0x80000000)sign = 0;else sign = 1;
//sign 1 = -ve, sign 0 = -ve 

1437590cookie-checkSchnelles Vorzeichen einer ganzen Zahl in C

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy