Manipulación de bits

La manipulación de bits consiste en manipular algorítmicamente bits u otros datos más cortos que una palabra . Las tareas de programación que requieren manipulación de bits incluyen el control de dispositivos de bajo nivel, algoritmos de detección y corrección de errores , compresión de datos , algoritmos de cifrado y optimización . Para la mayoría de las demás tareas, los lenguajes de programación modernos permiten al programador trabajar directamente con abstracciones en lugar de con los bits que las representan.

El código fuente que realiza manipulación de bits utiliza las operaciones bit a bit : AND, OR, XOR, NOT y posiblemente otras operaciones análogas a los operadores booleanos; también existen desplazamientos de bits y operaciones para contar unos y ceros, encontrar uno o cero alto y bajo, establecer, restablecer y probar bits, extraer e insertar campos, enmascarar y poner a cero campos, y agrupar y dispersar bits hacia y desde posiciones o campos de bits específicos. Los operadores aritméticos enteros también pueden realizar operaciones de bits en conjunto con los demás operadores.

En algunos casos, la manipulación de bits puede obviar o reducir la necesidad de iterar sobre una estructura de datos y puede proporcionar aceleraciones considerables, ya que las manipulaciones de bits se procesan en paralelo. Sin embargo, si la operación es inusual o costosa de implementar , su inclusión no se justifica, lo que inspira investigaciones innovadoras. ^{[ 1 ]}

Los términos "bit twiddling" , "bit fiddling" , "bit bashing" y "bit gymnastics" se utilizan a menudo indistintamente con "manipulación de bits", pero a veces se refieren exclusivamente a formas o usos ingeniosos o no obvios de la manipulación de bits, o a tareas tediosas o desafiantes de manipulación de datos de control de dispositivos de bajo nivel , para las cuales el término coloquial más preciso se conoce como "bit banging" .

El término "manipulación de bits" se remonta a los inicios del hardware informático , donde los operadores realizaban ajustes manipulando los controles de la computadora. A medida que evolucionaron los lenguajes de programación, los programadores adoptaron el término para referirse a cualquier manejo de datos que implicara computación a nivel de bits .

Una operación bit a bit opera sobre uno o más patrones de bits o números binarios a nivel de sus bits individuales . Es una acción rápida y básica, directamente compatible con la unidad central de procesamiento (CPU), y se utiliza para manipular valores con fines de comparación y cálculo.

En la mayoría de los procesadores, la mayoría de las operaciones bit a bit se ejecutan en un solo ciclo, lo que las hace considerablemente más rápidas que la división, la multiplicación y las bifurcaciones. Si bien los procesadores modernos suelen realizar algunas operaciones aritméticas y lógicas con la misma rapidez que las operaciones bit a bit debido a sus largas cadenas de instrucciones y otras decisiones de diseño arquitectónico , las operaciones bit a bit suelen consumir menos energía debido al menor uso de recursos.

Para determinar si un número es una potencia de dos, conceptualmente podemos dividir repetidamente el número entero entre dos hasta que el resultado no sea divisible por 2 de forma exacta; si el único factor restante es 1, el número original era una potencia de 2. Utilizando operadores lógicos y de bits, existe una expresión simple que devuelve verdadero (1) o falso (0):

bool isPowerOfTwo = ( x != 0 ) && (( x & ( x - 1 )) == 0 );

La segunda parte utiliza el hecho de que las potencias de dos tienen un único bit activado en su representación binaria:

x == 0...0 1 0...0 x-1 == 0...001...1 x & (x-1) == 0...000...0

Si el número no es ni cero ni una potencia de dos, tendrá un '1' en más de una posición:

x == 0... 1 ...0 1 0...0 x-1 == 0... 1 ...001...1 x & (x-1) == 0... 1 ...000...0

Si se utiliza código ensamblador en línea, podría estar disponible una instrucción ( popcnt ) que cuente la cantidad de 1 o 0 en el operando; un operando con exactamente un bit '1' es una potencia de 2. Sin embargo, dicha instrucción puede tener una latencia mayor que el método bit a bit descrito anteriormente.

Los procesadores suelen ofrecer solo un subconjunto de los operadores de bits útiles. Los lenguajes de programación no admiten directamente la mayoría de las operaciones de bits, por lo que se deben usar modismos para codificarlas. El lenguaje de programación C, por ejemplo, solo ofrece los operadores AND (&), OR (|), XOR (^) y NOT (~) a nivel de bits. Fortran ofrece AND (.and.), OR (.or.), XOR (.neqv.) y EQV (.eqv.). Cuando se proporciona el conjunto completo de operadores a nivel de bits, estos son funciones booleanas de dos o tres operandos.

