Zweigloser Code, der Zero, Negativ und positiv auf 0, 1, 2 bildet

Question

Schreiben Sie eine verzweiglose Funktion, die 0, 1 oder 2 zurückgibt, wenn die Differenz zwischen zwei signierten Ganzzahlen Null, negativ oder positiv ist.

Hier ist eine Version mit Verzweigungen:

int Compare(int x, int y)
{
    int diff = x - y;
    if (diff == 0)
        return 0;
    else if (diff < 0)
        return 1;
    else
        return 2;
}

Hier ist eine Version, die je nach Compiler und Prozessor schneller sein kann:

int Compare(int x, int y)
{
    int diff = x - y;
    return diff == 0 ? 0 : (diff < 0 ? 1 : 2);
}

Können Sie sich eine schnellere ohne Zweige einfallen lassen?

ZUSAMMENFASSUNG

Die 10 Lösungen, die ich mit dem Benchmarked war, hatten eine ähnliche Leistung. Die tatsächlichen Zahlen und der Gewinner variierten je nach Compiler (ICC/GCC), Compiler -Optionen (z. B. -O3, -March = Nocona, -Fast, -xHost) und Maschine. Die Canon -Lösung hat in vielen Benchmark -Läufen gut abgebildet, Aber wieder war der Leistungsvorteil gering. Ich war überrascht, dass in einigen Fällen einige Lösungen langsamer waren als die naive Lösung mit Zweigen.

Answer 1

int Compare(int x, int y) {
     return (x < y) + (y < x) << 1;
}

Bearbeiten: Nur bitweise? Zählen Sie dann <und> nicht?

int Compare(int x, int y) {
    int diff = x - y;
    return (!!diff) | (!!(diff & 0x80000000) << 1);
}

Aber da ist dieser lästige -.

Bearbeiten: Verschieben Sie sich umgekehrt.

Meh, nur um es erneut zu versuchen:

int Compare(int x, int y) {
    int diff = y - x;
    return (!!diff) << ((diff >> 31) & 1);
}

Aber ich vermute, es gibt keine Standard -ASM -Anweisung für !!. Auch die << kann ersetzt werden durch +, je nachdem, was schneller ist ...

Ein bisschen Twiddling macht Spaß!

Hmm, ich habe gerade etwas gelernt setnz.

Ich habe die Ausgabe des Assemblers nicht überprüft (aber ich habe es diesmal ein bisschen getestet), und mit ein bisschen Glück könnte es speichern eine ganze Anweisung!:

IN DER THEORIE. Mein Assembler ist rostig

subl  %edi, %esi
setnz %eax
sarl  $31, %esi
andl  $1, %esi
sarl  %eax, %esi
mov   %esi, %eax
ret

Streifen macht Spaß.

Ich brauche Schlaf.

Answer 2

Zweigloser (auf Sprachebene) Code, der negativ auf -1, Null bis 0 und positiv auf +1 aussieht wie folgt

int c = (n > 0) - (n < 0);

Wenn Sie eine andere Zuordnung benötigen, können Sie einfach eine explizite Karte verwenden, um sie neu zu gestalten

const int MAP[] = { 1, 0, 2 };
int c = MAP[(n > 0) - (n < 0) + 1];

Oder verwenden Sie für die angeforderte Zuordnung einen numerischen Trick wie

int c = 2 * (n > 0) + (n < 0);

(Es ist offensichtlich sehr einfach, eine Zuordnung daraus zu generieren, solange 0 auf 0 abgebildet ist und der Code ziemlich lesbar ist. Wenn 0 auf etwas anderes zugeordnet ist, wird er schwieriger und weniger lesbar.)

Als additinales Hinweis: Der Vergleich von zwei Ganzzahlen durch Subtrahieren von einem anderen auf C -Sprachebene ist eine fehlerhafte Technik, da sie im Allgemeinen zum Überlauf anfällig ist. Die Schönheit der oben genannten Methoden ist, dass sie sofort für "subtraktionslose" Vergleiche verwendet werden können

int c = 2 * (x > y) + (x < y);

Answer 3

Angenommen, 2S -Komplement, arithmetische rechte Verschiebung und kein Überlauf in der Subtraktion:

#define SHIFT (CHARBIT*sizeof(int) - 1)

int Compare(int x, int y)
{
    int diff = x - y;
    return -(diff >> SHIFT) - (((-diff) >> SHIFT) << 1);
}

Answer 4

Zwei ergänzt:

#include <limits.h>
#define INT_BITS (CHAR_BITS * sizeof (int))

int Compare(int x, int y) {
    int d = y - x;
    int p = (d + INT_MAX) >> (INT_BITS - 1);
    d = d >> (INT_BITS - 2);
    return (d & 2) + (p & 1);
}

Unter der Annahme eines vernünftigen Compilers wird weder die Vergleichshardware Ihres Systems aufgerufen, noch verwendet es einen Vergleich in der Sprache. Um zu überprüfen: Wenn x == y ist, dann ist D und P eindeutig 0, so dass das Endergebnis Null ist. If (x - y)> 0 dann ((x - y) + int_max) setzt das hohe Bit der Ganzzahl, sonst ist er nicht festgelegt. Also wird P sein niedrigstes Bit eingestellt, wenn und nur wenn (x - y)> 0. Wenn (x - y) <0 dann sein hohes Bit eingestellt wird und D das zweite auf das niedrigste Bit einstellt.

Answer 5

Unsignierter Vergleich, der -1,0,1 (CMPU) zurückgibt GNU Superoptimizer.

cmpu: compare (unsigned)
int cmpu(unsigned_word v0, unsigned_word v1)
{
    return ( (v0 > v1) ? 1 : ( (v0 < v1) ? -1 : 0) );
}

