traduccion rotacion operadores derecha corrimiento bitwise java bitwise-operators packing bit-packing

java - rotacion - Uso de los operadores bitwise para empaquetar múltiples valores en un int.



operadores de bits javascript (7)

La manipulación de bits de bajo nivel nunca ha sido mi punto fuerte. Apreciaré alguna ayuda para comprender el siguiente caso de uso de operadores bitwise. Considere ...

int age, gender, height, packed_info; . . . // Assign values // Pack as AAAAAAA G HHHHHHH using shifts and "or" packed_info = (age << 8) | (gender << 7) | height; // Unpack with shifts and masking using "and" height = packed_info & 0x7F; // This constant is binary ...01111111 gender = (packed_info >> 7) & 1; age = (packed_info >> 8);

No estoy seguro de lo que este código está logrando y cómo? ¿Por qué usar el número mágico 0x7F? ¿Cómo se realiza el embalaje y el desembalaje?

Source

Como dice el comentario, vamos a agrupar la edad, el género y la altura en 15 bits, del formato:

AAAAAAAGHHHHHHH

Vamos a empezar con esta parte:

(age << 8)

Para empezar, la edad tiene este formato:

age = 00000000AAAAAAA

donde cada A puede ser 0 o 1.

<< 8 mueve los bits 8 lugares a la izquierda y llena los espacios con ceros. Así que tienes:

(age << 8) = AAAAAAA00000000

Similar:

gender = 00000000000000G (gender << 7) = 0000000G0000000 height = 00000000HHHHHHH

Ahora queremos combinarlos en una sola variable. El | el operador trabaja observando cada bit y devolviendo 1 si el bit es 1 en cualquiera de las entradas. Asi que:

0011 | 0101 = 0111

Si un bit es 0 en una entrada, obtienes el bit de la otra entrada. Mirando a (age << 8) , (gender << 7) y height , verás que, si un bit es 1 para uno de estos, es 0 para los otros. Asi que:

packed_info = (age << 8) | (gender << 7) | height = AAAAAAAGHHHHHHH

Ahora queremos desempacar los bits. Empecemos por la altura. Queremos obtener los últimos 7 bits, e ignorar los primeros 8. Para hacer esto, usamos el operador & , que devuelve 1 solo si los dos bits de entrada son 1. Entonces:

0011 & 0101 = 0001

Asi que:

packed_info = AAAAAAAGHHHHHHH 0x7F = 000000001111111 (packed_info & 0x7F) = 00000000HHHHHHH = height

Para tener la edad, podemos empujar todo 8 lugares a la derecha, y nos queda 0000000AAAAAAAA . Así que age = (packed_info >> 8) .

Finalmente, para obtener el género, empujamos 7 lugares a la derecha para deshacernos de la altura. Entonces solo nos importa el último bit:

packed_info = AAAAAAAGHHHHHHH (packed_info >> 7) = 0000000AAAAAAAG 1 = 000000000000001 (packed_info >> 7) & 1 = 00000000000000G

El mismo requisito que he enfrentado muchas veces. Es muy fácil con la ayuda del operador Bitwise Y. Solo califica tus valores con poderes crecientes de dos (2). Para almacenar varios valores, AGREGUE su número relativo (potencia de 2) y obtenga el SUM. Esta SUMA consolidará sus valores seleccionados. CÓMO ?

Simplemente haga Bitwise AND con cada valor y dará cero (0) para los valores que no se seleccionaron y no cero para los que se seleccionaron.

Aquí está la explicación:

1) Valores (SI, NO, MAYOR)

2) Asignación a potencia de dos (2)

YES = 2^0 = 1 = 00000001 NO = 2^1 = 2 = 00000010 MAYBE = 2^2 = 4 = 00000100

3) Elijo SÍ y MAYO por lo tanto SUMA:

SUM = 1 + 4 = 5 SUM = 00000001 + 00000100 = 00000101

Este valor almacenará tanto SI como MAYOR. ¿CÓMO?

1 & 5 = 1 ( non zero ) 2 & 5 = 0 ( zero ) 4 & 5 = 4 ( non zero )

Por lo tanto SUM consiste en

1 = 2^0 = YES 4 = 2^2 = MAYBE.

Para una explicación más detallada y la implementación visite mi blog

El operador de cambio a la izquierda significa "multiplica por dos, esto muchas veces". En binario, multiplicar un número por dos es lo mismo que sumar un cero al lado derecho.

