Matriz de bits

Un arreglo de bits (también conocido como mapa de bits , conjunto de bits , cadena de bits o vector de bits ) es una estructura de datos de arreglo que almacena bits de forma compacta . Se puede utilizar para implementar una estructura de datos de conjunto simple . Un arreglo de bits es eficaz para aprovechar el paralelismo a nivel de bits en el hardware para realizar operaciones rápidamente. Un arreglo de bits típico 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 positivo. Si w no divide el número de bits a almacenar, se desperdicia espacio debido a la fragmentación interna .

Una matriz de bits es una asignación de algún dominio (casi siempre un rango de enteros) a valores en el conjunto.${\displaystyle \{{\texttt {0}},{\texttt {1}}\}}$Los valores se pueden interpretar como oscuro/claro, ausente/presente, bloqueado/desbloqueado, válido/inválido, etcétera. La cuestión es que solo hay dos valores posibles, por lo que se pueden almacenar en un bit. Al igual que con otros arreglos, el acceso a un solo bit se puede gestionar aplicando un índice al arreglo. Suponiendo que su tamaño (o longitud) sea de n bits, el arreglo se puede utilizar para especificar un subconjunto del dominio (por ejemplo,${\displaystyle \{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 la máquina . Que el bit menos significativo (de la palabra) o el bit más significativo indique el índice más pequeño es en gran medida irrelevante, pero se suele preferir el primero (en máquinas little-endian ).

Una relación binaria finita puede representarse mediante una matriz de bits denominada matriz lógica . En el cálculo de relaciones , estas matrices se componen mediante multiplicación de matrices, donde la aritmética es booleana, y dicha composición representa la composición de relaciones . ^{[ 1 ]}

Aunque la mayoría de las máquinas no pueden acceder a bits individuales en la memoria, ni tienen instrucciones para manipular bits individuales, cada bit en una palabra puede ser seleccionado y manipulado mediante operaciones bit a bit . En particular:

Se utiliza ORpara establecer un bit a uno:

 11101 0 10 O 00000 1 00 = 11101 1 10

ANDPara poner un bit a cero:

 111010 1 0 Y 111111 0 1 = 111010 0 0

ANDPara determinar si un bit está activado, mediante una prueba de cero:

 1110101 0 Y 0000000 1 = 0000000 0 (0 significa que el bit no está activado) 111010 1 0 Y 000000 1 0 = 000000 1 0 (un valor distinto de cero significa que el bit está activado)

XORpara invertir o alternar un poco:

 11101 0 10 XOR 00000 1 00 = 11101 1 10 11101 1 10 XOR 00000 1 00 = 11101 0 10

NOTInvertir todos los bits:

NO 10110010 = 01001101

Para obtener la máscara de bits necesaria para estas operaciones, podemos usar un operador de desplazamiento de bits para desplazar el número 1 a la izquierda el número de posiciones apropiado, así como la negación bit a bit si fuera necesario.

Dados dos arreglos 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 uno (2n / w para la diferencia), así como el complemento de cualquiera de ellos:

para i desde 0 hasta 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 iterar a través de los bits de una matriz de bits, podemos hacerlo de manera eficiente utilizando un bucle doblemente anidado que recorre cada palabra, una a la vez. Solo se requieren n / w accesos a la memoria:

para i desde 0 hasta n/w-1 índice := 0 // si es necesario palabra := a[i] para b desde 0 hasta w-1 valor := palabra y 1 ≠ 0 palabra := palabra desplazar a la derecha 1 // hacer algo con el valor índice := índice + 1 // si es necesario

Ambos ejemplos de código muestran una localidad de referencia ideal , lo que posteriormente se traduce en una gran mejora del rendimiento gracias a una caché de datos. Si una línea de caché tiene k palabras, solo se producirán aproximadamente n / wk fallos 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 (endianness) .

intercambiar dos medias palabras de 16 bits Intercambiar bytes por pares (0xddccbbaa -> 0xccddaabb) ... Intercambiar bits por pares Intercambiar bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1) La última operación se puede escribir como ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)). 

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 de longitud de ejecución se usa comúnmente para comprimir estas largas secuencias. Sin embargo, la mayoría de los formatos de datos comprimidos no son tan fáciles de acceder aleatoriamente; además, al comprimir 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 matrices de bits como secuencias de bits, podríamos comprimirlas como secuencias de bytes o palabras (ver Índice de mapas de bits (compresión) ).

