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

https://stackoverflow.com/questions/141525

02-07-2019
|

Pregunta

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

Lo que me pregunto es, a nivel central, ¿qué significa el cambio de bits (<<, >>, >>>) hacen, ¿qué problemas puede ayudar a resolver y qué trampas acechan a la vuelta de la esquina?En otras palabras, una guía absoluta para principiantes sobre el cambio de bits en todas sus bondades.

Solución

Los operadores de desplazamiento de bits hacen exactamente lo que su nombre implica.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 con signo).
>>> 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 desplazamientos 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, aplicar los operadores de turno a cualquier tipo de datos más pequeño que int cambia automáticamente el tamaño del operando para que sea un int.

Tenga en cuenta que <<< no es un operador, porque sería redundante.Tenga en cuenta también que C y C++ no distinguen entre los operadores de desplazamiento a la derecha.Proporcionan sólo el >> operador, y el comportamiento de desplazamiento a la derecha se define en la implementación para tipos con signo.

Desplazamiento a la izquierda (<<)

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

00000000 00000000 00000000 00000110

Desplazando este patrón de bits a la izquierda una posición (6 << 1) daría como resultado el número 12:

00000000 00000000 00000000 00001100

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

Cambio no circular

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

11100000 00000000 00000000 00000000

resulta en 3.221.225.472:

11000000 00000000 00000000 00000000

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

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

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

00000000 00000000 00000000 00001100

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

00000000 00000000 00000000 00000110

Entonces vemos que desplazarse hacia la derecha equivale a dividir por potencias de 2.

Los bits perdidos se han ido

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

00111000 00000000 00000000 00000110

hacia la izquierda 4 posiciones (939,524,102 << 4), obtenemos 2.147.483.744:

10000000 00000000 00000000 01100000

y luego retroceder ((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.

Desplazamiento aritmético a la derecha (>>)

El desplazamiento aritmético a la derecha es exactamente igual al desplazamiento 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 la parte más significativa es la firmar bit, o el bit que distingue números positivos y negativos.Al rellenar con el bit más significativo, el desplazamiento aritmético a la derecha conserva 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.Desplazando esto hacia la derecha 4 posiciones 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 preservado 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 una división por potencias de 2.

Otros consejos

Digamos que tenemos un solo byte:

La aplicación de un solo desplazamiento de bits a la izquierda nos lleva:

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; Se descartan. Eso significa que si dejó el desplazamiento 1101100 y luego lo desplazó hacia la derecha, no obtendrá el mismo resultado.

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

Desplazar a la derecha por N es (si está usando complementos de uno ) es el equivalente a dividir entre 2 ^N y redondear a cero.

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

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

memoryOffset = (row * 320) + column

Ahora, en aquellos tiempos, 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 una potencia de dos que sumados hacen 320:

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

Ahora podemos convertir eso en desplazamientos 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 pasado una eternidad desde que hice el ensamblaje (editor nota: corrigió 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 duro para reducir 16 ciclos de CPU.

En el modo de 32 o 64 bits, ambas versiones se vuelven 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 la multiplicación de 64 bits. En las CPU Intel y AMD Ryzen, dos cambios tienen una latencia ligeramente más baja 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 comoinstrucción hift-and-add (LEA) que puede hacer pequeños cambios a la izquierda y agregar al mismo tiempo, con el rendimiento como y la instrucción add. ARM es aún más poderoso: un operando de cualquier instrucción se puede desplazar hacia la izquierda o hacia la derecha de forma gratuita. Por lo tanto, escalar mediante 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, en los tiempos modernos ... algo más útil ahora sería usar el desplazamiento 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ó un struct con dos miembros de 8 bits, pero en la práctica no siempre.

Las operaciones bit a 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 archivo binario, verá bytes, palabras y palabras clave, divididas 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, debe hacer 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 SOLO verde, que comienza en el desplazamiento 5 y termina en 10 (es decir, 6 bits de largo), debe usar una máscara (bit), que cuando se aplica contra el píxel completo 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, use el operador AND (& amp;).

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 11 ° bit. El verde en realidad tiene solo 6 bits de longitud, por lo que debemos 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 de bits & amp; Cambiando

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 determinado 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 ese valor fácilmente enmascarando y desplazando .

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

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 en 16 lugares (desplazamiento lógico a la derecha) .

 green_value = masked_color >>> 16

Et voil & # 225 ;, 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 decodificar formatos de imagen como jpg, png, ....

Un problema 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 lo último.

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

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

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

Por ejemplo:

(long) 4 >> 65

es igual a 2. Puede esperar que el desplazamiento de los bits a la derecha 65 veces ponga 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.

Algunas operaciones / manipulaciones de bits útiles en Python. Se implementaron las respuestas de @Ravi Prakash en Python.

# basic bit operations
# int to bin
print(bin(10))

# bin to int
print(int('1010',2))

# multiplying x with 2 .... x**2== x << 1
print(200<<1)

# dividing x with 2 .... x /2 == x >> 1
print(200>>1)

# modulo x with 2 .... x%2 == x&1
if 20&1==0:
    print("20 is a even number")

# check if n is power of 2 : check !(n & (n-1))
print(not(33 &(33-1)))

# getting xth bit of n : (n>>x)&1
print((10>>2)&1) # bin of 10==1010 and 2nd bit is 0

# toggle nth bit of x : x^(1<<n)
# take bin(10)==1010 and toggling 2nd bit in bin(10) we get 1110 === bin(14)
print(10^(1<<2))

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

Entonces, por ejemplo, si desplazas < < 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 utiliza la versión de PHP de 64 bits (unix), debe evitar el desplazamiento 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 número 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 suelen tener un valor máximo de aproximadamente 9E18, excepto en Windows anterior a PHP 7, donde siempre era de 32 bits.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow