Warum ist infinity = 0x3f3f3f3f?

In einigen Situationen, man verwendet in der Regel einen ausreichend großen integer-Wert ein, der für die Unendlichkeit. Ich verwende in der Regel die größte Darstellbare positive/negative ganze Zahl ist. Das liefert meist mehr code, da Sie brauchen, um zu überprüfen, ob einer der Operanden infinity, bevor praktisch alle arithmetischen Operationen, um überläufe zu vermeiden. Manchmal wäre es wünschenswert, gesättigten integer-Arithmetik. Aus diesem Grund, einige Leute verwenden Sie kleinere Werte für unendlich, Hinzugefügt werden können oder multipliziert mehrmals ohne überlauf. Was mich fasziniert, ist die Tatsache, dass es extrem Häufig zu sehen (speziell in der Programmierung Wettbewerben):

const int INF = 0x3f3f3f3f;

Warum ist diese Zahl besonders? Es ist binäre Darstellung:

00111111001111110011111100111111

Sehe ich keine besonders interessante Eigenschaft hier. Ich sehe es leicht zu geben, aber wenn das der Grund war, die fast alles tun würde (0x3e3e3e3e, 0x2f2f2f2f, etc). Es kann Hinzugefügt werden, einmal ohne überlauf, wodurch für:

a = min(INF, b + c);

Aber auch alle anderen Konstanten tun würde, dann. Googeln zeigt nur mir eine Menge code-snippets verwenden, die Konstante, aber keine Erklärungen oder Kommentare.

Kann jeder es sehen?

  • Hast du irgendein konkretes Beispiel verwendet werden in einem generischen Kontext (und nicht in einem speziellen Algorithmus, wo es sinnvoll ist)?
  • Ich getaggt dies als C, da eine schnelle Google-Suche findet man nur C-code verwendet, der Konstante. Fühlen Sie sich frei, um neues Tag zuzuordnen.
  • Zum Beispiel, nehmen Sie einen Algorithmus, der berechnet die kürzesten Wege in einem Graphen. Der Abstand zu den nicht-erreichbar-vertices aus der starting vertex ist theoretisch unendlich. Benötigen Sie eine Möglichkeit, Sie zu vertreten (aber mit floating-point wäre ein overkill). Es könnte sein Beispiele für sehr unterschiedliche algorithmen, die diesen verwenden. Ich gab ein konkretes Beispiel, aber die Technik ist praktisch, wenn Sie schreiben würde "infinity" in pseudocode.
  • Die spezifischen Beispiele, nicht "dies könnte hypothetisch verwendet werden". Sie behaupten, dass diese sind extrem Häufig, bitte link, um einige Reale Beispiele.
  • Sorry, ich glaube, meine Behauptung war in der Tat zu stark. Dies kann gelegentlich in der "realen Welt", aber Sie sind immer noch "sehr Häufig" in der Programmierung Wettbewerbe: goo.gl/PMCUNL
InformationsquelleAutor Gabriel | 2013-08-25
  1. 25

    Fand ich einige Hinweise über diese hier (original-Inhalt in Chinesisch); die Grundidee ist, dass 0x7fffffff ist problematisch, da es bereits "oben" der Bereich von 4-byte signed ints; so, etwas hinzuzufügen, um es führt zu negativen zahlen; 0x3f3f3f3f statt:

    • ist immer noch ziemlich groß ist (gleiche Größenordnung wie 0x7fffffff);

    • hat viel headroom; wenn Sie sagen, dass der Wertebereich der ganzen zahlen ist beschränkt auf zahlen darunter, Sie können jede "gültige positive Zahl" und noch eine unendliche (D. H. etwas >=INF). Auch INF+INF nicht überläuft. Dies ermöglicht es immer "unter Kontrolle":

      a+=b;
if(a>INF)
    a=INF;

    • ist eine Wiederholung von gleichen bytes, was bedeutet, können Sie leicht memset Zeug zu INF;

    • auch, wie @Jörg W Mittag bemerkt, oben, es hat eine schöne ASCII-Darstellung, die es erlaubt sowohl, dass es vor Ort on-the-fly Suche im Speicher-dumps und schreiben es direkt in den Speicher.
    • Es ist die größte byte mit der memset und INF+INF Eigenschaften, weil 2*0x40404040 ist 0x80808080 > 0x80000000, die eine mehr als die max 32-bit-int.
    InformationsquelleAutor Matteo Italia
  2. 11

    Ich sein kann oder nicht, ist eine der frühesten Entdeckungen der 0x3f3f3f3f. Ich veröffentlichte ein Rumänischer Artikel über ihn in 2004 (http://www.infoarena.ro/12-ponturi-pentru-programatorii-cc #9), aber ich habe mit diesem Wert seit 2002 zumindest für Programmier-Wettbewerbe.

    Es gibt zwei Gründe dafür:

    • 0x3f3f3f3f + 0x3f3f3f3f nicht überläuft int32. Für einige dieser Verwendung 100000000 (eine Milliarde).
    • kann man ein array von int-Werten bis zur Unendlichkeit by doing memset(array, 0x3f, sizeof(array))
    InformationsquelleAutor Alexandru
  3. 9

    0x3f3f3f3f ist die ASCII-Darstellung der Zeichenfolge ????.

    Krugle sucht 48 Instanzen, die Konstante in Ihrer gesamten Datenbank. 46 diese Instanzen werden in einem Java-Projekt, wo es verwendet wird, als eine Bitmaske für einige Grafik-manipulation.

    - 1-Projekt ist ein Betriebssystem, wo es gebraucht wird, darstellen, ein unbekanntes ACPI Gerät.

    - 1-Projekt ist wieder eine Bitmaske für die Java-Grafiken.

    So, in allen Projekten indiziert durch Krugle, die es gewohnt ist 47-mal wegen seiner bitpattern, einmal wegen seiner ASCII-interpretation, und nicht ein einziges mal als eine Darstellung des unendlichen.

    InformationsquelleAutor Jörg W Mittag
Schreibe einen Kommentar