He estado intentando 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 un nivel básico, ¿qué hace el cambio de bits (<<
, >>
, >>
), qué problemas puede ayudar a resolver, y qué gotchas acechan a la vuelta de la esquina? En otras palabras, una guía para principiantes absolutos sobre el cambio de bits en toda su bondad.
Los operadores de desplazamiento de bits hacen exactamente lo que su nombre indica. Cambian los bits. He aquí una breve (o no tan breve) introducción a los diferentes operadores de desplazamiento.
>>
es el operador aritmético (o con signo) de desplazamiento a la derecha.>>>
es el operador lógico (o sin signo) de desplazamiento a la derecha.<<
es el operador de desplazamiento a la izquierda, y satisface las necesidades de los desplazamientos lógicos y aritméticos.Todos estos operadores pueden aplicarse a valores enteros (int
, long
, posiblemente short
y byte
o char
). En algunos lenguajes, la aplicación de los operadores de desplazamiento a cualquier tipo de datos menor que int
redimensiona automáticamente el operando para que sea un int
.
Tenga en cuenta que <<<
no es un operador, porque sería redundante.
Observe también que C y C++ no distinguen entre los operadores de desplazamiento a la derecha. Sólo proporcionan el operador >>
, y el comportamiento de desplazamiento a la derecha está definido por la implementación para los tipos con signo. El resto de la respuesta utiliza los operadores de C# / Java.
(En todas las implementaciones principales de C y C++, incluyendo gcc y clang/LLVM, >>
en tipos con signo es aritmético. Algunos códigos lo asumen, pero no es algo que el estándar garantice. Sin embargo, no está indefinido; el estándar requiere que las implementaciones lo definan de una forma u otra. Sin embargo, el desplazamiento a la izquierda de números con signo negativo es un comportamiento indefinido (desbordamiento de enteros con signo). Así que, a menos que necesite un desplazamiento aritmético a la derecha, suele ser una buena idea hacer su desplazamiento de bits con tipos sin signo).
Los números enteros se almacenan, en memoria, como una serie de bits. Por ejemplo, el número 6 almacenado como un int
de 32 bits sería:
00000000 00000000 00000000 00000110
Desplazando este patrón de bits hacia la izquierda una posición (6 << 1
) se obtendría el número 12:
00000000 00000000 00000000 00001100
Como puede ver, los dígitos se han desplazado a la izquierda una posición, y el último dígito de la derecha se rellena con un cero. También puede notar que el desplazamiento a la izquierda es equivalente a la multiplicación por potencias de 2. Así que 6 << 1
es equivalente a 6 * 2
, y 6 << 3
es equivalente a 6 * 8
. Un buen compilador optimizador sustituirá las multiplicaciones por desplazamientos cuando sea posible.
Tenga en cuenta que estos son no desplazamientos circulares. Desplazando este valor hacia la izquierda en 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 extremo" se pierde. No se envuelve alrededor.
Un desplazamiento lógico a la derecha es lo contrario al desplazamiento a la izquierda. En lugar de mover los bits a la izquierda, simplemente se mueven a la derecha. Por ejemplo, desplazando el número 12:
00000000 00000000 00000000 00001100
a la derecha en una posición (12 >> 1
) recuperará nuestro 6 original:
00000000 00000000 00000000 00000110
Así que vemos que el desplazamiento a la derecha es equivalente a la división por potencias de 2.
Sin embargo, un desplazamiento no puede recuperar los bits "perdidos". Por ejemplo, si desplazamos 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 desplazando hacia atrás ((939.524.102 << 4) >> 4
) obtenemos 134.217.734:
00001000 00000000 00000000 00000110
No podemos recuperar el valor original una vez que hemos perdido bits.
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 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. Desplazando 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.
Así que vemos que hemos preservado el signo de nuestros números negativos mediante el uso del desplazamiento aritmético a la derecha, en lugar del desplazamiento lógico a la derecha. Y una vez más, vemos que estamos realizando la división por potencias de 2.
Digamos que tenemos un solo byte:
0110110
Aplicando un único desplazamiento de bits a la izquierda obtenemos:
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 desplazan; se descartan. Esto significa que si se desplaza a la izquierda 1101100 y luego se desplaza a la derecha, no se obtendrá el mismo resultado.
Desplazar a la izquierda por N es equivalente a multiplicar por 2N.
Desplazar a la derecha por N es (si está usando complemento a unos') el equivalente a dividir por 2N y redondear a cero.
El desplazamiento de bits se puede utilizar para multiplicar y dividir a una velocidad increíble, siempre que se trabaje con una potencia de 2. Casi todas las rutinas gráficas de bajo nivel utilizan el desplazamiento 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 vídeo se distribuía secuencialmente por píxeles. Eso significaba que para calcular la ubicación de un píxel, se utilizaba la siguiente matemática:
memoryOffset = (row * 320) + column
Ahora bien, en esa época, la velocidad era crítica, por lo que se utilizaba el desplazamiento de bits para realizar esta operación.
Sin embargo, 320 no es una potencia de dos, así que para evitarlo tenemos que averiguar cuál es la potencia de dos que sumada da 320:
(row * 320) = (row * 256) + (row * 64)
Ahora podemos convertirlo 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 desplazamientos de bits... en x86 sería algo así (nota, hace una eternidad que no hago ensamblaje (nota del editor: corregidos un par de errores y añadido 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 timings.
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í de duro para recortar 16 ciclos de CPU.
En el modo de 32 o 64 bits, ambas versiones son mucho más cortas y rápidas. Las CPUs modernas de ejecución fuera de orden como Intel Skylake (ver http://agner.org/optimize/) tienen una multiplicación por hardware muy rápida (baja latencia y alto rendimiento), por lo que la ganancia es mucho menor. La familia Bulldozer de AMD es un poco más lenta, especialmente para la multiplicación de 64 bits. En las CPUs de Intel, y AMD Ryzen, los dos turnos tienen una latencia ligeramente inferior, pero más instrucciones que un multiplicador (lo que puede llevar 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 lo harán por ti: Vea cómo gcc, clang y MSVC utilizan shift+lea cuando optimizan return 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 desplazamientos a la izquierda y sumar al mismo tiempo, con el rendimiento de una instrucción add
. ARM es aún más potente: un operando de cualquier instrucción puede ser desplazado a la izquierda o a 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.
Vale, volviendo a los tiempos modernos... algo más útil ahora sería utilizar 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 ti si utilizas una estructura
con dos miembros de 8 bits, pero en la práctica no siempre lo hacen.
Un inconveniente es que lo siguiente depende de la implementación (según la norma ANSI):
char x = -1;
x >> 1;
x puede ser ahora 127 (01111111) o todavía -1 (11111111).
En la práctica, suele ser esto último.