He estado tratando de 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, en un nivel básico, lo que hace de desplazamiento de bits ( <<, >>, >>>) hacer, qué problemas puede ayudar a resolver, y qué trampas están al acecho alrededor de la curva? En otras palabras, una guía absoluta para principiantes para cambiar un poco en toda su bondad.

Los operadores de desplazamiento de bits hacen exactamente lo que su nombre implica. Cambian pedazos. 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 los cambios lógicos y aritméticos.

Todos estos operadores se puede aplicar a los valores enteros ( int, long, posiblemente shorty byteo char). En algunos idiomas, la aplicación de los operadores de desplazamiento a cualquier tipo de datos más pequeño que intredimensiona automáticamente el operando para que sea un int.

Tenga en cuenta que <<<no es un operador, ya que sería redundante.

También tenga en cuenta que C y C ++ no distinguen entre los operadores de desplazamiento a la derecha . Proporcionan solo el >>operador, y el comportamiento de desplazamiento hacia la derecha es la implementación definida para los tipos con signo. El resto de la respuesta usa los operadores C # / Java.

(En todas las implementaciones principales de C y C ++, incluidas GCC y Clang / LLVM, los >>tipos con signo son aritméticos. Algunos códigos asumen esto, pero no es algo que el estándar garantice. Sin embargo, no está indefinido ; el estándar requiere implementaciones para definirlo como uno Sin embargo, los desplazamientos a la izquierda de los números con signo negativo es un comportamiento indefinido (desbordamiento de entero con signo). Por lo tanto, a menos que necesite un desplazamiento aritmético a la derecha, generalmente es una buena idea hacer su desplazamiento de bits con tipos sin signo).

Desplazamiento a la izquierda (<<)

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

00000000 00000000 00000000 00000110

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

00000000 00000000 00000000 00001100

Como puede ver, los dígitos se han desplazado hacia la izquierda en una posición, y el último dígito a la derecha se llena con un cero. También puede notar que desplazar a la izquierda es equivalente a la multiplicación por potencias de 2. Entonces, 6 << 1es equivalente a 6 * 2, y 6 << 3es equivalente 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 por 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 "del final" se pierde. No se envuelve.

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

Un desplazamiento lógico a la derecha es el inverso al desplazamiento a 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 por una posición ( 12 >>> 1) volverá nuestro 6 original:

00000000 00000000 00000000 00000110

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

Los trozos 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.

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 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 desplazamiento 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. Desplazar esto a 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 al usar 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.

Digamos que tenemos un solo byte:

0110110

La aplicación de un único desplazamiento a la izquierda nos consigue:

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

Cambiantes dada por N es equivalente a multiplicar por 2 ^N .

Desplazar a la derecha por N es (si está utilizando el complemento de unos ) es el equivalente a dividir por 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 esa época, 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, por lo que para solucionar esto tenemos que descubrir cuál es la 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 tenemos 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 (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 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. Las CPU modernas de ejecución fuera de orden como Intel Skylake (consulte 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 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 Microsoft Visual C ++ usan shift + lea cuando optimizanreturn 320*row + col; .

Lo más interesante a tener en cuenta aquí es que x86 tiene una instrucción shift-and-add ( LEA) que puede hacer pequeños cambios a la izquierda y agregar al mismo tiempo, con el rendimiento como una addinstrucción. 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 structcon dos miembros de 8 bits, pero en la práctica no siempre lo hacen.

Las operaciones bit a bit, incluido el cambio de bit, son fundamentales para hardware de bajo nivel o programación integrada. Si lee una especificación para un dispositivo o incluso algunos formatos de archivos binarios, 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 gráfica 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, 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 SOLAMENTE el valor de 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 a 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, use 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 11 ° bit. El verde en realidad solo tiene 6 bits de longitud, 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 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 representan 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 del color de este píxel. Podemos obtener ese valor fácilmente enmascarando 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

El &operador lógico garantiza 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à, tenemos el número entero que representa la cantidad de verde en el color del píxel:

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

Esto a menudo se utiliza para la codificación o descodificación de los formatos de imagen como jpg, png, etc.

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, suele ser lo último.

Solo escribo consejos y trucos. Puede ser útil en pruebas y exámenes.

1. n = n*2: n = n<<1
2. n = n/2: n = n>>1
3. Verificando si n es potencia de 2 (1,2,4,8, ...): verifica !(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. Activar el n ^ésimo 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.

Implementé la respuesta de Ravi Prakash en Python.

# Basic bit operations
# Integer to binary
print(bin(10))

# Binary to integer
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 second bit is 0

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

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

Entonces, si, por ejemplo, desplaza << 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 el cambio 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 PHP 7 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 (32 bits con signo). 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.