Pregunta ¿Qué son los operadores de desplazamiento bit a bit (bit shift) y cómo funcionan?


He estado intentando 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 cambio de bit (<<, >>, >>>), qué problemas puede ayudar a resolver y qué problemas acechan en la curva. En otras palabras, una guía absoluta para principiantes sobre el cambio de bit en toda su bondad.


1189
2017-09-26 19:47


origen


Respuestas:


Los operadores de cambio de bit hacen exactamente lo que su nombre implica. Ellos cambian bits. Aquí hay una breve introducción (o no tan breve) 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 cumple con las necesidades de los cambios lógicos y aritméticos.

Todos estos operadores se pueden aplicar 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 cambia automáticamente el tamaño del operando para que sea 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 a la derecha. Ellos proporcionan solo el >> operador, y el comportamiento de desplazamiento a la derecha es la implementación definida para los tipos firmados.


Cambio a la izquierda (<<)

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

00000000 00000000 00000000 00000110

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

00000000 00000000 00000000 00001100

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

Desplazamiento no circular

Tenga en cuenta que estos son no turnos circulares. Cambiando este valor a la izquierda en 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


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

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

00000000 00000000 00000000 00001100

a la derecha en una posición (12 >>> 1) recibirá nuestro 6 original:

00000000 00000000 00000000 00000110

Entonces vemos que el desplazamiento a la derecha es equivalente a la división por poderes 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 los bits.


Desplazamiento aritmético a la derecha (>>)

El desplazamiento aritmético a la derecha es exactamente como el desplazamiento lógico a la derecha, excepto que en lugar de relleno con cero, rellena con el bit más significativo. Esto se debe a que el bit más significativo es el firmar bit, o el bit que distingue los números positivos y negativos. Al rellenar con el bit más significativo, el desplazamiento aritmético hacia la derecha preserva el signo.

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 las 4 posiciones correctas con el desplazamiento aritmético (-2,147,483,552 >> 4) nos daría:

11111000 00000000 00000000 00000110

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

Entonces vemos que hemos conservado el signo de nuestros números negativos usando el desplazamiento aritmético a la derecha, en lugar del desplazamiento lógico a la derecha. Y una vez más, vemos que estamos realizando división por poderes de 2.


1508
2017-09-26 20:46



Digamos que tenemos un solo byte:

0110110

La aplicación de un único cambio de bits a la izquierda nos permite:

1101100

El cero más a la izquierda se desplazó fuera del byte y se agregó un nuevo cero al extremo derecho del byte.

Los bits no se vuelcan; ellos son descartados Eso significa que si dejó el turno 1101100 y luego lo desplazó a la derecha, no obtendrá el mismo resultado.

Desplazar a la izquierda por N equivale a multiplicar por 2norte.

Cambiando a la derecha por N es (si está usando el complemento de uno) es el equivalente a dividir por 2norte y redondeando a cero.

Bitshifting se puede usar para una multiplicación y división increíblemente rápida, siempre que trabajes con una potencia de 2. Casi todas las rutinas de gráficos de bajo nivel usan el cambio de bits.

Por ejemplo, en los viejos tiempos, usamos el modo 13h (320x200 256 colores) para juegos. En el Modo 13h, la memoria de video se distribuyó secuencialmente por píxel. Eso significaba calcular la ubicación de un píxel, usaría las siguientes operaciones matemáticas:

memoryOffset = (row * 320) + column

Ahora, en ese día y edad, la velocidad era crítica, por lo que usaríamos cambios de bits para hacer esta operación.

Sin embargo, 320 no es una potencia de dos, así que para evitar esto tenemos que descubrir qué es un poder de dos que sumados hace 320:

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

Ahora podemos convertir eso en cambios a la 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 costosa operación de multiplicación, usamos los dos cambios de bits ... en x86 sería algo como esto (nota, ha sido para siempre desde que hice el ensamblaje (nota del editor: corregida) un par de errores y agregó 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 así para reducir los 16 ciclos de CPU.

En el modo de 32 o 64 bits, ambas versiones son mucho más cortas y rápidas. CPU modernas de ejecución fuera de servicio como Intel Skylake (ver http://agner.org/optimize/) tienen multiplexación de hardware muy rápida (baja latencia y alto rendimiento), por lo que la ganancia es mucho menor. La familia AMD Bulldozer 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 conducir a un menor rendimiento):

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.

vs.

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 al optimizar return 320*row + col;.

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


OK, en los tiempos modernos ... algo más útil ahora sería usar el intercambio 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 ti si usabas un struct con dos miembros de 8 bits, pero en la práctica no siempre.


169
2017-09-26 19:55



Las operaciones a nivel de bit, incluido el cambio de bit, son fundamentales para el hardware de bajo nivel o la programación integrada. Si lee una especificación para un dispositivo o incluso algunos formatos de archivos binarios, verá los bytes, las palabras y los dwords divididos en campos de bits alineados no en byte, 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 llegar al valor verde, harías 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 (de bit), que cuando se aplica contra el píxel de 16 bits completo, producirá solo los bits en los que estamos interesados

#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, usa el operador AND (&).

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

Después de aplicar la máscara, terminarás 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 11mo bit. El verde es en realidad de solo 6 bits, por lo que debemos reducirlo utilizando un desplazamiento a la derecha (11 - 6 = 5), de ahí el uso de 5 como desplazamiento (#define GREEN_OFFSET 5)

También es común usar cambios de bit para una multiplicación y división rápida por potencias de 2:

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

83
2017-09-26 22:22



Enmascaramiento y cambio de bits

El cambio de bit se usa 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 de 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 ese valor fácilmente enmascaramiento y cambiando.

Nuestra máscara:

                  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

La lógica & el operador se asegura de que solo se guarden los valores donde la máscara es 1. Lo último que tenemos que hacer ahora es obtener el valor entero correcto al cambiar todos esos bits a la derecha por 16 lugares (cambio de sentido lógico a la derecha).

 green_value = masked_color >>> 16

Et voilá, tenemos el número 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 descodificar formatos de imagen como jpg,png,....


39
2018-03-31 10:49



Uno de los problemas 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, generalmente es el último.


26
2017-09-26 20:07



Tenga en cuenta que en la implementación de Java, el número de bits para modificar está modificado por el tamaño de la fuente.

Por ejemplo:

(long) 4 >> 65

es igual a 2. Es posible que espere que al cambiar los bits a la derecha 65 veces se ponga en 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.


8
2017-08-28 13:16



Estoy escribiendo consejos y trucos solamente, puede resultar útil en exámenes / exámenes.

  1. n = n*2: n = n<<1
  2. n = n/2: n = n>>1
  3. Comprobando si n es potencia de 2 (1,2,4,8, ...): cheque !(n & (n-1))
  4. Consiguiendo Xth un poco de n: n |= (1 << x)
  5. Comprobando si x es par o impar: x&1 == 0 (incluso)
  6. Alternar el norteth poco de x: x ^ (1<<n)

6
2017-10-11 22:43



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

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

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

ACTUALIZACIÓN: desde PHP7 Windows, las compilaciones de php finalmente pueden usar enteros completos de 64 bits: 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 firmados). Las plataformas de 64 bits generalmente tienen un valor máximo de aproximadamente 9E18, excepto en Windows anterior a PHP 7, donde siempre fue de 32 bits.


-2
2017-10-23 14:28