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 el 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 algún número entero no negativo. Si w no divide el número de bits a almacenar, se desperdicia algo de espacio debido a la fragmentación interna .
Una matriz de bits es una asignación de algún dominio (casi siempre un rango de números enteros) a valores del conjunto {0, 1}. Los valores se pueden interpretar como oscuro/claro, ausente/presente, bloqueado/desbloqueado, válido/inválido, etc. La cuestión es que sólo 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 1 bit indica el presencia y un bit 0 la ausencia de un número en el conjunto. Esta estructura de datos establecida utiliza aproximadamente n / w palabras de espacio, donde w es el número de bits en cada palabra de máquina . Si el bit menos significativo (de la palabra) o el bit más significativo indica el número de índice más pequeño es en gran medida irrelevante, pero el primero tiende a ser el preferido (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 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 de una palabra se puede seleccionar y manipular mediante operaciones bit a bit . En particular:
Úselo 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 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 poco:
11101 0 10 11101 1 10XOR 00000 1 00 XOR 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 el número adecuado 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 usando n / w operaciones de bits simples cada una (2 n / w para diferencia), así como el complemento de cualquiera de ellas:
para i de 0 a n/w-1 complemento_a[i] := no un[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 iterar a través de los bits de una matriz de bits, podemos hacerlo de manera eficiente usando un bucle doblemente anidado que recorra cada palabra, una a la vez. Sólo se requieren n / w accesos a 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 exhiben 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 / semanas de errores de caché.
Al igual que con las cadenas de caracteres, es sencillo definir longitud , subcadena , comparación lexicográfica , concatenación y operaciones inversas . La implementación de algunas de estas operaciones es sensible a la endianidad .
Si deseamos encontrar el número de bits 1 en una matriz de bits, a veces llamado recuento de población o peso de Hamming, existen algoritmos eficientes sin ramificaciones que pueden calcular el número de bits en una palabra usando una serie de operaciones de bits simples. Simplemente ejecutamos dicho algoritmo en cada palabra y mantenemos un total acumulado. Contar ceros es similar. Consulte el artículo sobre el peso de Hamming para ver ejemplos de una implementación eficiente.
La inversión vertical de una imagen de un bit por píxel, o algunos algoritmos FFT, requiere invertir los bits de palabras individuales (así b31 b30 ... b0es b0 ... b30 b31). Cuando esta operación no está disponible en el procesador, aún es posible realizar pasadas sucesivas, en este ejemplo de 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 buscar el primer conjunto o buscar el primero identifica el índice o la posición del bit con el índice más pequeño en una matriz, y tiene soporte de hardware generalizado (para matrices que no sean más grandes 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 buscar primero para identificar el elemento de mayor prioridad en la cola. Para expandir un tamaño de palabra, buscar primero a matrices más largas, se puede encontrar la primera palabra distinta de cero y luego ejecutar buscar el primero en esa palabra. Las operaciones relacionadas encontrar el primer cero , contar ceros a la izquierda , contar unos a la izquierda , contar ceros a la derecha , contar unos a la derecha y registrar la base 2 (consulte encontrar el primer conjunto ) también se pueden extender a una matriz de bits de manera sencilla.
Una matriz de bits es el almacenamiento más denso para bits "aleatorios", es decir, donde es igualmente probable que cada bit sea 0 o 1, y cada uno es independiente. Pero la mayoría de los datos no son aleatorios, por lo que es 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 de longitud de ejecución se usa comúnmente para comprimir estas secuencias largas. Sin embargo, no es tan fácil acceder a la mayoría de los formatos de datos comprimidos de forma aleatoria; Además, al comprimir matrices de bits de manera 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 matrices de bits como flujos de bits, podríamos comprimirlos 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 marcadas ventajas 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 tamaño compacto, las matrices de bits tienen numerosas aplicaciones en áreas donde el espacio o la eficiencia son escasos. 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 sólo si k está en la cola; esta estructura de datos es utilizada, por ejemplo, por el kernel de Linux y se beneficia enormemente de una operación de búsqueda del primero 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 frecuentemente 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 de conjuntos probabilísticos 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 sobre ellas también son importantes para construir estructuras de datos concisas , que utilizan casi el mínimo espacio posible. En este contexto, operaciones como encontrar el n.ésimo 1 bit o contar el número de 1 bits hasta una determinada posición se vuelven importantes.
Las matrices de bits también son una abstracción útil para examinar flujos 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 de codificación Huffman comprimida de un único 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 de 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 usando codificación unaria , el resultado es una matriz de bits con 1 bit en la n -ésima posición si y solo si n está en la lista. La probabilidad implícita de una brecha de n es 1/2 n . Este es también el caso especial de la codificación Golomb donde el parámetro M es 1; este parámetro normalmente solo se selecciona 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 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 densamente 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 operan utilizando un algoritmo de caso especial, como la suma de los bits mediante una búsqueda de bytes en una tabla. .
Los campos de bits del lenguaje de programación C , pseudoobjetos que se encuentran en estructuras con un tamaño igual a una cierta cantidad de bits, son en realidad pequeñas matrices de bits; están limitados porque no pueden abarcar palabras. Aunque brindan una sintaxis conveniente, todavía se accede a los bits mediante operadores byte a byte en la mayoría de las máquinas, y solo se pueden definir estáticamente (como las matrices estáticas de C, sus tamaños se fijan en tiempo de compilación). También es un modismo común entre los programadores de C usar palabras como pequeñas matrices de bits y acceder a sus bits 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 del campo de bits de matrices de bits". Puede encontrar una descripción más explicativa del enfoque antes mencionado en las preguntas frecuentes de comp.lang.c.
En C++ , aunque los mensajes de correo electrónico individuales boolsuelen ocupar el mismo espacio que un byte o un número 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 de proxy . Esto puede parecer un punto menor, pero significa que novector<bool> es un contenedor STL estándar, por lo que generalmente se desaconseja su uso . Otra clase STL única, [ 3] crea un vector de bits fijados en un tamaño particular en tiempo de compilación, y en su interfaz y sintaxis se parece más al uso idiomático de palabras como conjuntos de bits por parte de los programadores de C. También tiene alguna potencia adicional, como la capacidad de contar de manera eficiente la cantidad de bits configurados. 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 formato std.bitmanip. Como 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 archivo 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 familiares para los programadores de C. A diferencia bitsetde C++, Java BitSetno tiene un estado de "tamaño" (tiene un tamaño efectivamente infinito, inicializado con 0 bits); un bit se puede configurar o probar en cualquier índice. Además, existe 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. Almacena bits utilizando 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 y su Lengthpropiedad se puede cambiar para hacerla crecer o truncarla.
Aunque Standard ML no admite matrices de bits, Standard ML de Nueva 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, inusualmente, operaciones de desplazamiento.
Haskell también carece actualmente de soporte estándar para operaciones bit a bit, pero tanto GHC como Hugs proporcionan un Data.Bitsmódulo con una variedad de funciones y operadores bit a bit, incluidas operaciones de desplazamiento y rotación, y se puede usar una matriz "sin caja" sobre valores booleanos para modelar una matriz de bits, aunque esto Carece de soporte del módulo anterior.
En Perl , las cadenas se pueden utilizar como matrices de bits ampliables. Se pueden manipular utilizando los operadores bit a bit habituales ( ~ | & ^), [6] y los bits individuales se pueden probar y configurar utilizando la función vec . [7]
En Ruby , puedes acceder (pero no configurar) un bit de un número entero ( Fixnumo Bignum) usando el operador de corchetes ( []), 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 ser de longitud fija o variable. Los elementos de la matriz pueden estar alineados (cada elemento comienza en un byte o límite de palabra) o no alineados (los elementos se suceden inmediatamente entre sí sin relleno).
PL/pgSQL y SQL de PostgreSQL admiten cadenas de bits como tipo nativo. Hay dos tipos de bits SQL: y , donde es un número 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 incorporado array, actuando en una doble capacidad como especificador de clase y tipo. [9] Al ser un derivado de la matriz, se basa en que la make-arrayfunción general se configure con un tipo de elemento de bit, que opcionalmente permite designar el vector de bits como dinámicamente redimensionable. El bit-vector, sin embargo, no es infinito en extensión. Existe un tipo más restringido simple-bit-vector, que excluye explícitamente las características dinámicas. [10] Los vectores de bits se representan y pueden construirse de una manera más concisa mediante la macro del lector . [11] Además de las funciones generales aplicables a todas las matrices, existen operaciones dedicadas para vectores de bits. Se puede acceder y modificar bits individuales utilizando las funciones y [12] y se admite una gran cantidad de operaciones lógicas. [13]#*bitsbitsbit