Ein Superoptimizer durchsucht den Anweisungsraum ausführlich nach der bestmöglichen Kombination von Anweisungen, die eine bestimmte Funktion implementieren. Es wird vermutet, dass Compiler die oben genannten Funktionen automatisch durch ihre superoptimierten Versionen ersetzen (obwohl nicht alle Compiler dies tun). Zum Beispiel im Powerpc Compiler Writer's Guide (powerpc-cwg.pdf) Die CMPU -Funktion wird in Anhang D S. 204 als diese angezeigt:

cmpu: compare (unsigned)
PowerPC SuperOptimized Version
subf  R5,R4,R3
subfc R6,R3,R4
subfe R7,R4,R3
subfe R8,R7,R5

Das ist ziemlich gut, nicht wahr ... nur vier Subtrahiere (und mit Tragen und/oder erweiterten Versionen). Ganz zu schweigen davon, dass es ist Ehrlich. Es gibt wahrscheinlich eine PC / Intel X86 -äquivalente Sequenz, die ähnlich kurz ist, da der GNU -Superoptimizer sowohl für x86 als auch für PowerPC ausgeführt wird.

Beachten Sie, dass der nicht signierte Vergleich (CMPU) in einem 32-Bit-Vergleich zu einem signierten Vergleich (CMPS) verwandelt werden kann, indem Sie 0x80000000 zu beiden signierten Eingängen hinzufügen, bevor Sie ihn an CMPU übergeben.

cmps: compare (signed)
int cmps(signed_word v0, signed_word v1)
{
    signed_word offset=0x80000000;
    return ( (unsigned_word) (v0 + signed_word),
        (unsigned_word) (v1 + signed_word) );
}

Dies ist jedoch nur eine Option ... Der Superoptimizer findet möglicherweise ein CMPS, das kürzer ist und keine Aussagen hinzufügen und CMPU anrufen muss.

Um die Version zu erhalten, die Sie angefordert haben, die Ihre Werte von {1,0,2} und nicht {-1,0,1} zurückgeben, verwenden Sie den folgenden Code, der die superoptimierte CMPS-Funktion nutzt.

int Compare(int x, int y)
{
    static const int retvals[]={1,0,2};
    return (retvals[cmps(x,y)+1]);
}

Answer 6

Ich bin auf der Seite von Tordeks ursprünglicher Antwort:

int compare(int x, int y) {
    return (x < y) + 2*(y < x);
}

Kompilien mit gcc -O3 -march=pentium4 führt zu iedsfreier Code, der bedingte Anweisungen verwendet setg und setl (Sieh dir das an Erläuterung von x86 Anweisungen).

push   %ebp
mov    %esp,%ebp
mov    %eax,%ecx
xor    %eax,%eax
cmp    %edx,%ecx
setg   %al
add    %eax,%eax
cmp    %edx,%ecx
setl   %dl
movzbl %dl,%edx
add    %edx,%eax
pop    %ebp
ret 

Answer 7

Guter Gott, das hat mich verfolgt.

Was auch immer, ich glaube, ich habe einen letzten Tropfen der Leistung herausgedrückt:

int compare(int a, int b) {
    return (a != b) << (a > b);
}

Obwohl das Kompilieren mit -O3 in GCC geben wird (Bär mit mir, mache ich es aus dem Gedächtnis)

xorl  %eax, %eax
cmpl  %esi, %edi
setne %al
cmpl  %esi, %edi
setgt %dl
sall  %dl, %eax
ret

Aber der zweite Vergleich scheint (nach einigem Test; ich sauge an ASM) überflüssig und lasse die kleinen und schönen

xorl  %eax, %eax
cmpl  %esi, %edi
setne %al
setgt %dl
sall  %dl, %eax
ret

(Sall ist vielleicht keine ASM -Anweisung, aber ich erinnere mich nicht genau)

Also ... wenn es Ihnen nichts ausmacht, Ihren Benchmark noch einmal zu laufen, würde ich gerne die Ergebnisse hören (meine hat eine Verbesserung von 3% gegeben, aber es kann falsch sein).

Answer 8

Kombination von Stephen Canon und Tordeks Antworten:

int Compare(int x, int y)
{
    int diff = x - y; 
    return -(diff >> 31) + (2 & (-diff >> 30));
} 

Ausbeuten: (G ++ -O3)

subl     %esi,%edi 
movl     %edi,%eax
sarl     $31,%edi
negl     %eax
sarl     $30,%eax
andl     $2,%eax
subl     %edi,%eax 
ret 

Fest! Paul Hsiehs Version hat jedoch noch weniger Anweisungen:

subl     %esi,%edi
leal     0x7fffffff(%rdi),%eax
sarl     $30,%edi
andl     $2,%edi
shrl     $31,%eax
leal     (%rdi,%rax,1),%eax
ret

Answer 9

int Compare(int x, int y)
{
    int diff = x - y;

    int absdiff = 0x7fffffff & diff; // diff with sign bit 0
    int absdiff_not_zero = (int) (0 != udiff);

    return
        (absdiff_not_zero << 1)      // 2 iff abs(diff) > 0
        -
        ((0x80000000 & diff) >> 31); // 1 iff diff < 0
}

Answer 10

Versuchen Sie für 32 signierte Ganzzahlen (wie in Java):

return 2 - ((((x >> 30) & 2) + (((x-1) >> 30) & 2))) >> 1;

wo (x >> 30) & 2 kehrt zurück 2 für negative Zahlen und 0 Andernfalls.

x wäre der Unterschied der beiden Eingabezahlen