Comprimere due o più numeri in un byte

Penso che questo non è davvero possibile, ma vale la pena chiedere comunque. Dire che ho due piccoli numeri (Ogni varia da 0 a 11). C’è un modo che posso comprimere in un byte e farli tornare più tardi. Come circa con quattro numeri di dimensioni simili.

Quello che mi serve è qualcosa di simile a: a1 + a2 = x. So solo che x e da che ottenere a1, a2

Per la seconda parte: a1 + a2 + a3 + a4 = x. So solo che x e da che ottenere a1, a2, a3, a4

Nota: so che non è possibile unadd, a illustrare la mia domanda.

x deve essere un byte. a1, a2, a3, a4 intervallo [0, 11].

  • 11 1011 in binario, in modo che richiede solo 4 bit. Quindi sì, dovrebbe essere possibile. Si hanno per spostare a sinistra per quattro volte, poi aggiungete. Dopo di che, per recuperare i loro primi quattro bit e gli ultimi quattro bit.
  • Questo puzza un po ‘ come compiti a casa per me.
  • No, le assicuro che è la mia ricerca, la Scuola non inizia fino a settembre 😉
  • no, suona più come la compressione dei dati. Mi è venuto anche questo problema di compressione dei dati, e risolto, vedi il mio post.
InformationsquelleAutor Dave | 2010-08-17