Los arreglos de bits, a pesar de su simplicidad, tienen una serie de ventajas notables sobre otras estructuras de datos para los mismos problemas:

• Son extremadamente compactas; ninguna otra estructura de datos puede almacenar n piezas de datos independientes en n / w palabras.
• Permiten almacenar y manipular pequeños conjuntos de bits en el conjunto de registros durante largos períodos de tiempo sin necesidad de acceder a la memoria.
• Gracias a su capacidad para aprovechar el paralelismo a nivel de bits, limitar el acceso a la memoria y utilizar al máximo la caché de datos , a menudo superan a muchas otras estructuras de datos en conjuntos de datos prácticos, incluso a aquellas que son asintóticamente más eficientes.

Sin embargo, las matrices de bits no son la solución a todo. En particular:

• Sin compresión, las estructuras de datos de conjuntos resultan ineficientes en términos de tiempo y espacio para conjuntos dispersos (aquellos con pocos elementos en comparación con su rango). Para este tipo de aplicaciones, conviene considerar matrices de bits comprimidas, matrices Judy , árboles de búsqueda o incluso filtros de Bloom .
• El acceso a elementos individuales puede ser costoso y difícil de expresar en algunos lenguajes. Si el acceso aleatorio es más común que el secuencial y el array es relativamente pequeño, un array de bytes puede ser preferible en una máquina con direccionamiento por bytes. Sin embargo, un array de palabras probablemente no se justifique debido al enorme consumo de espacio y a los fallos de caché adicionales que provoca, a menos que la máquina solo tenga direccionamiento por palabras.

Debido a su compacidad, las matrices de bits tienen diversas aplicaciones en áreas donde el espacio o la eficiencia son factores críticos. Generalmente, se utilizan para representar un grupo simple de indicadores booleanos o una secuencia ordenada de valores booleanos.

Los arreglos de bits se utilizan para colas de prioridad , donde el bit en el índice k se activa 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 enormemente 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 estos casos, se suele usar el término mapa de bits . Sin embargo, este término se usa con frecuencia para referirse a imágenes rasterizadas , que pueden usar varios bits por píxel .

Otra aplicación de los arreglos de bits es el filtro de Bloom , una estructura de datos de conjuntos probabilísticos que permite almacenar grandes conjuntos en un espacio reducido a cambio de una baja probabilidad de error. También es posible construir tablas hash probabilísticas basadas en arreglos de bits que aceptan tanto falsos positivos como falsos negativos.

Los arreglos de bits y las operaciones que se realizan sobre ellos también son importantes para construir estructuras de datos concisas , que utilizan el mínimo espacio posible. En este contexto, operaciones como encontrar el enésimo bit 1 o contar la cantidad de bits 1 hasta una posición determinada cobran importancia.

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 que no están alineados a bytes. Por ejemplo, la representación comprimida en 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 términos muy frecuentes. Si calculamos los intervalos entre valores adyacentes en una lista de enteros estrictamente crecientes y los codificamos usando 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 intervalo de n es 1/2 ⁿ . Este es también el caso especial de la codificación de 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.

Dado un archivo grande de direcciones IPv4 (más de 100 GB), necesitamos contar las direcciones únicas. Si usamos genéricos map[string]bool, necesitaremos más de 64 GB de RAM , por lo que usamos el mapa de bits en Go :

