Una matriz de bits (también conocida como máscara de bits , [1] mapa de bits , conjunto de bits , cadena de bits o vector de bits ) es una estructura de datos de matriz que almacena bits de forma compacta . Se puede utilizar para implementar una estructura de datos de conjunto simple . Una matriz de bits es eficaz para explotar el paralelismo a nivel de bits en hardware para realizar operaciones rápidamente. Una matriz de bits típica almacena kw bits, donde w es el número de bits en la unidad de almacenamiento, como un byte o una palabra , y k es un entero no negativo. Si w no divide el número de bits que se almacenarán, se desperdicia algo de espacio debido a la fragmentación interna .
Una matriz de bits es una asignación de un dominio (casi siempre un rango de números enteros) a valores en el conjunto {0, 1}. Los valores se pueden interpretar como oscuro/claro, ausente/presente, bloqueado/desbloqueado, válido/inválido, etcétera. El punto es que solo hay dos valores posibles, por lo que se pueden almacenar en un bit. Al igual que con otras matrices, el acceso a un solo bit se puede gestionar aplicando un índice a la matriz. Suponiendo que su tamaño (o longitud) sea de n bits, la matriz se puede utilizar para especificar un subconjunto del dominio (por ejemplo, {0, 1, 2, ..., n −1}), donde un bit 1 indica la presencia y un bit 0 la ausencia de un número en el conjunto. Esta estructura de datos de conjunto utiliza aproximadamente n / w palabras de espacio, donde w es el número de bits en cada palabra de máquina . No importa en gran medida si el bit menos significativo (de la palabra) o el bit más significativo indica el número de índice más pequeño, pero se tiende a preferir el primero (en máquinas little-endian ).
Una relación binaria finita puede representarse mediante una matriz de bits llamada matriz lógica . En el cálculo de relaciones , estas matrices se componen con la multiplicación de matrices donde la aritmética es booleana, y dicha composición representa la composición de relaciones . [2]
Aunque la mayoría de las máquinas no pueden direccionar bits individuales en la memoria ni tienen instrucciones para manipular bits individuales, cada bit en una palabra puede ser seleccionado y manipulado usando operaciones bit a bit . En particular:
Se utiliza ORpara establecer un bit en uno:
11101 0 10O 00000 1 00 = 11101 1 10
ANDPara poner un bit a cero:
111010 1 0Y 111111 0 1 = 111010 0 0
ANDPara determinar si un bit está establecido, mediante una prueba de cero:
1110101 0 111010 1 0 Y 0000000 1 Y 000000 1 0 = 0000000 0 = 000000 1 0(=0 ∴ el bit no está establecido) (≠0 ∴ el bit está establecido)
XORPara invertir o alternar un bit:
11101 0 10 11101 1 10O 00000 1 00 O 00000 1 00 = 11101 1 10 = 11101 0 10
NOTPara invertir todos los bits:
NO 10110010 = 01001101
Para obtener la máscara de bits necesaria para estas operaciones, podemos utilizar un operador de desplazamiento de bits para desplazar el número 1 hacia la izquierda la cantidad adecuada de lugares, así como la negación bit a bit si es necesario.
Dadas dos matrices de bits del mismo tamaño que representan conjuntos, podemos calcular su unión , intersección y diferencia teórica de conjuntos utilizando n / w operaciones de bits simples cada una (2 n / w para la diferencia), así como el complemento de cualquiera de los dos:
para i de 0 a n/w-1 complemento_a[i] := no a[i] unión[i] := a[i] o b[i] intersección[i] := a[i] y b[i] diferencia[i] := a[i] y ( no b[i])
Si deseamos recorrer los bits de una matriz de bits, podemos hacerlo de manera eficiente mediante un bucle doblemente anidado que recorra cada palabra, una a la vez. Solo se requieren n / w accesos a la memoria:
para i de 0 a n/w-1 índice := 0 // si es necesario palabra := a[i] para b de 0 a w-1 valor := palabra y 1 ≠ 0 palabra := palabra desplazada a la derecha 1 // hacer algo con valor índice := índice + 1 // si es necesario
Ambos ejemplos de código muestran una localidad de referencia ideal , que posteriormente recibirá un gran aumento de rendimiento de un caché de datos. Si una línea de caché tiene k palabras, solo se producirán aproximadamente n / semana de errores de caché.
Al igual que con las cadenas de caracteres, es sencillo definir operaciones de longitud , subcadena , comparación lexicográfica , concatenación e inversión . La implementación de algunas de estas operaciones es sensible al orden de bytes .
Si deseamos encontrar la cantidad de bits 1 en una matriz de bits, a veces llamada recuento de población o ponderación de Hamming, existen algoritmos eficientes sin ramificaciones que pueden calcular la cantidad de bits en una palabra mediante una serie de operaciones de bits simples. Simplemente ejecutamos un algoritmo de este tipo en cada palabra y llevamos un total acumulado. Contar ceros es similar. Consulte el artículo sobre la ponderación de Hamming para ver ejemplos de una implementación eficiente.
El volteo vertical de una imagen de un bit por píxel, o algunos algoritmos FFT, requieren voltear los bits de palabras individuales (por lo que b31 b30 ... b0se convierte en b0 ... b30 b31). Cuando esta operación no está disponible en el procesador, aún es posible proceder mediante pasadas sucesivas, en este ejemplo en 32 bits:
intercambiar dos medias palabras de 16 bitsintercambiar bytes por pares (0xddccbbaa -> 0xccddaabb)...intercambiar bits por paresintercambiar bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)La última operación se puede escribir ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)).La operación de búsqueda del primer conjunto o búsqueda del primer uno identifica el índice o la posición del bit 1 con el índice más pequeño en una matriz, y tiene un amplio soporte de hardware (para matrices no mayores que una palabra) y algoritmos eficientes para su cálculo. Cuando una cola de prioridad se almacena en una matriz de bits, se puede utilizar la operación de búsqueda del primer uno para identificar el elemento de mayor prioridad en la cola. Para expandir una operación de búsqueda del primer uno del tamaño de una palabra a matrices más largas, se puede encontrar la primera palabra distinta de cero y luego ejecutar la operación de búsqueda del primer uno en esa palabra. Las operaciones relacionadas búsqueda del primer cero , contar los ceros iniciales , contar los unos iniciales , contar los ceros finales , contar los unos finales y el logaritmo en base 2 (consulte la operación de búsqueda del primer conjunto ) también se pueden extender a una matriz de bits de una manera sencilla.
Una matriz de bits es el almacenamiento más denso para bits "aleatorios", es decir, donde cada bit tiene la misma probabilidad de ser 0 o 1, y cada uno es independiente. Pero la mayoría de los datos no son aleatorios, por lo que puede ser posible almacenarlos de forma más compacta. Por ejemplo, los datos de una imagen de fax típica no son aleatorios y se pueden comprimir. La codificación por longitud de ejecución se utiliza comúnmente para comprimir estos flujos largos. Sin embargo, la mayoría de los formatos de datos comprimidos no son tan fáciles de acceder de forma aleatoria; también al comprimir las matrices de bits de forma demasiado agresiva corremos el riesgo de perder los beneficios debido al paralelismo a nivel de bits ( vectorización ). Por lo tanto, en lugar de comprimir las matrices de bits como flujos de bits, podríamos comprimirlas como flujos de bytes o palabras (consulte Índice de mapa de bits (compresión) ).
Las matrices de bits, a pesar de su simplicidad, tienen una serie de ventajas marcadas sobre otras estructuras de datos para los mismos problemas:
Sin embargo, las matrices de bits no son la solución para todo. En particular:
Debido a su compacidad, las matrices de bits tienen diversas aplicaciones en áreas donde el espacio o la eficiencia son importantes. Por lo general, se utilizan para representar un grupo simple de indicadores booleanos o una secuencia ordenada de valores booleanos.
Las matrices de bits se utilizan para colas de prioridad , donde el bit en el índice k se establece si y solo si k está en la cola; esta estructura de datos es utilizada, por ejemplo, por el kernel de Linux , y se beneficia en gran medida de una operación de búsqueda del primer cero en el hardware.
Las matrices de bits se pueden utilizar para la asignación de páginas de memoria , inodos , sectores de disco, etc. En tales casos, se puede utilizar el término mapa de bits . Sin embargo, este término se utiliza con frecuencia para referirse a imágenes rasterizadas , que pueden utilizar varios bits por píxel .
Otra aplicación de las matrices de bits es el filtro Bloom , una estructura de datos probabilística que puede almacenar conjuntos grandes en un espacio pequeño a cambio de una pequeña probabilidad de error. También es posible construir tablas hash probabilísticas basadas en matrices de bits que aceptan falsos positivos o falsos negativos.
Las matrices de bits y las operaciones que se realizan con ellas también son importantes para construir estructuras de datos concisas que utilicen el mínimo espacio posible. En este contexto, operaciones como encontrar el n -ésimo bit 1 o contar la cantidad de bits 1 hasta una determinada posición se vuelven importantes.
Las matrices de bits también son una abstracción útil para examinar secuencias de datos comprimidos , que a menudo contienen elementos que ocupan porciones de bytes o no están alineados en bytes. Por ejemplo, la representación comprimida de la codificación Huffman de un solo carácter de 8 bits puede tener una longitud de entre 1 y 255 bits.
En la recuperación de información , las matrices de bits son una buena representación para las listas de publicación de términos muy frecuentes. Si calculamos los espacios entre valores adyacentes en una lista de números enteros estrictamente crecientes y los codificamos utilizando codificación unaria , el resultado es una matriz de bits con un bit 1 en la posición n si y solo si n está en la lista. La probabilidad implícita de un espacio de n es 1/2 n . Este también es el caso especial de la codificación de Golomb donde el parámetro M es 1; este parámetro solo se selecciona normalmente cuando −log(2 − p ) / log(1 − p ) ≤ 1 , o aproximadamente el término aparece en al menos el 38% de los documentos.
El lenguaje de programación APL admite completamente matrices de bits de forma y tamaño arbitrarios como un tipo de datos booleano distinto de los números enteros. Todas las implementaciones principales ( Dyalog APL, APL2, APL Next, NARS2000, Gnu APL , etc.) empaquetan los bits de manera densa en cualquier tamaño que tenga la palabra de máquina. Se puede acceder a los bits individualmente a través de la notación de indexación habitual (A[3]), así como a través de todas las funciones y operadores primitivos habituales, donde a menudo se opera sobre ellos utilizando un algoritmo de caso especial, como la suma de los bits a través de una búsqueda de bytes en una tabla.
Los campos de bits del lenguaje de programación C , pseudo-objetos que se encuentran en estructuras con un tamaño igual a una cierta cantidad de bits, son de hecho pequeñas matrices de bits; están limitadas en el sentido de que no pueden abarcar palabras. Aunque brindan una sintaxis conveniente, los bits aún se acceden mediante operadores byte a byte en la mayoría de las máquinas, y solo se pueden definir de forma estática (al igual que las matrices estáticas de C, sus tamaños se fijan en tiempo de compilación). También es un modismo común para los programadores de C usar palabras como pequeñas matrices de bits y acceder a bits de ellas mediante operadores de bits. Un archivo de encabezado ampliamente disponible incluido en el sistema X11 , xtrapbits.h, es "una forma portátil para que los sistemas definan la manipulación de campos de bits de matrices de bits". Se puede encontrar una descripción más explicativa del enfoque mencionado anteriormente en las preguntas frecuentes de comp.lang.c.
En C++ , aunque los s individuales boolsuelen ocupar el mismo espacio que un byte o un entero, el tipo STLvector<bool> es una especialización de plantilla parcial en la que los bits se empaquetan como una optimización de la eficiencia del espacio. Dado que los bytes (y no los bits) son la unidad direccionable más pequeña en C++, el operador [] no devuelve una referencia a un elemento, sino que devuelve una referencia proxy . Esto puede parecer un punto menor, pero significa que novector<bool> es un contenedor STL estándar, por lo que generalmente se desaconseja el uso de . Otra clase STL única, , [3] crea un vector de bits fijado en un tamaño particular en tiempo de compilación, y en su interfaz y sintaxis se asemeja más al uso idiomático de palabras como conjuntos de bits por parte de los programadores de C. También tiene algo de poder adicional, como la capacidad de contar de manera eficiente la cantidad de bits que se establecen. Las bibliotecas Boost C++ proporcionan una clase [4] cuyo tamaño se especifica en tiempo de ejecución.vector<bool>bitsetdynamic_bitset
El lenguaje de programación D proporciona matrices de bits en su biblioteca estándar, Phobos, en std.bitmanip. Al igual que en C++, el operador [] no devuelve una referencia, ya que los bits individuales no son direccionables directamente en la mayoría del hardware, sino que devuelve un bool.
En Java , la clase BitSetcrea una matriz de bits que luego se manipula con funciones que llevan el nombre de operadores bit a bit que son familiares para los programadores de C. A diferencia de bitseten C++, Java BitSetno tiene un estado de "tamaño" (tiene un tamaño efectivamente infinito, inicializado con 0 bits); un bit se puede establecer o probar en cualquier índice. Además, hay una clase EnumSetque representa un conjunto de valores de un tipo enumerado internamente como un vector de bits, como una alternativa más segura a los campos de bits.
.NET Framework proporciona una BitArrayclase de colección que almacena bits mediante una matriz de tipo int(cada elemento de la matriz suele representar 32 bits). [5] La clase admite acceso aleatorio y operadores bit a bit, se puede iterar sobre ella y se pueden modificar sus Lengthpropiedades para hacerla crecer o truncarla.
Aunque Standard ML no admite matrices de bits, Standard ML of New Jersey tiene una extensión, la BitArrayestructura, en su biblioteca SML/NJ. No tiene un tamaño fijo y admite operaciones de conjuntos y operaciones de bits, incluidas, de manera inusual, operaciones de desplazamiento.
Asimismo, Haskell actualmente carece de soporte estándar para operaciones bit a bit, pero tanto GHC como Hugs proporcionan un Data.Bitsmódulo con diversas funciones y operadores bit a bit, incluyendo operaciones de desplazamiento y rotación, y una matriz "sin encapsular" sobre valores booleanos que se puede usar para modelar una matriz Bit, aunque esto carece del soporte del módulo anterior.
En Perl , las cadenas se pueden utilizar como matrices de bits expandibles. Se pueden manipular utilizando los operadores bit a bit habituales ( ~ | & ^), [6] y se pueden probar y configurar bits individuales utilizando la función vec . [7]
En Ruby , puedes acceder (pero no configurar) a un bit de un entero ( Fixnumo Bignum) usando el operador de corchete ( []), como si fuera una matriz de bits.
La biblioteca Core Foundation de Apple contiene estructuras CFBitVector y CFMutableBitVector.
PL/I admite matrices de cadenas de bits de longitud arbitraria, que pueden tener una longitud fija o variable. Los elementos de la matriz pueden estar alineados (cada elemento comienza en un byte o en el límite de una palabra) o no alineados (los elementos se suceden inmediatamente sin relleno).
El soporte SQL de PL/pgSQL y PostgreSQL admite cadenas de bits como tipo nativo. Existen dos tipos de bits SQL: y , donde es un entero positivo. [8]bit(n)bit varying(n)n
Los lenguajes de descripción de hardware como VHDL , Verilog y SystemVerilog admiten de forma nativa vectores de bits, ya que se utilizan para modelar elementos de almacenamiento como flip-flops , buses de hardware y señales de hardware en general. En lenguajes de verificación de hardware como OpenVera, e y SystemVerilog , los vectores de bits se utilizan para muestrear valores de los modelos de hardware y para representar datos que se transfieren al hardware durante las simulaciones.
Common Lisp proporciona una implementación unidimensional bit-vectorcomo un caso especial del array, que actúa en una capacidad dual como una clase y un especificador de tipo. [9] Al ser un derivado de la matriz, se basa en la make-arrayfunción general que se configurará con un tipo de elemento de bit, que opcionalmente permite que el vector de bits se designe como redimensionable dinámicamente. bit-vectorSin embargo, el , no es infinito en extensión. simple-bit-vectorExiste un tipo más restringido, que excluye explícitamente las características dinámicas. [10] Los vectores de bits se representan como, y pueden construirse de una manera más concisa mediante, la macro de lectura . [11] Además de las funciones generales aplicables a todas las matrices, existen operaciones dedicadas para vectores de bits. Se puede acceder a bits individuales y modificarlos utilizando las funciones y [12] y se admite una gran cantidad de operaciones lógicas. [13]#*bitsbitsbit