operators - operacion - ¿Qué son los operadores de cambio de bit(cambio de bit) y cómo funcionan?

operadores de bits java (8)

Enmascaramiento y desplazamiento de bits

El desplazamiento de bits se utiliza a menudo en la programación de gráficos de bajo nivel. Por ejemplo, un valor de color de píxel dado codificado en una palabra de 32 bits.

Pixel-Color Value in Hex: B9B9B900 Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000

Para una mejor comprensión, el mismo valor binario etiquetado con qué secciones representa qué parte del color.

Red Green Blue Alpha Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000

Digamos, por ejemplo, que queremos obtener el valor verde de este color de píxeles. Podemos obtener fácilmente ese valor enmascarando y cambiando .

Nuestra mascara

Red Green Blue Alpha color : 10111001 10111001 10111001 00000000 green_mask : 00000000 11111111 00000000 00000000 masked_color = color & green_mask masked_color: 00000000 10111001 00000000 00000000

El operador & lógico se asegura de que solo se mantengan los valores donde la máscara es 1. Lo último que tenemos que hacer ahora es obtener el valor entero correcto desplazando todos esos bits a la derecha en 16 lugares (desplazamiento lógico a la derecha) .

green_value = masked_color >>> 16

Y luego, tenemos el entero que representa la cantidad de verde en el color de los píxeles:

Pixels-Green Value in Hex: 000000B9 Pixels-Green Value in Binary: 00000000 00000000 00000000 10111001 Pixels-Green Value in Decimal: 185

Esto se usa a menudo para codificar o decodificar formatos de imagen como jpg , png , ...

