Digamos que tenemos un solo byte:{[16]]}

0110110

Aplicando un solo cambio de bit a la izquierda nos lleva:

1101100

El cero más a la izquierda fue desplazado fuera del byte, y un nuevo cero fue añadido al extremo derecho del byte.

Los bits no se vuelcan; se descartan. Eso significa que si dejas shift 1101100 y luego a la derecha, no obtendrás el mismo resultado.

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

Cambiando a la derecha por N es (si está utilizando el complemento de ones) es el equivalente de dividir por 2^N y redondear a cero.

Bitshifting se puede utilizar para multiplicación y división increíblemente rápida, siempre que esté trabajando con una potencia de 2. Casi todas las rutinas gráficas de bajo nivel usan bitshifting.

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

memoryOffset = (row * 320) + column

Ahora, en ese día y época, la velocidad era crítica, por lo que usaríamos bitshifts para hacer esta operación.

Sin embargo, 320 no es una potencia de dos, por lo que para evitar esto tenemos que averiguar qué es una potencia de dos que sumada hace 320:{[16]]}

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

Ahora podemos convertir eso en cambios a la izquierda:{[16]]}

(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 en lugar de una costosa operación de multiplicación, usamos los dos bitshifts...in x86 sería algo como esto (nota, ha sido siempre desde que he hecho el ensamblaje (nota del editor: corregido un par de errores y agregado 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 duro para reducir 16 ciclos de CPU.

En modo de 32 o 64 bits, ambas versiones son mucho más cortas y rápidas. CPU modernas de ejecución fuera de orden como Intel Skylake (ver http://agner.org/optimize / ) tienen una multiplicació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 multiplicar 64 bits. En las CPU Intel, y AMD Ryzen, dos turnos son ligeramente menor latencia, pero más instrucciones que una multiplicación (lo que puede conducir a una 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 la instrucción performance as y add. ARM es aún más potente: un operando de cualquier instrucción se puede desplazar a la izquierda o a la derecha de forma gratuita. Tan 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.

OK, de vuelta en los días modernos... algo más útil ahora sería usar bitshifting 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 utilizas un struct con dos miembros de 8 bits, pero en la práctica no siempre lo haces.

Las operaciones Bitwise, incluyendo bit shift, son fundamentales para el hardware de bajo nivel o la programación embebida. Si lee una especificación para un dispositivo o incluso algunos formatos de archivo binario, verá bytes, palabras y dwords, divididos en campos de bits no alineados con bytes, que contienen varios valores de interés. El acceso a estos campos de bits para leer/escribir es el uso más común.

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

  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, haría esto:

 #define GREEN_MASK  0x7E0
 #define GREEN_OFFSET  5

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

Explicación

Para obtener el valor de verde SOLAMENTE, que comienza en el desplazamiento 5 y termina en 10 (es decir, 6 bits de largo), necesita usar una máscara (bit), que cuando se aplica contra todo el píxel de 16 bits, producirá solo los bits que nos interesan.

#define GREEN_MASK  0x7E0

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

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

Para aplicar una máscara, se utiliza el operador Y (&).

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 bit 11. El verde es en realidad solo 6 bits de largo, por lo que necesitamos reducirlo usando 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 bits para la multiplicación y división rápidas por potencias de 2:

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

Enmascaramiento y desplazamiento de bits

El desplazamiento de bits 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 fácilmente ese valor por enmascarando y cambiando.

Nuestro 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

El operador lógico & asegura 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 por 16 lugares (desplazamiento lógico a la derecha).

 green_value = masked_color >>> 16

Et voilá, 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,....

Una conclusión 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.

Tenga en cuenta que en la implementación de Java, el número de bits a desplazar se mod'd por el tamaño de la fuente.

Por ejemplo:

(long) 4 >> 65

Es Igual a 2. Se podría esperar que el desplazamiento de los bits a la derecha 65 veces sería 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.

Estoy escribiendo consejos y trucos solo, puede ser útil en las pruebas/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,...): check !(n & (n-1))
4. Obteniendo x^th bit de n: n |= (1 << x)
5. Comprobando si x es par o impar: x&1 == 0 (par)
6. Alternar el n^th bit de x: x ^ (1<<n)

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

Entonces, si por ejemplo cambia > 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 utiliza la versión de 64 bits de PHP (unix), debe evitar el desplazamiento de más de 63 bits. Sin embargo, por ejemplo, MySQL utiliza el BIGINT de 64 bits, por lo que no debería haber ninguna compatibilidad problema.

ACTUALIZACIÓN: Desde Windows PHP7, 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 era de 32 bits.