Algol proporciona extracción e inserción sintáctica de campos de bits. Cuando los lenguajes ofrecen operaciones de bits que no se corresponden directamente con las instrucciones de hardware, los compiladores deben sintetizar la operación a partir de los operadores disponibles.

Una operación de bits especialmente útil es el conteo de ceros iniciales, que se utiliza para encontrar el bit más significativo de una palabra de máquina, aunque puede tener diferentes nombres en distintas arquitecturas. ^{[ 2 ]} No existe una sintaxis de lenguaje de programación sencilla, por lo que debe ser proporcionada por una función intrínseca del compilador o una rutina de la biblioteca del sistema. Sin ese operador, es muy costoso (véase Find first set#CLZ ) realizar cualquier operación con respecto al bit más significativo de una palabra, debido a la propagación asimétrica del acarreo en las operaciones aritméticas. Afortunadamente, la mayoría de las arquitecturas de CPU lo han proporcionado desde mediados de la década de 1980. Una operación complementaria, count ones , también llamada Popcount , que cuenta el número de bits establecidos en una palabra de máquina, también suele proporcionarse como un operador de hardware.

Las operaciones de bits más simples, como establecer, restablecer, probar y alternar bits, a menudo se proporcionan como operadores de hardware, pero se pueden simular fácilmente si no lo son; por ejemplo, (SET R0, 1; LSHFT R0, i; OR x, R0) establece el bit i en el operando x.

Algunas de las operaciones de bits más útiles y complejas que deben codificarse como modismos en el lenguaje de programación y ser sintetizadas por los compiladores incluyen:

• Borrar desde la posición de bit especificada hacia arriba (dejar la parte inferior de la palabra)
• Borrar desde la posición de bit especificada hacia abajo (dejar la parte superior de la palabra)
• máscara desde el bit inferior hacia abajo (palabra inferior clara)
• máscara desde el bit superior hacia arriba (palabra inferior clara)
• extracto de campo de bits
• inserción de campo de bits
• Operaciones de dispersión/recopilación de campos de bits que distribuyen porciones contiguas de un campo de bits sobre una palabra de máquina, o recopilan campos de bits dispares dentro de la palabra en una porción contigua de un campo de bits (véanse los operadores recientes Intel PEXT/PDEP). Se utilizan en criptografía y codificación de vídeo.
• inversión de matriz

Algunas operaciones aritméticas se pueden reducir a operaciones más simples y a operaciones de bits:

• reducir multiplicar por constante a secuencia de desplazamiento-suma

Por ejemplo, multiplicar por 9 es copiar el operando, desplazarlo 3 posiciones hacia arriba (multiplicarlo por 8) y sumarlo al operando original.

• Reducir la división por constante a una secuencia de desplazamiento-resta

La inversión de bits, la inversión de bytes y las diversas formas de rotación pueden resultar costosas en términos del número de instrucciones necesarias. El desplazamiento tiene variantes, como el desplazamiento aritmético, el desplazamiento lógico y la rotación.

Entre las instrucciones poco comunes se incluyen las instrucciones Packed BCD , que son muy frecuentes en los sectores financiero, comercial e industrial.

• Warren, Henry S. (2013). Hacker's Delight (2.ª  ed.). Addison–Wesley Professional. p.  512. ISBN 978-0321842688.
• Knuth, Donald E. (2009). El arte de la programación informática, volumen 4, fascículo 1: Trucos y técnicas bit a bit; diagramas de decisión binarios (1.ª  ed.). Addison–Wesley Professional. pág.  272. ISBN 978-0321580504.( Borrador del fascículo 1a archivado el 16/10/2019 en Wayback Machine, disponible para su descarga)

• Anderson, Sean Eron, ed. (26 de noviembre de 2009) [1997]. "Trucos de manipulación de bits" . Universidad de Stanford . Archivado del original el 1 de junio de 2020. Recuperado el 1 de junio de 2020 .
• Trucos de manipulación de bits con explicaciones completas y código fuente.
• Guía de Intel Intrinsics
• xchg rax, rax : acertijos y trucos para x86_64
• The Aggregate Magic Algorithms from University of Kentucky