El operador de cambio a la derecha es el reverso del operador de cambio a la izquierda.

El operador de la tubería es "o", lo que significa que se superponen dos números binarios uno encima del otro, y donde hay un 1 en cualquiera de los números, el resultado en esa columna es un 1.

Entonces, extraigamos la operación para packed_info:

// Create age, shifted left 8 times: // AAAAAAA00000000 age_shifted = age << 8; // Create gender, shifted left 7 times: // 0000000G0000000 gender_shifted = gender << 7; // "Or" them all together: // AAAAAAA00000000 // 0000000G0000000 // 00000000HHHHHHH // --------------- // AAAAAAAGHHHHHHH packed_info = age_shifted | gender_shifted | height;

Y el desembalaje es lo contrario.

// Grab the lowest 7 bits: // AAAAAAAGHHHHHHH & // 000000001111111 = // 00000000HHHHHHH height = packed_info & 0x7F; // right shift the ''height'' bits into the bit bucket, and grab the lowest 1 bit: // AAAAAAAGHHHHHHH // >> 7 // 0000000AAAAAAAG & // 000000000000001 = // 00000000000000G gender = (packed_info >> 7) & 1; // right shift the ''height'' and ''gender'' bits into the bit bucket, and grab the result: // AAAAAAAGHHHHHHH // >> 8 // 00000000AAAAAAA age = (packed_info >> 8);

Esta podría ser una lección bastante larga sobre manipulación de bits, pero primero permítame señalarle también el artículo de enmascaramiento de bits en Wikipedia .

packed_info = (age << 8) | (gender << 7) | height;

Tome la edad y mueva su valor más de 8 bits, luego tome el género y muévalo más de 7 bits y la altura ocupará los últimos bits.

age = 0b101 gender = 0b1 height = 0b1100 packed_info = 0b10100000000 | 0b00010000000 | 0b00000001100 /* which is */ packed_info = 0b10110001100

Desembalar hace lo contrario pero usa máscaras como 0x7F (que es 0b 01111111) para recortar los otros valores en el campo.

gender = (packed_info >> 7) & 1;

Funcionaría como ...

gender = 0b1011 /* shifted 7 here but still has age on the other side */ & 0b0001 /* which is */ gender = 0b1

Tenga en cuenta que ANDing algo a 1 es lo mismo que "mantener" ese bit y ANDing con 0 es lo mismo que "ignorar" ese bit.

Puede ver la expresión x & mask como una operación que elimina de x los bits que no están presentes (es decir, tienen el valor 0) en la mask . Eso significa que packed_info & 0x7F eliminan de packed_info todos los bits que están por encima del séptimo bit.

Ejemplo: si packed_info es 1110010100101010 en binario, packed_info & 0x7f serán

1110010100101010 0000000001111111 ---------------- 0000000000101010

Entonces, en height obtenemos los 7 bits más packed_info de packed_info .

A continuación, estamos cambiando la información packed_info completa por 7, de esta manera eliminamos la información que ya hemos leído. Entonces obtenemos (para el valor del ejemplo anterior) 111001010 El género se almacena en el siguiente bit, así que con el mismo truco: & 1 estamos extrayendo solo ese bit de la información. El resto de la información está contenida en el offset 8.

La devolución no es complicada, también: se age , se desplaza 8 bits (para obtener 1110010100000000 desde 11100101 ), se cambia el gender en 7 (se obtiene 00000000 ) y se toma la altura (suponiendo que cabría en 7 bits más bajos) . Entonces, los estás componiendo todos juntos:

1110010100000000 0000000000000000 0000000000101010 ---------------- 1110010100101010

Si fuera a guardar una fecha como un número, tal vez lo lograría multiplicando el año por 10000, el mes por 100 y sumando el día. Una fecha como el 2 de julio de 2011 se codificaría como el número 20110702:

year * 10000 + month * 100 + day -> yyyymmdd 2011 * 10000 + 7 * 100 + 2 -> 20110702

Podemos decir que codificamos la fecha en una máscara aaaammdd . Podríamos describir esta operación como

  • Desplazar las posiciones del año 4 a la izquierda,
  • Desplazar las posiciones del mes 2 a la izquierda y
  • dejar el día como está.
  • Luego combina los tres valores juntos.

Esto es lo mismo que ocurre con la codificación de edad, género y altura, solo que el autor está pensando en binario.

Vea los rangos que esos valores pueden tener:

