Perché infinity = 0x3f3f3f3f?

Question

In alcune situazioni, generalmente si utilizza un valore intero abbastanza grande per rappresentare l'infinito. Di solito uso il numero intero positivo/negativo rappresentabile più grande. Questo di solito produce più codice, dal momento che è necessario verificare se uno degli operandi è infinito prima di praticamente tutte le operazioni aritmetiche per evitare overflow. A volte sarebbe desiderabile avere un aritmetico intero saturo. Per questo motivo, alcune persone usano valori più piccoli per l'infinito, che possono essere aggiunti o moltiplicati più volte senza eccessi. Quello che mi incuriosisce è il fatto che è estremamente comune vedere (specialmente nelle competizioni di programmazione):

const int INF = 0x3f3f3f3f; 

Perché quel numero speciale? La sua rappresentazione binaria è:

00111111001111110011111100111111 

Non vedo alcuna proprietà particolarmente interessante qui. Vedo che è facile da digitare, ma se questo fosse il motivo, quasi qualsiasi cosa avrebbe fatto (0x3e3e3e3e, 0x2f2f2f2f, ecc.). Può essere aggiunto una volta senza troppo pieno, che permette di:

a = min(INF, b + c); 

Ma tutte le altre costanti avrebbero fatto, allora. Googling mi mostra solo un sacco di frammenti di codice che usano quella costante, ma senza spiegazioni o commenti.

Qualcuno può individuarlo?

Answer 1

Ho trovato alcune prove su questo here (original content in cinese); l'idea di base è che 0x7fffffff è problematico dal momento che è già "la parte superiore" dell'intervallo di indici firmati a 4 byte; quindi, aggiungendo qualcosa ad esso si ottengono numeri negativi; 0x3f3f3f3f, invece:

• è ancora abbastanza grande (stesso ordine di grandezza di 0x7fffffff);

• ha un sacco di margine; se si dice che l'intervallo valido di numeri interi è limitato ai numeri sotto di esso, è possibile aggiungere qualsiasi "numero positivo valido" ad esso e ottenere comunque un numero infinito (ad esempio, >=INF). Anche INF+INF non ha overflow. Questo permette di mantenere sempre "sotto controllo":

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

• è una ripetizione delle pari byte, il che significa che si può facilmente memset roba da INF;

• inoltre, come notato da @ Jörg W Mittag sopra, ha una bella rappresentazione ASCII, che consente sia di individuarlo al volo guardando i dump della memoria, sia di scriverlo direttamente in memoria.

Answer 2

0x3f3f3f3f è la rappresentazione ASCII della stringa ????.

Krugle trova 48 istanze di tale costante nel suo intero database. 46 di queste istanze sono in un progetto Java, dove viene utilizzato come maschera di bit per alcune manipolazioni grafiche.

1 progetto è un sistema operativo, in cui viene utilizzato per rappresentare un dispositivo ACPI sconosciuto.

1 progetto è di nuovo una maschera di bit per la grafica Java.

Quindi, in tutti i progetti indicizzati da Krugle, viene utilizzato 47 volte a causa del suo bitpattern, una volta a causa della sua interpretazione ASCII, e non una sola volta come rappresentazione dell'infinito.

Answer 3

Posso essere o non essere uno dei primi scopritori di 0x3f3f3f3f. Ho pubblicato un articolo rumeno su di esso nel 2004 (http://www.infoarena.ro/12-ponturi-pentru-programatorii-cc # 9), ma ho usato questo valore dal 2002 almeno per la programmazione delle competizioni.

ci sono due ragioni per questo:

• 0x3f3f3f3f + 0x3f3f3f3f non trabocchi int32. Per questo alcuni usano 100000000 (un miliardo).
• si può impostare un array di int all'infinito facendo memset(array, 0x3f, sizeof(array))