In dieser verwandten Frage geht es darum, den maximalen Wert eines signierten Typs zur Kompilierzeit zu bestimmen:
C Frage: off_t (und andere vorzeichenbehaftete Integer-Typen) minimale und maximale Werte
Ich habe jedoch inzwischen erkannt, dass die Bestimmung des Maximalwerts eines signierten Typs (z. B. time_t oder off_t ) bei Laufzeit eine sehr schwierige Aufgabe zu sein scheint.
Einer Lösung, die mir am nächsten kommt, ist Folgendes am nächsten:
%Vor% Dies vermeidet Schleifen, solange type keine Füllbits hat, aber wenn type Füllbits hat, ruft der Cast implementationsdefiniertes Verhalten auf, das ein Signal oder eine unsinnige implementierungsdefinierte Konvertierung sein kann (z. B. stripping das Vorzeichen Bit).
Ich fange an zu denken, dass das Problem unlösbar ist, was ein wenig beunruhigend ist und meiner Meinung nach ein Defekt im C-Standard wäre. Irgendwelche Ideen, um mich falsch zu beweisen?
Update: Zum Glück war meine vorherige Antwort falsch und es scheint eine Lösung für diese Frage zu geben.
%Vor% Dieses Programm liefert entweder x , enthält den maximal möglichen Wert vom Typ T oder erzeugt ein implementierungsdefiniertes Signal.
Das Umgehen des Signalfalls ist zwar möglich, aber schwierig und rechnerisch nicht durchführbar (da für jede mögliche Signalnummer ein Signal-Handler installiert werden muss), daher glaube ich nicht, dass diese Antwort vollständig zufriedenstellend ist. Die POSIX-Signalsemantik kann genügend zusätzliche Eigenschaften liefern, um es durchführbar zu machen; Ich bin mir nicht sicher.
Der interessante Teil, insbesondere wenn Sie sich sicher fühlen, dass Sie sich nicht in einer Implementierung befinden, die ein Signal generiert, passiert, wenn (T)x zu einer implementierungsdefinierten Konvertierung führt. Der Trick der obigen Schleife besteht darin, dass sie sich überhaupt nicht auf die Wahl des Werts für die Konvertierung durch die Implementierung verlässt. Alles was darauf beruht ist, dass (T)x==x genau dann möglich ist, wenn x in den Typ T passt, da sonst der Wert von x außerhalb des Bereichs der möglichen Werte von jedem Ausdruck liegt vom Typ T .
Alte Idee, falsch, weil sie die obige Eigenschaft (T)x==x nicht berücksichtigt:
Ich denke, ich habe eine Skizze eines Beweises, wonach das, wonach ich suche, unmöglich ist:
INT_MAX>32767 . INT_MAX und INT_MIN jeweils durch 2 dividiert werden. Die wesentliche Idee dieser Gliederung ist, dass aufgrund der Tatsache, dass alles, was sich auf außerhalb des Bereichs liegende Werte mit vorzeichenbehafteten Typen bezieht, implementierungsdefiniertes oder undefiniertes Verhalten ist, eine beliebige Anzahl der hohen Wertbits eines vorzeichenbehafteten Integer-Typs kann als padding-Bits betrachtet werden, ohne Änderungen an der Implementierung vorzunehmen, ausgenommen die Limit-Makros in limits.h .
Irgendwelche Gedanken darüber, ob das korrekt oder falsch klingt? Wenn es korrekt ist, würde ich gerne das Kopfgeld an denjenigen vergeben, der es am besten machen kann, es rigoroser zu machen.
Sehen wir zuerst, wie C "Ganzzahl-Typen" definiert. Entnommen aus ISO / IEC 9899 , §6.2.6.2:
6.2.6.2 Ganzzahlige Typen
1
Für vorzeichenlose Integertypen, die nicht vorzeichenlos sind, die Bits des Objekts Repräsentation soll in zwei Gruppen unterteilt werden: Wertbits und Paddingbits (dort brauchen wir nicht einer der letzteren sein). Wenn es N-Wert-Bits gibt, soll jedes Bit einen anderen repräsentieren Stärke von 2 zwischen 1 und 2N-1, so dass Objekte dieses Typs in der Lage sein sollen Darstellen von Werten von 0 bis 2N - 1 unter Verwendung einer reinen Binärdarstellung; das soll sein bekannt als die Wertdarstellung. Die Werte von Füllbits sind nicht spezifiziert.44)
2
Für vorzeichenbehaftete Integer-Typen werden die Bits der Objektdarstellung in drei geteilt Gruppen: Wert-Bits, Füll-Bits und das Vorzeichen-Bit. Es muss keine Füllbits geben; es soll genau ein Vorzeichen geben. Jedes Bit, das ein Wertbit ist, muss den gleichen Wert wie das gleiche Bit in der Objektdarstellung des entsprechenden vorzeichenlosen Typs haben (wenn M-Wert-Bits im Typ mit Vorzeichen und N im Typ ohne Vorzeichen vorhanden sind, dann M ≤ N). Wenn das Vorzeichenbit Null ist, hat keinen Einfluss auf den resultierenden Wert. Wenn das Vorzeichenbit eins ist, soll der Wert sein auf eine der folgenden Weisen geändert:- der entsprechende Wert mit Vorzeichenbit 0 wird negiert (Vorzeichen und Betrag);
- das Vorzeichenbit hat den Wert - (2N) (Zweierkomplement);
- das Vorzeichenbit hat den Wert - (2N - 1) (Einerkomplement).
Welche davon gilt, ist implementierungsdefiniert, ebenso wie der Wert mit Vorzeichenbit 1 und alle Wertbits Null (für die ersten zwei) oder mit Vorzeichenbit und allen Wertbits 1 (für Einsen Komplement), ist eine Trap-Repräsentation oder ein normaler Wert. Im Falle von Zeichen und Wenn diese Repräsentation ein normaler Wert ist, heißt sie a negative Null.
Daraus können wir schließen:
~(int)0 kann eine Trap-Repräsentation sein, d.h. das Setzen aller Bits auf eine schlechte Idee ist int Füllbits, die keinen Einfluss auf den Wert Die gute Nachricht ist:
In diesem Sinne gibt es eine einfache Technik, um den maximalen Wert von int zu finden. Finde das Vorzeichenbit, setze es auf 0 und setze alle anderen Bits auf 1.
Wie finden wir das Vorzeichenbit? Betrachten wir int n = 1; , was streng positiv ist und garantiert nur das Ein-Bit und vielleicht einige Padding-Bits auf 1 gesetzt hat. Dann für alle anderen Bits i , wenn i==0 gilt, setze es auf 1 und sehe, ob Der resultierende Wert ist negativ. Ist dies nicht der Fall, setze es auf 0 zurück. Andernfalls haben wir das Vorzeichenbit gefunden.
Nun, da wir die Position des Vorzeichenbits kennen, nehmen wir unser int n , setzen das Vorzeichenbit auf Null und alle anderen Bits auf 1, und tadaa, wir haben den maximal möglichen int -Wert.
Das int Minimum zu bestimmen ist etwas komplizierter und wird dem Leser als Übung überlassen.
Beachten Sie, dass der C-Standard humoristisch nicht zwei verschiedene int s benötigt, um sich gleich zu verhalten. Wenn ich mich nicht irre, kann es zwei verschiedene int -Objekte geben, die z. ihre jeweiligen Zeichenbits an verschiedenen Positionen.
BEARBEITEN: Bei der Diskussion dieses Ansatzes mit R .. (siehe Kommentare unten) bin ich davon überzeugt, dass es auf mehrere Arten fehlerhaft ist und, allgemeiner gesagt, dass es da ist ist keine Lösung. Ich kann keinen Weg finden, diesen Beitrag zu korrigieren (außer das Löschen), also lasse ich ihn unverändert, damit die Kommentare unten Sinn ergeben.
Mathematisch, wenn Sie eine endliche Menge (X, der Größe n (na positive ganze Zahl) und einen Vergleichsoperator (x, y, z in X; x & lt; = y und y & lt; = z impliziert x & lt; = z) haben Es ist ein sehr einfaches Problem, den maximalen Wert zu finden. (Es existiert auch.)
Der einfachste Weg, um dieses Problem zu lösen, aber am rechenintensivsten ist, ein Array mit allen möglichen Werten zu generieren und dann das Maximum zu finden.
Teil 1. Für jeden Typ mit einer endlichen Elementmenge gibt es eine endliche Anzahl von Bits (m), die verwendet werden können, um ein bestimmtes Element dieses Typs eindeutig darzustellen. Wir machen nur ein Array, das alle möglichen Bitmuster enthält, wobei jedes gegebene Bitmuster durch einen gegebenen Wert in dem spezifischen Typ repräsentiert wird.
Teil 2. Als nächstes müssten wir jede Binärzahl in den gegebenen Typ konvertieren. Bei dieser Aufgabe kann ich aufgrund meiner Programmierunerfahrenheit nicht darüber sprechen, wie dies erreicht werden kann. Ich habe etwas über Casting gelesen, vielleicht würde das den Trick machen? Oder eine andere Konvertierungsmethode?
Teil 3. Unter der Annahme, dass der vorherige Schritt abgeschlossen wurde, haben wir jetzt eine endliche Menge von Werten im gewünschten Typ und einen Vergleichsoperator für diesen Satz. Finde die max.
Aber was wenn ...
... kennen wir nicht die genaue Anzahl der Mitglieder des gegebenen Typs? Als wir überschätzt haben. Wenn wir keine vernünftige Überschätzung erzielen können, dann sollte die Zahl physisch begrenzt sein. Sobald wir eine Überschätzung haben, prüfen wir alle möglichen Bit-Muster, um zu bestätigen, welche Bit-Muster Elemente dieses Typs darstellen. Nach dem Verwerfen von denen, die nicht verwendet werden, haben wir nun eine Menge aller möglichen Bitmuster, die ein Mitglied des gegebenen Typs repräsentieren. Dieser zuletzt erzeugte Satz ist das, was wir jetzt in Teil 1 verwenden würden.
... haben wir keinen Vergleichsoperator in diesem Typ? Dann ist das spezifische Problem nicht nur unmöglich, sondern auch logisch irrelevant. Das heißt, wenn unser Programm keinen Zugang hat, um ein sinnvolles Ergebnis zu liefern, wenn wir zwei Werte von unserem gegebenen Typ vergleichen, dann hat unser gegebener Typ keine Reihenfolge im Rahmen unseres Programms. Ohne eine Bestellung gibt es keinen Maximalwert.
... wir können eine gegebene Binärzahl nicht in einen gegebenen Typ umwandeln? Dann bricht die Methode ab. Aber ähnlich wie bei der vorherigen Ausnahme, wenn Sie Typen nicht konvertieren können, scheint unser Werkzeugsatz logisch sehr begrenzt zu sein.
Technisch gesehen müssen Sie möglicherweise nicht zwischen binären Darstellungen und einem bestimmten Typ konvertieren. Der ganze Punkt der Umwandlung ist sicherzustellen, dass die generierte Liste erschöpfend ist.
... wollen wir das Problem optimieren? Dann brauchen wir Informationen darüber, wie der gegebene Typ aus Binärzahlen abbildet. Zum Beispiel werden unsigned int, signed int (das Kompliment von 2) und signed int (das Kompliment von 1) jeweils in einer sehr dokumentierten und einfachen Weise von Bits in Zahlen abgebildet. Also, wenn wir den höchstmöglichen Wert für unsigned int wollten und wir wussten, dass wir mit m Bits arbeiteten, dann könnten wir einfach jedes Bit mit einer 1 füllen, das Bitmuster in Dezimal konvertieren und dann die Zahl ausgeben.
Dies bezieht sich auf die Optimierung, da der teuerste Teil dieser Lösung die Auflistung aller möglichen Antworten ist. Wenn wir einige Vorkenntnisse darüber haben, wie der gegebene Typ aus Bitmustern abbildet, können wir eine Teilmenge aller Möglichkeiten erzeugen, indem wir stattdessen alle möglichen Kandidaten machen.
Viel Glück.
Ich könnte hier nur dumme Sachen schreiben, da ich relativ neu in C bin, aber würde das nicht funktionieren, um das Maximum von signed zu bekommen?
Dies könnte eine dumme Art sein, es zu tun, aber soweit ich gesehen habe unsigned max Werte sind signed max * 2 + 1. Wird es nicht rückwärts arbeiten?
Entschuldigung für die Zeitverschwendung, wenn sich dies als völlig unzureichend und falsch erweist.
Sollte nicht so etwas wie der folgende Pseudocode den Job erledigen?
%Vor%Oder viel einfacher, warum sollte das Folgende nicht funktionieren?
%Vor%Für meinen eigenen Code würde ich definitiv eine Build-Time-Prüfung durchführen, die allerdings ein Präprozessor-Makro definiert.
Wenn angenommen wird, dass das Ändern von Füllbits keine Trap-Repräsentationen erzeugt, können Sie mit unsigned char * einzelne Bits überlappen und spiegeln, bis Sie das Vorzeichenbit treffen. Wenn Ihr anfänglicher Wert ~(type)0 war, sollte Ihnen dies das Maximum bringen:
Da Sie dies zur Laufzeit zulassen, könnten Sie eine Funktion schreiben, die de facto eine iterative Linksverschiebung von (type)3 ausführt. Wenn Sie aufhören, wenn der Wert unter 0 liegt, erhalten Sie nie eine Trap-Repräsentation. Und die Anzahl der Iterationen - 1 sagt dir die Position des Vorzeichenbits.
Bleibt das Problem der linken Verschiebung. Da nur die Verwendung des Operators << zu einem Überlauf führen würde, wäre dies ein undefiniertes Verhalten, so dass wir den Operator nicht direkt verwenden können.
Die einfachste Lösung ist, nicht wie oben beschrieben eine verschobene 3 zu verwenden, sondern über die Bitpositionen zu iterieren und immer auch das niedrigstwertige Bit hinzuzufügen.
(Der Startwert 7 ist die minimale Breite, die ein signierter Typ haben muss, glaube ich).
Warum wäre das ein Problem? Die Größe des Typs wird zur Kompilierzeit festgelegt, sodass das Problem der Bestimmung der Laufzeitgröße des Typs auf das Problem der Bestimmung der Kompilierzeitgröße des Typs reduziert wird. Für jede gegebene Zielplattform wird eine Deklaration wie off_t offset kompiliert, um eine bestimmte feste Größe zu verwenden, und diese Größe wird dann immer verwendet, wenn die resultierende ausführbare Datei auf der Zielplattform ausgeführt wird.
ETA: Sie können die Größe des Typs type über sizeof(type) ermitteln. Sie können dann mit gewöhnlichen Integer-Größen vergleichen und die entsprechende MAX / MIN Präprozessordefinition verwenden. Sie könnten es einfacher finden, einfach zu verwenden:
Nur weil ein Wert durch den zugrundeliegenden "physischen" Typ darstellbar ist, bedeutet dies nicht, dass der Wert für einen Wert vom "logischen" Typ gültig ist. Ich stelle mir vor, der Grund, warum die Max- und Min-Konstanten nicht angegeben sind, ist, dass es sich um "semi-opaque" Typen handelt, deren Verwendung auf bestimmte Domänen beschränkt ist. Wo weniger Deckkraft wünschenswert ist, finden Sie häufig Möglichkeiten, die gewünschten Informationen zu erhalten, wie die Konstanten, die Sie verwenden können, um herauszufinden, wie groß ein off_t ist, die von SUSv2 in seine Beschreibung von <unistd.h> .
Bevor Sie die Frage "Wie?" stellen, müssen Sie zuerst die Frage "Warum?" stellen. Warum musst du das zur Laufzeit wirklich wissen? Ist das mit dem wirklichen Problem verbunden oder ist es nur eine akademische Frage?
Ich sehe wirklich keine Notwendigkeit, das zur Kompilierzeit zu bestimmen. Wenn ein Programmierer ein Programm schreibt, um bestimmte Bedürfnisse zu erfüllen, hat er definitiv ein gewisses Wissen über die Umgebung, in der es laufen wird.