age: 0 to 127 years gender: M or F height: 0 to 127 inches

Si traducimos esos valores a binarios, tendríamos esto:

age: 0 to 1111111b (7 binary digits, or bits) gender: 0 or 1 (1 bit) height: 0 to 1111111b (7 bits also)

Con esto en mente, podemos codificar los datos de edad-género-altura con la máscara aaaaaaaghhhhhhh , solo que aquí estamos hablando de dígitos binarios , no de dígitos decimales .

Asi que,

  • Desplazar los bits de edad 8 a la izquierda,
  • desplaza el género 7 bits hacia la izquierda y
  • Deja la altura como está.
  • Luego combina los tres valores juntos.

En binario, el operador Shift-Left (<<) mueve un valor n posiciones hacia la izquierda. El operador "O" ("|" en muchos idiomas) combina valores. Por lo tanto:

(age << 8) | (gender << 7) | height

Ahora, ¿cómo "decodificar" esos valores?

Es más fácil en binario que en decimal:

  • Usted "enmascara" la altura,
  • desplaza el género 7 bits hacia la derecha y enmascara eso también, y finalmente
  • Cambia los bits de edad 8 a la derecha.

El operador Shift-Right (>>) mueve las posiciones de un valor n a la derecha (se pierden los dígitos desplazados "fuera" de la posición más a la derecha). El operador binario "Y" ("&" en muchos idiomas) enmascara bits. Para hacer eso, necesita una máscara, que indica qué bits conservar y qué bits destruir (se conservan 1 bits). Por lo tanto:

height = value & 1111111b (preserve the 7 rightmost bits) gender = (value >> 1) & 1 (preserve just one bit) age = (value >> 8)

Dado que 1111111b en hexadecimal es 0x7f en la mayoría de los idiomas, esa es la razón de ese número mágico. Tendría el mismo efecto utilizando 127 (que es 1111111b en decimal).

Una respuesta más condensada:

AAAAAAA G HHHHHHHH

Embalaje:

packed = age << 8 | gender << 7 | height

Alternativamente, puede simplemente sumar componentes si, por ejemplo, cuando se usa en la función agregada de MySQL SUM

packed = age << 8 + gender << 7 + height

Desembalaje:

age = packed >> 8 // no mask required gender = packed >> 7 & ((1 << 1) - 1) // applying mask (for gender it is just 1) height = packed & ((1 << 7) - 1) // applying mask


Otro ejemplo (más largo):

Digamos que tienes una dirección IP que quieres empacar, sin embargo, es una dirección IP ficticia, por ejemplo, 132.513.151.319. Tenga en cuenta que algunos componentes superiores a 256, que requieren más de 8 bits, a diferencia de las direcciones IP reales.

Primero debemos averiguar qué compensación necesitamos usar para poder almacenar el número máximo. Digamos que con nuestros IP ficticios, ningún componente puede ser más grande que 999, lo que significa que necesitamos 10 bits de almacenamiento por componente (permite números de hasta 1014).

packed = (comp1 << 0 * 10) | (comp1 << 1 * 10) | (comp1 << 2 * 10) | (comp1 << 3 * 10)

Lo que da dec 342682502276 o bin 100111111001001011110000000010010000100

Ahora vamos a descomprimir el valor.

comp1 = (packed >> 0 * 10) & ((1 << 10) - 1) // 132 comp2 = (packed >> 1 * 10) & ((1 << 10) - 1) // 513 comp3 = (packed >> 2 * 10) & ((1 << 10) - 1) // 151 comp4 = (packed >> 3 * 10) & ((1 << 10) - 1) // 319

Donde (1 << 10) - 1 es una máscara binaria que usamos para ocultar bits a la izquierda más allá de los 10 bits más a la derecha que nos interesan.

Mismo ejemplo usando la consulta de MySQL

SELECT (@offset := 10) AS `No of bits required for each component`, (@packed := (132 << 0 * @offset) | (513 << 1 * @offset) | (151 << 2 * @offset) | (319 << 3 * @offset)) AS `Packed value (132.513.151.319)`, BIN(@packed) AS `Packed value (bin)`, (@packed >> 0 * @offset) & ((1 << @offset) - 1) `Component 1`, (@packed >> 1 * @offset) & ((1 << @offset) - 1) `Component 2`, (@packed >> 2 * @offset) & ((1 << @offset) - 1) `Component 3`, (@packed >> 3 * @offset) & ((1 << @offset) - 1) `Component 4`;