He intentado aprender C en mi tiempo libre, y otros idiomas (C #, Java, etc.) tienen el mismo concepto (y, a menudo, los mismos operadores) ...

Lo que me pregunto es, a nivel central, ¿qué hace el desplazamiento de bits (<<, >>, >>>), qué problemas puede ayudar a resolver y qué errores se esconden en la curva? En otras palabras, una guía absoluta para principiantes sobre el cambio de bits en toda su bondad.

Digamos que tenemos un solo byte:

0110110

Aplicando un solo bithift izquierdo nos consigue:

1101100

El cero de la izquierda se desplazó del byte y se agregó un nuevo cero al extremo derecho del byte.

Los bits no vuelven; son descartados. Eso significa que si cambia a la izquierda 1101100 y luego a la derecha, no obtendrá el mismo resultado.

Desplazar a la izquierda por N es equivalente a multiplicar por 2 ^N.

Desplazar hacia la derecha por N es (si está utilizando el complemento de unos ) equivale a dividir por 2 ^N y redondear a cero.

Bitshifting se puede usar para la multiplicación y división increíblemente rápidas, siempre que esté trabajando con una potencia de 2. Casi todas las rutinas de gráficos de bajo nivel utilizan el cambio de bits.

Por ejemplo, hace mucho tiempo atrás, usamos el modo 13h (320x200 256 colores) para los juegos. En el Modo 13h, la memoria de video se distribuyó secuencialmente por píxel. Eso significaba que para calcular la ubicación de un píxel, usaría los siguientes cálculos matemáticos:

memoryOffset = (row * 320) + column

Ahora, en esa época, la velocidad era crítica, por lo que usaríamos bitshifts para realizar esta operación.

Sin embargo, 320 no es una potencia de dos, por lo tanto, para solucionar esto, tenemos que descubrir qué potencia de dos suman a 320:

(row * 320) = (row * 256) + (row * 64)

Ahora podemos convertir eso en turnos de izquierda:

(row * 320) = (row << 8) + (row << 6)

Para un resultado final de:

memoryOffset = ((row << 8) + (row << 6)) + column

Ahora obtenemos el mismo desplazamiento que antes, excepto que en lugar de una operación de multiplicación costosa, usamos los dos cambios de bits ... en x86 sería algo como esto (nota, ha pasado una eternidad desde que hice el ensamblaje (nota del editor: corregida un par de errores y añadió un ejemplo de 32 bits)):

mov ax, 320; 2 cycles mul word [row]; 22 CPU Cycles mov di,ax; 2 cycles add di, [column]; 2 cycles ; di = [row]*320 + [column] ; 16-bit addressing mode limitations: ; [di] is a valid addressing mode, but [ax] isn''t, otherwise we could skip the last mov

Total: 28 ciclos en cualquier CPU antigua que tuviera estos tiempos.

Vrs

mov ax, [row]; 2 cycles mov di, ax; 2 shl ax, 6; 2 shl di, 8; 2 add di, ax; 2 (320 = 256+64) add di, [column]; 2 ; di = [row]*(256+64) + [column]

12 ciclos en la misma CPU antigua.

Sí, trabajaríamos tan duro para eliminar 16 ciclos de CPU.

En el modo de 32 o 64 bits, ambas versiones son mucho más cortas y más rápidas. Las modernas CPU de ejecución fuera de orden como Intel Skylake (ver http://agner.org/optimize/ ) tienen hardware muy rápido multiplicado (baja latencia y alto rendimiento), por lo que la ganancia es mucho menor. La familia de Bulldozer de AMD es un poco más lenta, especialmente para la multiplicación de 64 bits. En las CPU Intel y AMD Ryzen, dos turnos tienen una latencia ligeramente menor pero más instrucciones que una multiplicación (lo que puede llevar a un rendimiento más bajo):

imul edi, [row], 320 ; 3 cycle latency from [row] being ready add edi, [column] ; 1 cycle latency (from [column] and edi being ready). ; edi = [row]*(256+64) + [column], in 4 cycles from [row] being ready.

contra

mov edi, [row] shl edi, 6 ; row*64. 1 cycle latency lea edi, [edi + edi*4] ; row*(64 + 64*4). 1 cycle latency add edi, [column] ; 1 cycle latency from edi and [column] both being ready ; edi = [row]*(256+64) + [column], in 3 cycles from [row] being ready.

Los compiladores harán esto por usted: vea cómo gcc, clang y MSVC usan shift + lea cuando optimizan el return 320*row + col; .

Lo más interesante a tener en cuenta aquí es que x86 tiene una instrucción de desplazamiento y adición ( LEA ) que puede hacer pequeños cambios a la izquierda y agregar al mismo tiempo, con la instrucción de rendimiento y add . ARM es aún más poderoso: un operando de cualquier instrucción se puede cambiar a la izquierda oa la derecha de forma gratuita. Así que escalar por una constante de tiempo de compilación que se sabe que es una potencia de 2 puede ser incluso más eficiente que una multiplicación.

De acuerdo, en los tiempos modernos ... algo más útil ahora sería usar el cambio de bits para almacenar dos valores de 8 bits en un entero de 16 bits. Por ejemplo, en C #:

// Byte1: 11110000 // Byte2: 00001111 Int16 value = ((byte)(Byte1 >> 8) | Byte2)); // value = 000011111110000;

En C ++, los compiladores deberían hacer esto por usted si utilizó una struct con dos miembros de 8 bits, pero en la práctica no siempre.

Las operaciones bitwise, incluido el cambio de bit, son fundamentales para el hardware de bajo nivel o la programación integrada. Si lees una especificación para un dispositivo o incluso algunos formatos de archivos binarios, verás bytes, palabras y palabras clave, divididos en campos de bits alineados sin bytes, que contienen varios valores de interés. Acceder a estos campos de bits para leer / escribir es el uso más común.

Un ejemplo real simple en la programación de gráficos es que un píxel de 16 bits se representa de la siguiente manera:

bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | | Blue | Green | Red |

Para obtener el valor verde deberías hacer esto:

#define GREEN_MASK 0x7E0 #define GREEN_OFFSET 5 // Read green uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Explicación

Para obtener SOLAMENTE el valor de verde, que comienza en el desplazamiento 5 y finaliza en 10 (es decir, 6 bits de longitud), debe usar una máscara (bit), que cuando se aplica contra el píxel completo de 16 bits, producirá Sólo los bits que nos interesan.

#define GREEN_MASK 0x7E0

La máscara adecuada es 0x7E0, que en binario es 0000011111100000 (que es 2016 en decimal).

uint16_t green = (pixel & GREEN_MASK) ...;

Para aplicar una máscara, utilice el operador AND (&).

uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Después de aplicar la máscara, terminará con un número de 16 bits que en realidad es solo un número de 11 bits, ya que su MSB está en el bit 11. El verde en realidad solo tiene 6 bits de longitud, por lo que necesitamos #define GREEN_OFFSET 5 usando un cambio a la derecha (11 - 6 = 5), por lo tanto, el uso de 5 como desplazamiento ( #define GREEN_OFFSET 5 ).

También es común el uso de cambios de bits para la multiplicación rápida y la división por potencias de 2:

i <<= x; // i *= 2^x; i >>= y; // i /= 2^y;

Los operadores de cambio de bits hacen exactamente lo que su nombre implica. Ellos cambian bits. Aquí hay una breve (o no tan breve) introducción a los diferentes operadores de turno.

Los operadores

>> es el operador de desplazamiento a la derecha aritmético (o firmado).
>>> es el operador de desplazamiento a la derecha lógico (o sin signo).
<< es el operador de desplazamiento a la izquierda, y satisface las necesidades de los cambios lógicos y aritméticos.

Todos estos operadores pueden aplicarse a valores enteros ( int , long , posiblemente short y byte o char ). En algunos idiomas, la aplicación de los operadores de cambio a cualquier tipo de datos más pequeño que int redimensiona automáticamente el operando para que sea un int .

Tenga en cuenta que <<< no es un operador, porque sería redundante. También tenga en cuenta que C y C ++ no distinguen entre los operadores de desplazamiento correctos. Proporcionan solo el operador >> , y el comportamiento de desplazamiento hacia la derecha es la implementación definida para los tipos firmados.

Desplazamiento a la izquierda (<<)

Los enteros se almacenan, en memoria, como una serie de bits. Por ejemplo, el número 6 almacenado como un int 32 bits sería:

00000000 00000000 00000000 00000110

Desplazar este patrón de bits a la izquierda una posición ( 6 << 1 ) resultaría en el número 12:

00000000 00000000 00000000 00001100

Como puede ver, los dígitos se han desplazado hacia la izquierda una posición, y el último dígito de la derecha se rellena con un cero. También puede tener en cuenta que desplazarse hacia la izquierda equivale a la multiplicación por potencias de 2. Entonces 6 << 1 es equivalente a 6 * 2 , y 6 << 3 equivale a 6 * 8 . Un buen compilador de optimización reemplazará las multiplicaciones con turnos cuando sea posible.

Desplazamiento no circular

Tenga en cuenta que estos no son turnos circulares. Desplazando este valor a la izquierda una posición ( 3,758,096,384 << 1 ):

11100000 00000000 00000000 00000000

Resultados en 3,221,225,472:

11000000 00000000 00000000 00000000

El dígito que se desplaza "fuera del final" se pierde. No se envuelve alrededor.

Cambio lógico a la derecha (>>>)

Un cambio lógico a la derecha es lo contrario al cambio a la izquierda. En lugar de mover los bits a la izquierda, simplemente se mueven a la derecha. Por ejemplo, cambiando el número 12:

00000000 00000000 00000000 00001100

a la derecha por una posición ( 12 >>> 1 ) recuperaremos nuestros 6 originales:

00000000 00000000 00000000 00000110

Entonces vemos que desplazarse hacia la derecha es equivalente a la división por potencias de 2.

Los bits perdidos se han ido

Sin embargo, un cambio no puede reclamar bits "perdidos". Por ejemplo, si cambiamos este patrón:

00111000 00000000 00000000 00000110

a la izquierda 4 posiciones ( 939,524,102 << 4 ), obtenemos 2,147,483,744:

10000000 00000000 00000000 01100000

y luego retrocediendo ( (939,524,102 << 4) >>> 4 ) obtenemos 134,217,734:

00001000 00000000 00000000 00000110

No podemos recuperar nuestro valor original una vez que hemos perdido bits.

Derecha aritmética (>>)

El cambio aritmético a la derecha es exactamente igual al cambio lógico a la derecha, excepto que en lugar de rellenar con cero, rellena con el bit más significativo. Esto se debe a que el bit más significativo es el bit de signo o el bit que distingue los números positivos y negativos. Al rellenar con el bit más significativo, el cambio aritmético a la derecha conserva los signos.

Por ejemplo, si interpretamos este patrón de bits como un número negativo:

10000000 00000000 00000000 01100000

Tenemos el número -2,147,483,552. Cambiar esto a la derecha 4 posiciones con el cambio aritmético (-2,147,483,552 >> 4) nos daría:

11111000 00000000 00000000 00000110

o el número -134,217,722.

Así que vemos que hemos conservado el signo de nuestros números negativos utilizando el cambio a la derecha aritmética, en lugar del cambio a la derecha lógica. Y una vez más, vemos que estamos realizando división por potencias de 2.

Solo estoy escribiendo sugerencias y trucos, puede ser útil en las pruebas / exámenes.

n = n*2 : n = n<<1
n = n/2 : n = n>>1
Comprobando si n es la potencia de 2 (1,2,4,8, ...): !(n & (n-1)) cheque !(n & (n-1))
Obtención de x ^th bit de n : n |= (1 << x)
Comprobando si x es par o impar: x&1 == 0 (par)
Alternar el bit n de x: x ^ (1<<n)

Tenga en cuenta que en la implementación de Java, el número de bits a cambiar se modifica por el tamaño de la fuente.

Por ejemplo:

(long) 4 >> 65

es igual a 2. Usted podría esperar que el desplazamiento de los bits a la derecha 65 veces cero todo, pero en realidad es el equivalente de:

(long) 4 >> (65 % 64)

Esto es cierto para <<, >>, y >>>. No lo he probado en otros idiomas.

Tenga en cuenta que solo la versión de PHP de 32 bits está disponible en la plataforma Windows.

Luego, si por ejemplo cambia << o >> más de 31 bits, los resultados son inesperados. Por lo general, se devolverá el número original en lugar de ceros, y puede ser un error realmente complicado.

Por supuesto, si usa la versión de 64 bits de PHP (unix), debe evitar los cambios de más de 63 bits. Sin embargo, por ejemplo, MySQL usa el BIGINT de 64 bits, por lo que no debería haber ningún problema de compatibilidad.

ACTUALIZACIÓN: Desde PHP7 Windows, las compilaciones php finalmente pueden usar enteros de 64 bits completos: el tamaño de un entero depende de la plataforma, aunque un valor máximo de aproximadamente dos mil millones es el valor habitual (es decir, 32 bits con signo). Las plataformas de 64 bits generalmente tienen un valor máximo de alrededor de 9E18, excepto en Windows antes de PHP 7, donde siempre fue de 32 bits.

Una consecuencia es que lo siguiente depende de la implementación (de acuerdo con el estándar ANSI):

char x = -1; x >> 1;

x ahora puede ser 127 (01111111) o aún -1 (11111111).

En la práctica, suele ser lo último.