¿Hay alguna buena razón para usar el cambio de bit a excepción de la matemática rápida?

Question

Entiendo las operaciones bit a bit y cómo pueden ser útiles para diferentes propósitos, p. permisos Sin embargo, no parece entender qué uso tienen los operadores de cambio de bit. Entiendo cómo funcionan, pero no puedo pensar en ningún escenario donde pueda querer usarlos a menos que quiera hacer una multiplicación o división realmente rápida. ¿Hay alguna otra razón para usar el cambio de bit?

Answer 1

Hay muchas razones, aquí:

1. Digamos que representa a una imagen en blanco y negro como una secuencia de bits y desea establecer un único píxel en esta imagen de manera genérica. Por ejemplo, su desplazamiento de bytes puede ser x >> 3 y su desplazamiento de bit puede ser x & 0x7 y puede establecer ese bit por: byte = byte | (1 < < (x & 0x7));
2. Implementación de algoritmos de compresión de datos en los que se tratan secuencias de bits de longitud variable, p. codificación Huffman.
3. Estás interactuando con algún hardware, p. un dispositivo de comunicación serie, y necesita leer o establecer algunos bits de control.

Por esas y otras razones, la mayoría de los procesadores tienen instrucciones de cambio de bit y/o rotación, así como otras instrucciones lógicas (y/o/xor/no).

Históricamente, la multiplicación y la división fueron significativamente más lentas ya que son operaciones más complejas y algunas CPU no las tenían.

También vea aquí: Have you ever had to use bit shifting in real projects?

Answer 2

Como indica, un cambio a la izquierda es lo mismo que una multiplicación por dos. Al menos es cuando estamos hablando de cantidades sin firmar. El significado de un "desplazamiento a la izquierda" de una cantidad firmada es ... dependiente del idioma.

Con compiladores modernos, realmente no hay diferencia entre escribir "i = x * 2;" y "i = x < < 1;" El compilador generará el código más eficiente. Entonces, en ese sentido, no hay razón para preferir el cambio sobre la multiplicación.

Algunos algoritmos funcionan desplazando una cantidad que queda un bit y luego ajustando el bit bajo a 0 o 1. Algunos algoritmos de compresión simples funcionan de esta manera. Por ejemplo, si su valor acumulado está en la variable x, y el valor actual (0 o 1) está en y, entonces tiene más sentido escribir "x = (x < < 1) | y", en lugar de "x = (x * 2) + y ". Ambos hacen lo mismo, pero el primero es más notablemente correcto. No tiene que pensar: "oh, correcto, multiplicar por dos es lo mismo que un cambio a la izquierda".

Además, cuando se trata de algoritmos que cambian los bits, es más conveniente desplazarse hacia la izquierda o hacia la derecha en un número determinado de bits que calcular el múltiplo de 2 que desea multiplicar o dividir.

Entonces, mientras que normalmente no hay un beneficio en el rendimiento al cambiar en lugar de multiplicar, al menos no cuando se trabaja con idiomas de alto nivel, hay momentos en que tener la capacidad de cambiar hace que lo que está haciendo sea más fácil de entender.

Answer 3

Hay muchos lugares donde las operaciones de cambio de bits utilizan regularmente fuera de su uso en los cálculos numéricos. Por ejemplo, Bitboard es una estructura de datos que se usa comúnmente en juegos de mesa para la representación de la mesa.Algunos de los motores de ajedrez más fuertes usan esta estructura de datos principalmente para la velocidad y la facilidad de la generación y evaluación de movimientos. Estos programas usan mucho las operaciones de bits y las operaciones de cambio de bit se usan específicamente en muchos contextos, como encontrar máscaras de bits, generar nuevos movimientos en el tablero, calcular el logaritmo muy rápidamente, etc. Incluso hay cálculos numéricos muy avanzados que pueden ser hecho elegantemente mediante el uso inteligente de operaciones de bits. Echa un vistazo a this site para hackear bit twits - muchos de esos algoritmos utilizan operadores de turno. Las operaciones de cambio de bit se utilizan regularmente en la programación del controlador de dispositivo, el desarrollo de códec, la programación de sistemas integrados, etc.

Answer 4

El desplazamiento permite acceder a bits específicos dentro de una variable. La expresión (n >> p) & ((1 << m) - 1) recupera una porción de 0-bit de m de la variable n con un desplazamiento de p bits desde la derecha.

Esto permite que su programa utilice enteros que no son múltiplos de 8 bits, lo que es útil para la compresión de datos.

Por ejemplo, lo usé en mis programas Netflix Prize para empacar registros (ID de usuario de 22 bits + ID de película de 15 bits + fecha de 12 bits + calificación de 3 bits) en un uint64_t (con 12 bits de repuesto) .

Un caso especial muy común es empacar 8 variables bool en cada byte. (permisos de archivos UNIX, mapas de bits en blanco y negro, CPU flags registers, etc.)

Además, la manipulación de bits se utiliza en UTF-8, que es un muy popular codificación de caracteres. Los caracteres Unicode se representan distribuyendo sus bits en 1, 2, 3 o 4 bytes.