Después de de esta larga compilación de datos pudimos resolver esta cuestión que suelen tener ciertos usuarios. Te brindamos la respuesta y nuestro deseo es servirte de mucha ayuda.
Solución:
Los operadores de cambio 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 turnos.
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 firmar).<<es el operador de desplazamiento a la izquierda y satisface las necesidades de los desplazamientos tanto lógicos como aritméticos.
Todos estos operadores se pueden aplicar a valores enteros (int, long, posiblemente short y byte o char). En algunos lenguajes, aplicar los operadores de turno a cualquier tipo de datos menor 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.
También tenga en cuenta que C y C ++ no distinguen entre los operadores de turno correctos. Proporcionan solo el >> operador, y el comportamiento de desplazamiento a la derecha se define por implementación para tipos firmados. El resto de la respuesta usa los operadores C # / Java.
(En todas las implementaciones principales de C y C ++, incluidas GCC y Clang / LLVM, >> en tipos con signo es aritmética. Algunos códigos asumen esto, pero no es algo que garantice el estándar. No es indefinido, aunque; el estándar requiere implementaciones para definirlo de una forma u otra. Sin embargo, los desplazamientos a la izquierda de números con signo negativo es comportamiento indefinido (desbordamiento de enteros con signo). Entonces, a menos que necesite un cambio aritmético a la derecha, generalmente es una buena idea hacer su cambio de bits con tipos sin firmar).
Desplazamiento 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
Desplazando 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 una posición hacia la izquierda y el último dígito de la derecha se ha llenado con un cero. También puedes notar que desplazarse a la izquierda es equivalente 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 a la izquierda una posición (3,758,096,384 << 1):
11100000 00000000 00000000 00000000
da como resultado 3.221.225.472:
11000000 00000000 00000000 00000000
El dígito que se desplaza "al final" se pierde. No 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 en una posición (12 >>> 1) recuperará 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 pedazos perdidos se han ido
Sin embargo, un cambio no puede recuperar 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 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 el bit más significativo es el 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. 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.
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 una división por potencias de 2.
Digamos que tenemos un solo byte:
0110110
La aplicación de un solo desplazamiento de bits a la izquierda nos da:
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 traspasan; se descartan. Eso significa que si cambia a la izquierda 1101100 y luego a la derecha, no obtendrá el mismo resultado.
Desplazarse a la izquierda por N equivale a multiplicar por 2norte.
Desplazarse a la derecha por N es (si está usando el complemento de unos) es el equivalente a dividir por 2norte y redondeando a cero.
El cambio de bits se puede utilizar para multiplicaciones y divisiones 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, en los viejos tiempos, usábamos 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 fundamental, por lo que usaríamos bitshifts para realizar 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 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 desplazamientos de bits ... en x86 sería algo como esto (nota, ha pasado una eternidad desde que hice el ensamblaje (nota del editor: corregido 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 tan 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 servicio 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 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.
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 al optimizar return 320*row + col;.
Lo más interesante a tener en cuenta aquí es que x86 tiene una instrucción de cambio y suma (LEA) que puede hacer pequeños cambios a la izquierda y agregar al mismo tiempo, con el rendimiento como un add instrucció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 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.
Bien, 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 usó un struct con dos miembros de 8 bits, pero en la práctica no siempre.
Las operaciones bit a bit, incluido el desplazamiento de bits, 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 dwords, divididos en campos de bits no alineados con bytes, que contienen varios valores de interés. Acceder a estos campos de bits para lectura / escritura 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, 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 longitud), debe usar una máscara (de bits), que cuando se aplica contra todo el píxel de 16 bits, producirá solo las partes 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, usa 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 undécimo 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 el uso de cambios de bits para multiplicaciones y divisiones rápidas por potencias de 2:
i <<= x; // i *= 2^x;
i >>= y; // i /= 2^y;