Comprima dos o más números en un byte

Question

Creo que esto no es realmente posible, pero vale la pena preguntarlo de todos modos. Digamos que tengo dos números pequeños (cada uno varía de 0 a 11). ¿Hay una manera que puedo comprimirlos en un byte y recuperarlos más tarde. ¿Qué tal con cuatro números de tamaños similares.

Lo que necesito es algo así como: a1 + a2 = x. Solo sé xy a partir de eso obtengo a1, a2
Para la segunda parte: a1 + a2 + a3 + a4 = x. Solo sé xy a partir de eso obtengo a1, a2, a3, a4
Nota: Sé que no puede retirarse, simplemente ilustrando mi pregunta.

x debe ser de un byte. a1, a2, a3, a4 rango [0, 11].

Answer 1

Eso es trivial con máscaras de bits. La idea es dividir el byte en unidades más pequeñas y dedicarlas a diferentes elementos.

Para 2 números, puede ser así: los primeros 4 bits son el número 1, el resto es el número 2. Utilizaría number1 = (x & 0b11110000) >> 4, number2 = (x & 0b00001111) para recuperar valores, y x = (number1 << 4) | number2 para comprimirlos.

Answer 2

El ejemplo 0-11 es bastante fácil: puede almacenar cada número en cuatro bits, por lo que ponerlos en un solo byte es simplemente cuestión de desplazar uno 4 bits hacia la izquierda y or juntar los dos.

No caben cuatro números de tamaños similares: cuatro bits cada cuatro veces da un mínimo de 16 bits para mantenerlos.

Answer 3

De modo que un byte puede contener hasta 256 valores o FF en hexadecimal. Entonces puedes codificar dos números del 0-16 en un byte.

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

4 Los números se pueden hacer si se reduce a solo 0-8 rango.

Answer 4

Para dos números, claro. Cada uno tiene 12 valores posibles, por lo que el par tiene un total de 12^2 = 144 valores posibles, y eso es menos que los 256 valores posibles de un byte. Entonces podrías hacer, por ejemplo

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

(Si sólo ha firmado bytes, por ejemplo, en Java, que es un poco más difícil)

Durante cuatro números del 0 al 11, hay 12^4 = 20736 valores, por lo que no pudo colóquelos en un byte, pero podría hacerlo con dos.

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: las otras respuestas hablan de almacenar un número por cuatro bits y el uso de bits de desplazamiento. Eso es más rápido.

Answer 5

Dado que un solo byte es de 8 bits, puede subdividirlo fácilmente, con rangos de valores más pequeños. El límite extremo de esto es cuando tienes 8 enteros de un solo bit, que se llama campo de bit.

Si desea almacenar dos enteros de 4 bits (que le da 0-15 para cada uno), simplemente tiene que hacer esto:

value = a * 16 + b; 

Mientras lo hace la comprobación de los límites apropiados, se quiere nunca pierdas ninguna información aquí.

Para obtener los dos valores de nuevo, sólo hay que hacer esto:

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

MOD es el módulo, que es el "resto" de una división.

Si desea almacenar cuatro números enteros de 2 bits (0-3), se puede hacer esto:

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

Y, para recuperarlos:

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

dejo la última división como un ejercicio para el lector;)

Answer 6

Si los números 0-11 no están distribuidos uniformemente, puede hacerlo aún mejor utilizando secuencias de bits más cortas para valores comunes y más largas para valores más raros. Cuesta al menos un bit codificar qué longitud está utilizando, por lo que hay una rama completa de CS dedicada a probar cuándo vale la pena hacerlo.

Answer 7

Digamos que en general: supongamos que quiere mezclar N números a1, a2, ... aN, a1 que van desde 0..k1-1, a2 desde 0..k2-1, ... y aN de 0 .. kN-1.

Entonces, el número codificado es:

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

La decodificación es entonces más difícil, por etapas:

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 

Answer 8

@ Mike Caron

su último ejemplo (4 números enteros entre 0- 3) es mucho más rápido con el cambio de bit. Sin necesidad de piso().

value = (a << 6) | (b << 4) | (c << 2) | d; 

a = (value >> 6); 
b = (value >> 4) % 4; 
c = (value >> 2) % 4; 
d = (value) % 4; 

Answer 9

Utilice el enmascaramiento de bits o el cambio de bit. El último es más rápido

Pruebe los BinaryTrees para divertirse. (se entregará más adelante en dev life con respecto a los datos y todo tipo de dev voodom lol)

Answer 10

El embalaje de cuatro valores en un número requerirá al menos 15 bits. Esto no cabe en un solo byte, sino en dos.

Lo que debe hacer es una conversión de la base 12 a la base 65536 y viceversa.

B = A1 + 12.(A2 + 12.(A3 + 12.A4)) 

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

---

Como esto tiene 2 bytes de todos modos, la conversión de la base 12 a la base 16 (embalado) es, de lejos prefable.

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

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

Los módulos y las divisiones se implementan mediante mascaras y turnos.

Answer 11

0-9 funciona mucho más fácil. Puede almacenar fácilmente 11 decimales de orden aleatorio en 4 1/2 bytes. Que es una compresión más ajustada que log (256) ÷ log (10). Solo por mapeo creativo. Recuerde que no toda la compresión tiene que ver con diccionarios, redundancias o secuencias.

Si habla de números aleatorios del 0 al 9, puede tener 4 dígitos por 14 bits, no 15.