paquete principalimportar ("bufio""fmt""matemáticas/bits""os")// bitsetSize es el número de bytes necesarios para 2^32 bits (512 MiB)const bitsetSize = 1 << 29función principal () {archivo , error := os.Open ( " ip_addresses " )si err != nil {fmt.Println ( "Error al abrir el archivo: " , err )devolver}aplazar archivo . Cerrar ()conjunto de bits : = [ tamaño de conjunto de bits ] byte {}// Utilizar un escáner con búfer con un búfer más grandeescáner := bufio . NuevoEscáner ( archivo )const maxBuffer = 64 * 1024 // búfer de 64 KBbuf := make ([] byte , 0 , maxBuffer )escáner.Buffer ( buf , maxBuffer )​​// Procesar cada líneapara escáner . Escanear () {línea : = escáner.Bytes ( )// Analizar manualmente la dirección IP a partir de los bytesip := parseIPv4 ( línea )// Establecer el bitbyteIndex := ip >> 3 // Dividir por 8bitIndex := ip & 7 // Posición del bit 0-7bitset [ byteIndex ] |= 1 << bitIndex}// Comprobar si hay errores de escaneoif err := scanner . Err (); err != nil {fmt.Println ( "Error al leer el archivo : " , err )devolver}var count uint64para yo : = 0 ; i < tamaño de conjunto de bits ; yo ++ {contar += uint64 ( bits . OnesCount8 ( conjunto de bits [ i ]))}fmt.Println ( "Número de direcciones IPv4 únicas : " , count )}func parseIPv4 ( línea [] byte ) ( ip uint32 ) {i := 0// Octeto 1n := uint32 ( línea [ i ] - '0' )para i = 1 ; línea [ i ] != '.' ; i ++ {n = n * 10 + uint32 ( línea [ i ] - '0' )}ip |= n << 24i ++ // Saltar el punto// Octeto 2n = uint32 ( línea [ i ] - '0' )yo ++para ; línea [ i ] != '.' ; i ++ {n = n * 10 + uint32 ( línea [ i ] - '0' )}ip |= n << 16i ++ // Saltar el punto// Octeto 3n = uint32 ( línea [ i ] - '0' )yo ++para ; línea [ i ] != '.' ; i ++ {n = n * 10 + uint32 ( línea [ i ] - '0' )}ip |= n << 8i ++ // Saltar el punto// Octeto 4n = uint32 ( línea [ i ] - '0' )yo ++para ; i < len ( línea ); i ++ {n = n * 10 + uint32 ( línea [ i ] - '0' )}ip |= ndevolver IP}

Los lenguajes de programación admiten ampliamente las matrices de bits, ya sea a través de interfaces específicas o mediante capacidades más generales de manipulación de bits.

El lenguaje de programación APL admite completamente matrices de bits de forma y tamaño arbitrarios como un tipo de dato booleano distinto de los enteros. Todas las implementaciones principales ( Dyalog APL, APL2, APL Next, NARS2000, Gnu APL , etc.) empaquetan los bits de forma densa en el tamaño de la palabra de máquina. Se puede acceder a los bits individualmente mediante la notación de indexación habitual (por ejemplo, A[3]) así como a través de todas las funciones y operadores primitivos habituales, donde a menudo se realizan operaciones con ellos utilizando un algoritmo de caso especial, como la suma de los bits mediante una búsqueda en una tabla de bytes.

Los campos de bits del lenguaje de programación C , pseudoobjetos que se encuentran en estructuras con un tamaño igual a un número determinado de bits, son en realidad pequeños arreglos de bits; su limitación radica en que no pueden abarcar palabras. Aunque ofrecen una sintaxis conveniente, en la mayoría de las máquinas se sigue accediendo a los bits mediante operadores byte a byte, y solo se pueden definir de forma estática (al igual que los arreglos estáticos de C, sus tamaños se fijan en tiempo de compilación). También es una práctica común entre los programadores de C usar palabras como pequeños arreglos de bits y acceder a sus bits mediante operadores de bits. Un archivo de cabecera ampliamente disponible incluido en el sistema X11 , , es "una forma portátil para que los sistemas definan la manipulación de campos de bits de arreglos de bits". Una descripción más detallada de este enfoque se puede encontrar en las preguntas frecuentes de comp.lang.c.<xtrapbits.h>

En C++ , aunque boollos elementos individuales suelen ocupar el mismo espacio que un byte o un entero, el tipo STLstd::vector<bool> es una especialización parcial de plantilla en la que los bits se empaquetan como una optimización de eficiencia de 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 una referencia proxy . Esto puede parecer un punto menor, pero significa que novector<bool> es un contenedor STL estándar, razón por la cual generalmente se desaconseja su uso. Otra clase STL única, , ^{[ 2 ]} crea un vector de bits fijo 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 algunas capacidades adicionales, como la capacidad de contar eficientemente la cantidad de bits que están establecidos. Al igual que el array , el tamaño de debe especificarse en tiempo de compilación y no puede ser inferido por el compilador. Las bibliotecas Boost C++ proporcionan una clase ^{[ 3 ]} cuyo tamaño se especifica en tiempo de ejecución.vector<bool>std::bitsetbitsetboost::dynamic_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 directamente direccionables en la mayoría del hardware, sino que devuelve un bool.