11 Replies
  1. 12

    Thats banale con le maschere di bit. L’Idea è quella di dividere il byte in unità più piccole e dedicarsi a diversi elementi.

    Per 2 numeri, non può essere come questo: primi 4 bit sono numero1, il resto sono numero2. Utilizzare number1 = (x & 0b11110000) >> 4, number2 = (x & 0b00001111) per recuperare i valori, e x = (number1 << 4) | number2 per comprimerli.

    • per coloro che sono nuovi per lo spostamento di bit: questo funziona solo per i numeri che possono essere rappresentati con 4 bit (2 ^ 4) = numeri da 0 a 15. Il motivo è perché ciò che si sta facendo qui è la memorizzazione di un valore (a 4 bit) e poi trasferirli su 4 posti e memorizzare il numero successivo in quel punto. Dal momento che un byte è di solo 8 bit, avete solo in camera per due a 4 bit di numeri, limitando in tal modo questo approccio per piccoli numeri.
  2. 9

    Per due numeri, certo. Ognuno ha 12 valori possibili, in modo che la coppia ha un totale di 12^2 = 144 valori possibili, e che, a meno di 256 valori possibili di un byte. Così si potrebbe fare ad esempio

    x = 12*a1 + a2
    a1 = x /12
    a2 = x % 12
    

    (Se hai solo firmato byte, ad esempio, in Java, è un po ‘ più complicato)

    Per quattro numeri da 0 a 11, ci sono 12^4 = 20736 valori, e quindi non adatti a loro in un byte, ma si potrebbe fare con due.

    x = 12^3*a1 + 12^2*a2 + 12*a3 + a4
    a1 = x /12^3
    a2 = (x /12^2) % 12
    a3 = (x /12) % 12
    a4 = x % 12
    

    EDIT: le altre risposte parlare di memorizzazione di un numero massimo di quattro bit e l’utilizzo di spostamento di bit. Che è più veloce.

    • La cambiata è più veloce in questo caso specifico, ma apprezzo il semplice entropia di calcolo qui perché è più generico 🙂 vale la pena notare che il cambio non è un’ottimizzazione che viene applicato solo una volta stabilito che ci potrebbe essere una soluzione.
  3. 2

    Il 0-11 esempio è abbastanza facile, è possibile memorizzare ogni numero quattro bit, in modo da mettere in un singolo byte è solo una questione di spostare 4 bit a sinistra, e oring i due insieme.

    Quattro numeri di simili dimensioni non è adatta — quattro bit a testa per quattro dà un minimo di 16 bit per tenerli.

    • nitpick – 16 bit non è il minimo di bit necessari per tenere i 4 numeri di 0-11 si può usare meno bit a scapito di non essere in grado di codificare/decodificare il più rapidamente
    • beh, sì, si potrebbe ottenere con meno di 16, ma ci vuole ancora più di 8.
  4. 1

    Se i numeri 0-11 non sono uniformemente distribuiti si può fare ancora meglio con l’utilizzo di brevi sequenze di bit per i valori comuni e di quelli lunghi, per valori più rari. Costa almeno un po ‘ di codice di lunghezza si utilizza quindi c’è un intero ramo di CS dedicato a dimostrare che quando vale la pena di fare.

  5. 1

    Diciamo che, in generale, si supponga di voler mix di N numeri a1, a2, … aN, a1 che vanno da 0..k1-1, a2 da 0..k2-1, … e un da 0 .. kN-1.

    Quindi, codificato numero è:

    encoded = a1 + k1*a2 + k1*k2*a3 + ... k1*k2*..*k(N-1)*aN
    

    La decodifica è quindi più difficile, graduale:

    rest = encoded
    a1 = rest mod k1
    rest = rest div k1
    
    a2 = rest mod k2
    rest = rest div k2
    
    ...
    
    a(N-1) = rest mod k(N-1)
    rest = rest div k(N-1)
    
    aN = rest # rest is already < kN
    
  6. 0

    Quindi un byte può contenere fino a 256 valori o FF in Esadecimale. Così è possibile codificare due numeri da 0-16 in un byte.

    byte a1 = 0xf;
    byte a2 = 0x9;
    byte compress = a1 << 4 | (0x0F & a2);  //should yield 0xf9 in one byte.
    

    4 Numeri si può fare se si riduce a un solo 0-8 gamma.

    • “4 Numeri si può fare se si riduce a un solo 0-8 gamma.” Ummmmm…. forse 0-3 gamma? 2 bit per il numero…i numeri 4, 8 bit.
  7. 0

    Dal momento che un singolo byte a 8 bit, si può facilmente suddividere, con piccoli intervalli di valori. Il limite estremo di questo è quando si hanno 8 singolo bit interi, che è chiamato un campo di bit.

    Se si desidera memorizzare due a 4 bit interi (che ti dà 0-15 per ciascuno), basta fare questo:

    value = a * 16 + b;
    

    Come lungo come si fa una corretta verifica dei limiti, non si sarà mai perdere qualsiasi informazione qui.

    Per ottenere i due valori, è solo fare questo:

    a = floor(value /16)
    b = value MOD 15
    

    MOD è il modulo, è il “resto” di una divisione.

    Se si desidera memorizzare quattro 2-bit interi (0-3), si può fare questo:

    value = a * 64 + b * 16 + c * 4 + d
    

    E, per farli tornare:

    a = floor(value /64)
    b = floor(value /16) MOD 4
    c = floor(value /4) MOD 4
    d = value MOD 4
    

    Lascio l’ultima divisione come esercizio per il lettore 😉

  8. 0

    @Mike Caron

    tuo ultimo esempio (4 numeri interi tra 0 e 3) è molto più veloce con spostamento di bit. Nessun bisogno di pavimento().

    value = (a << 6) | (b << 4) | (c << 2) | d;
    
    a = (value >> 6);
    b = (value >> 4) % 4;
    c = (value >> 2) % 4;
    d = (value) % 4;
    
  9. 0

    Utilizzare il Bit di maschera o di Spostamento di Bit. Il secondo è più veloce

    Testare BinaryTrees per un certo divertimento. (sarà la consegna più tardi nel dev vita in materia di dati e di tutti i tipi di dev voodom lol)

  10. 0

    Imballaggio quattro valori in un numero richiederà almeno 15 bit. Questo non si adatta in un singolo byte, ma in due.

    Quello che dovete fare è una conversione da base 12 a base di 65536 e viceversa.

    B = A1 + 12.(A2 + 12.(A3 + 12.A4))
    
    A1 = B % 12
    A2 = (B /12) % 12
    A3 = (B /144) % 12
    A4 = B /1728
    

    Come questo richiede di 2 byte, comunque, di conversione da base 12 (imballato) base 16 è prefable.

    B1 = A1 + 256.A2
    B2 = A3 + 256.A4
    
    A1 = B1 % 256
    A2 = B1 /256
    A3 = B2 % 256
    A4 = B2 /256
    

    Il modulos e divisioni sono implementati bymaskings e turni.

  11. 0

    0-9 opere molto più facile. Si può facilmente memorizzare 11random ordine decimali in 4 1/2 byte. Che è più stretto di compressione di registro(256) ś log(10). Appena creativo di mappatura. Ricordate che non tutti la compressione ha a che fare con, dizionari, licenziamenti, o sequenze.

    Se stai parlando di numeri casuali da 0 a 9 si possono avere 4 cifre a 14 bit non 15.

Lascia un commento