2013-05-13 14 views
13

Gibt es eine ziemlich standardmäßige C (Linux) -Funktion oder eine code-effiziente, aber gute Lösung, um zwei ganze Zahlen einer beliebigen Größe zu vergleichen?Generische Funktion zum Vergleichen zweier Ganzzahlen?

Ich suche nach etwas mit den Parametern, die int intcmp(const void *a, const void *b, size_t size)a und b für jede praktische Größe size auf ganze Zahlen arbeitet. (memcmp() funktionieren würde (glaube ich), wenn die Architektur war Big-Endian.)

Die Implementierung Ich neige dazu, geht so zu verwenden (mit Verbesserungen von Efficient integer compare function), aber es ist nicht vollständig generisch und hat genug von einem Code-Overhead, dass ich im Allgemeinen denke zweimal, bevor du es einsteckst.

+2

Es gibt immer GMP. – Antimony

+4

Ich bezweifle, dass es dafür eine Standardfunktion gibt. Beachten Sie, dass Ihre Lösung nicht funktioniert, wenn Sie sowohl signierte als auch nicht signierte Typen benötigen. –

+6

Sobald Sie von "Ganzzahlen einer beliebigen Größe" schreiben, denke ich, dass Sie jenseits des Bereichs von "Wenn die Architektur ein großer Endian ist" fallen, da diese Art von niedriger architektonischer Betrachtung keine Ganzzahlen von willkürliche Größe. Stattdessen müssen Sie entscheiden, wie Sie (sagen wir) 1024-Bit-Ganzzahlen darstellen und dann Ihre Funktion entsprechend schreiben möchten. – ruakh

Antwort

0

Ich denke, der folgende Link wird helfen. Sie machen den Vergleich, ohne Komparatoren zu verwenden, um den Code-Overhead gering zu halten. Ich habe den Code, der mit diesem Link verbunden ist, in der Vergangenheit selbst benutzt.

-Gute Hunting-

C program to compare integers without using logical operators?

+0

Wer würde einen solchen Code für die Produktion verwenden und warum? –

+0

Ich würde eine Variation in der Produktion verwenden. Wenn ich die Druckanweisungen beiseite lege, sehe ich Wiederverwendbarkeit, und die Funktion passt zur Aufgabe. –

0

Wenn die Aufrufort die Größe zur Verfügung hat, würde ich es vorziehen, sie als Index dort in einer Look-up-Tabelle zu verwenden, rufen Sie einfach die richtige Funktion richtig Weg.

+0

Es ist eine interessante Idee, aber ich fand http://stackoverflow.com/questions/2662442/c-funktion-pointers-vs-switch und http://stackoverflow.com/questions/2293655/if-switch-and-function -Pointer-Speed-Vergleich, der darauf hindeutet, dass es nicht viel Nutzen gegenüber der Verwendung von 'switch' geben kann. – antak

1

Wenn Sie wirklich gute Vergleiche von Ganzzahlen beliebiger Größe benötigen, empfehle ich Ihnen, sich The GNU Multiple Precision Arithmetic Library anzusehen. Dazu müssen Sie den speziellen mpz_t-Typ verwenden (der die Länge enthält). Dann können Sie die Funktion int mpz_cmp(mpz_t op1, mpz_t op2) verwenden. Es ist nicht trivial, die eigene Darstellung großer Ganzzahlen zu entscheiden und sie so zu implementieren, dass sie sowohl tragbar als auch effizient ist.

Wenn Sie auf der anderen Seite nur die Standard-Integer-Größen benötigen, die Sie erwähnen, denke ich, dass Ihre Implementierung in Ordnung ist. Aber für eine noch bessere Portabilität sollten Sie keine Annahmen über die verschiedenen Integer-Größen machen:

#include <stdint.h> 

int intcmp(const void *a, const void *b, size_t size) { 
    switch (size) { 
    case 1: return (*(int8_t*)a > *(int8_t*)b) - (*(int8_t*)a < *(int8_t*)b) 
    case 2: return (*(int16_t*)a > *(int16_t*)b) - (*(int16_t*)a < *(int16_t*)b) 
    case 4: return (*(int32_t*)a > *(int32_t*)b) - (*(int32_t*)a < *(int32_t*)b) 
    case 8: return (*(int64_t*)a > *(int64_t*)b) - (*(int64_t*)a < *(int64_t*)b) 
    } 

    assert(0); 
    return 0; 
} 

Vielleicht werden Sie es besser finden eine separate Funktion für jede Länge müssen Sie stattdessen zu erstellen, die für alle gleich mit? Und schließlich, wenn die Effizienz wichtig ist, ist es oft weniger effizient, Arithmetik mit char oder short als mit int. Versuchen Sie also, die Fälle zu vermeiden, in denen Sie diese Funktion mit char oder short aufrufen müssen, und verwenden Sie stattdessen int.

+0

Das Problem dabei ist, dass es undefiniertes Verhalten aufruft, wenn "a" eine große negative Zahl und "b" eine große positive Zahl ist oder umgekehrt. Sie stoßen auf einen arithmetischen Überlauf mit Vorzeichen, der in der Praxis oft gutartig ist, aber formell undefiniert ist und zu fast jedem Preis vermieden werden sollte. Die Namen "sint8_t' et al." Sind nicht definiert in "" gemäß dem C-Standard; Die Typen mit Vorzeichen als "int8_t" und die Typen ohne Vorzeichen sind "uint8_t". Ich benutze manchmal die 'sintN_t' Namen, aber ich weiß, dass es eine nicht standardmäßige Erweiterung ist. –

+0

Ja, Sie haben Recht. Ich habe die Änderungen vorgenommen, um Ihre Kommentare zu reflektieren. – Fabel

2

Statische Inline-Funktionen haben den Vorteil, dass die Argumente nur einmal ausgewertet werden (dies ist mit Makros schwer/unmöglich). Dies würde Funktionsaufrufe wie int diff = cmp_all (p++, q++, sizeof *p); ermöglichen:

#include <stdlib.h> 
#include <stdint.h> 

static inline int cmp1(const int8_t *one, const int8_t *two) 
{ 
if (*one < *two) return -1; 
else if (*one > *two) return 1; 
else return 0; 
} 

static inline int cmp2(const int16_t *one, const int16_t *two) 
{ 
if (*one < *two) return -1; 
else if (*one > *two) return 1; 
else return 0; 
} 

static inline int cmp4(const int32_t *one, const int32_t *two) 
{ 
if (*one < *two) return -1; 
else if (*one > *two) return 1; 
else return 0; 
} 

static inline int cmp8(const int64_t *one, const int64_t *two) 
{ 
if (*one < *two) return -1; 
else if (*one > *two) return 1; 
else return 0; 
} 

int cmp_all(const void *one, const void *two, size_t size) 
{ 
switch(size) { 
case 1: return cmp1(one, two); 
case 2: return cmp2(one, two); 
case 4: return cmp4(one, two); 
case 8: return cmp8(one, two); 
default: return 0; /* that will teach them ... */ 
     } 
} 
Verwandte Themen