En Java , la clase BitSet( java.util.BitSet) crea un array de bits que luego se manipula con funciones cuyos nombres corresponden a operadores bit a bit familiares para los programadores de C. A diferencia de bitseten C++, en Java BitSetno existe un estado de "tamaño" (tiene un tamaño prácticamente infinito, inicializado con 0 bits); un bit puede establecerse o comprobarse en cualquier índice. Además, existe una clase EnumSet( java.util.EnumSet), que representa internamente un conjunto de valores de un tipo enumerado como un vector de bits, como una alternativa más segura a los campos de bits.

El .NET Framework proporciona una Systems.Collections.BitArrayclase de colección. Almacena bits usando una matriz de tipo int(cada elemento de la matriz generalmente representa 32 bits). ^{[ 4 ]} La clase admite acceso aleatorio y operadores bit a bit, se puede iterar sobre ella y su Lengthpropiedad se puede cambiar para aumentarla o truncarla.

Aunque Standard ML no admite matrices de bits, Standard ML de Nueva Jersey incluye una extensión, la BitArrayestructura, en su biblioteca SML/NJ. Esta estructura no tiene un tamaño fijo y admite operaciones de asignación y de bits, incluyendo, de forma inusual, operaciones de desplazamiento.

Haskell tampoco cuenta actualmente con 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, incluidas operaciones de desplazamiento y rotación, y se puede utilizar un array "sin empaquetar" sobre valores booleanos para modelar un array de bits, aunque esto no cuenta con el soporte del módulo anterior.

En Perl , las cadenas se pueden usar como matrices de bits expandibles. Se pueden manipular usando los operadores bit a bit habituales ( ~ | & ^), ^{[ 5 ]} y se pueden probar y establecer bits individuales usando la función vec . ^{[ 6 ]}

En Ruby , se puede acceder (pero no modificar) un bit de un entero ( Fixnumo Bignum) usando el operador de corchete ( []), como si fuera una matriz de bits.

Rust admite el uso de tipos numéricos nativos como matrices de bits de ancho fijo mediante operaciones bit a bit. Bibliotecas de terceros como bitvec^{[ 7 ]} proporcionan interfaces dedicadas.

La biblioteca Core Foundation de Apple contiene las 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 límite de byte o palabra) o no alineados ( los elementos se suceden inmediatamente sin relleno) .

PL/pgSQL y PostgreSQL admiten cadenas de bits como tipo nativo. Hay 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 estos se utilizan para modelar elementos de almacenamiento como biestables , 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 los datos que se transfieren al hardware durante las simulaciones.

Common Lisp proporciona matrices de bits multidimensionales. Se proporciona una implementación unidimensional bit-vectorcomo un caso especial de la función integrada array, que actúa en una doble capacidad como clase y especificador de tipo. ^{[ 9 ]} Las matrices de bits (y por lo tanto los vectores de bits) se basan en la make-arrayfunción general que se configura con un tipo de elemento de bit, que opcionalmente permite que un 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 se pueden construir de forma más concisa mediante la macro de lectura . ^{[ 11 ]} Además de las funciones generales aplicables a todas las matrices, existen operaciones dedicadas para matrices de bits. Se puede acceder a bits individuales y modificarlos utilizando las funciones y ^{[ 12 ]} y se admite un amplio número de operaciones lógicas. ^{[ 13 ]}#*bitsbitsbit

• Unidad aritmético-lógica
• Código binario
• Sistema numérico binario
• Ajedrez de mesa y juegos similares.
• Campo de bits
• Máscara de bits
• Índice de mapa de bits
• Flujo de bits
• Campo finito de 2 elementos, o GF(2)
• Arreglo de Judy
• Código de longitud variable

• Bases matemáticas. Archivado el 16 de octubre de 2019 en Wayback Machine por el profesor DEKnuth.
• vector < bool > No se ajusta a las normas y fuerza la elección de optimización
• vector < bool > : Más problemas, mejores soluciones