Un buon schema per rappresentare numeri interi da 0 a infinito, assumendo che tu abbia una memoria binaria lineare infinita?

Un approccio che ho usato: conta il numero di 1 bit iniziali, diciamo n . La dimensione del numero è quindi 2 ^ n byte (inclusi i primi 1 bit). Prendi i bit dopo il primo 0 bit come numero intero e aggiungi il valore massimo (più uno) che può essere rappresentato da un numero utilizzando questa codifica in 2 ^ (n-1) byte.

Quindi

                  0 = 0b00000000
                   ...
                127 = 0b01111111
                128 = 0b1000000000000000
                   ...
              16511 = 0b1011111111111111
              16512 = 0b11000000000000000000000000000000
                   ...
          536887423 = 0b11011111111111111111111111111111
          536887424 = 0b1110000000000000000000000000000000000000000000000000000000000000
                   ...
1152921505143734399 = 0b1110111111111111111111111111111111111111111111111111111111111111
1152921505143734400 = 0b111100000000000000000000000000000000000000000000 ...

Questo schema consente di rappresentare qualsiasi valore non negativo esattamente in un modo.

(Equivalentemente, usato il numero di 0 bit iniziali.)

C'è un sacco di teoria basata su ciò che stai cercando di fare. Dai un'occhiata alla pagina wiki sui codici universali - c'è un elenco piuttosto esaustivo dei metodi di codifica integer (alcuni dei che vengono effettivamente utilizzati nella pratica).

In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords

Oppure potresti usare solo i primi 8 byte per memorizzare la lunghezza del numero in alcune unità (molto probabilmente byte) e quindi inserire i byte dei dati. Sarebbe molto facile da implementare, ma piuttosto inefficiente per i piccoli numeri. E saresti in grado di codificare un numero intero abbastanza lungo da riempire tutte le unità di dati disponibili per l'umanità:)

Che ne dici di lasciare che il numero di iniziali 1 più il primo 0 sia la dimensione (sizeSize) della dimensione del numero (numSize) in bit. NumSize è un numero binario che fornisce la dimensione della rappresentazione numerica in byte compresi i bit di dimensione. I bit rimanenti sono il numero (num) in binario. Per uno schema intero positivo, ecco alcuni esempi di numeri esemplificativi:

Number              sizeSize  numSize    num
63:                 0 (1)     1 (1)      111111
1048575:            10 (2)    11 (3)     1111 11111111 11111111
1125899906842623:   110 (3)   111 (7)    11 11111111 11111111 11111111 11111111 11111111 11111111
5.19.. e+33:        1110 (4)  1111 (15)  11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111

Che ne dici di questo: Un byte per la lunghezza, quindi n byte per il numero (prima il byte meno significativo). Ripeti la lunghezza + il numero fino a quando la lunghezza precedente era 255.

Ciò consente numeri arbitrariamente grandi, ma è ancora facile da gestire e non spreca troppa memoria.

Perché non utilizzare solo 7 bit su ciascun byte e utilizzare l'8 ° bit per indicare se c'è un altro byte da seguire? Quindi 1-127 sarebbe in un byte, 128 sarebbe rappresentato da 0x80 0x01, ecc.

I sistemi UUID sono basati su una potenza di calcolo finita (ma grande) in un universo finito (ma grande). Il numero di UUID è grande anche se confrontato con cose assurdamente grandi come il numero di particelle nell'universo. Il numero di UUID, con qualsiasi numero di bit fissi, è piccolo, tuttavia, rispetto all'infinito.

Il problema con l'utilizzo di 0xFFFF per rappresentare il flag di fine del numero è che rende la codifica del numero meno efficiente quando i numeri sono grandi. Tuttavia, sembra che il tuo schema UUID renda questo problema ancora peggiore. Invece di saltare uno su 256 byte, ora si perde l'intero spazio UUID. L'efficienza del calcolo / riconoscimento (invece dello spazio) dipende molto dal tuo computer teorico (che, presumo tu abbia, se parli dell'infinito). Per una TM con un nastro e un controllore di stato finito, qualsiasi schema UUID è impossibile da scalare in modo efficiente (in pratica, il lemma di pompaggio ti impedisce di spostarti efficientemente oltre un marcatore finale a lunghezza di bit fissa). Se non si presuppone un controller a stato finito, questo potrebbe non essere applicabile, ma è necessario pensare a dove vanno i bit nel processo di decodifica / riconoscimento.

Se vuoi solo una migliore efficienza di 1 su 256 byte, puoi usare qualunque bit-length di 1 che avresti usato per il tuo schema UUID. Questo è 1 su 2 ^ lunghezza in bit di inefficienza.

Si noti tuttavia che esistono altri schemi di codifica. La codifica dei byte con delimitatori è la più semplice da implementare.

Suggerirei di avere una matrice di byte (o interi o lunghi) e un campo di lunghezza che indichi per quanto tempo è il numero.

Questo è approssimativamente l'approccio utilizzato da Java BigInteger . Lo spazio di indirizzi possibile da questo è enorme - abbastanza facilmente da fornire un UUID diverso a ogni singolo atomo dell'universo: -)

A meno che tu non abbia una buona ragione per fare diversamente, ti suggerirei di usare direttamente BigInteger (o il suo equivalente in altre lingue). Non è necessario reinventare la grande ruota dei numeri ....

Prima di tutto, grazie a tutti coloro che hanno fornito risposte eccellenti alla mia domanda relativamente vaga e astratta.

Mi piacerebbe contribuire con una potenziale risposta a cui ho pensato dopo aver pensato ad altre risposte. Non è una risposta diretta alla domanda, ma è rilevante.

Come alcune persone hanno sottolineato, l'utilizzo di un numero intero di 64/128/256 bit offre già uno spazio molto grande per gli UUID. Ovviamente non è infinito, ma ...

Forse potrebbe essere una buona idea usare solo una dimensione fissa int (per esempio, 64-bit per iniziare) finché 64 bit non sono sufficienti (o vicini ad essa). Quindi, supponendo che tu abbia un tale accesso a tutte le precedenti istanze degli UUID, basta aggiornarli tutti a 128 bit e prendere quello per essere la dimensione fissa del numero intero.

Se il sistema consente tali pause / interruzioni del servizio e poiché tali operazioni di "ricostruzione" dovrebbero verificarsi abbastanza raramente, forse i vantaggi (un sistema molto semplice, veloce, facile da implementare) supereranno gli svantaggi (dover ricostruire tutto numeri interi assegnati in precedenza a una nuova dimensione del bit intero).