Matriz de bits - Bit array

Uma matriz de bits (também conhecida como mapa de bits , conjunto de bits , sequência de bits ou vetor de bits ) é uma estrutura de dados de matriz que armazena bits de forma compacta . Ele pode ser usado para implementar uma estrutura de dados de conjunto simples . Uma matriz de bits é eficaz na exploração do paralelismo de nível de bits no hardware para executar operações rapidamente. Uma matriz de bits típica armazena kw bits, onde w é o número de bits na unidade de armazenamento, como um byte ou palavra , ek é algum número inteiro não negativo. Se w não divide o número de bits a serem armazenados, algum espaço é desperdiçado devido à fragmentação interna .

Definição

Uma matriz de bits é um mapeamento de algum domínio (quase sempre um intervalo de inteiros) para valores no conjunto {0, 1}. Os valores podem ser interpretados como escuro / claro, ausente / presente, bloqueado / desbloqueado, válido / inválido etc. A questão é que existem apenas dois valores possíveis, portanto, eles podem ser armazenados em um bit. Como acontece com outras matrizes, o acesso a um único bit pode ser gerenciado aplicando-se um índice à matriz. Assumindo que seu tamanho (ou comprimento) seja de n bits, a matriz pode ser usada para especificar um subconjunto do domínio (por exemplo, {0, 1, 2, ..., n −1}), onde 1 bit indica o presença e 0 bit a ausência de um número no conjunto. Essa estrutura de conjunto de dados usa cerca de n / w palavras de espaço, onde w é o número de bits em cada palavra de máquina . Se o bit menos significativo (da palavra) ou o bit mais significativo indica o número de menor índice é amplamente irrelevante, mas o primeiro tende a ser preferido (em máquinas little-endian ).

Operações básicas

Embora a maioria das máquinas não seja capaz de endereçar bits individuais na memória, nem tenha instruções para manipular bits únicos, cada bit em uma palavra pode ser separado e manipulado usando operações bit a bit . Em particular:

  • OU pode ser usado para definir um bit para um: 11101010 OR 00000100 = 11101110
  • E pode ser usado para definir um bit como zero: 11101010 AND 11111101 = 11101000
  • E junto com o teste de zero pode ser usado para determinar se um bit está definido:
    11101010 AND 00000001 = 00000000 = 0
    11101010 E 00000010 = 00000010 ≠ 0
  • XOR pode ser usado para inverter ou alternar um pouco:
    11101010 XOR 00000100 = 11101110
    11101110 XOR 00000100 = 11101010
  • NOT pode ser usado para inverter todos os bits.
    NÃO 10110010 = 01001101

Para obter a máscara de bits necessária para essas operações, podemos usar um operador de deslocamento de bits para deslocar o número 1 para a esquerda pelo número apropriado de casas, bem como negação bit a bit, se necessário.

Dadas duas matrizes de bits do mesmo tamanho que representam conjuntos, podemos calcular sua união , interseção e diferença teórica de conjunto usando n / w operações de bit simples cada (2 n / w para diferença), bem como o complemento de: 

for i from 0 to n/w-1
    complement_a[i] := not a[i]
    union[i]        := a[i] or b[i]
    intersection[i] := a[i] and b[i]
    difference[i]   := a[i] and (not b[i])

Se desejarmos iterar pelos bits de uma matriz de bits, podemos fazer isso de forma eficiente usando um loop duplamente aninhado que percorre cada palavra, uma de cada vez. Apenas n / w acessos de memória são necessários: 

for i from 0 to n/w-1
    index := 0    // if needed
    word := a[i]
    for b from 0 to w-1
        value := word and 1 ≠ 0
        word := word shift right 1
        // do something with value
        index := index + 1    // if needed

Ambos os exemplos de código exibem localidade ideal de referência , que subsequentemente receberá grande aumento de desempenho de um cache de dados. Se uma linha de cache tiver k palavras, ocorrerão apenas cerca de n / wk perdas de cache.

Operações mais complexas

Como ocorre com as strings de caracteres , é simples definir comprimento , substring , comparação lexicográfica , concatenação e operações reversas . A implementação de algumas dessas operações é sensível ao endianness .

Peso da população / Hamming

Se quisermos encontrar o número de 1 bits em uma matriz de bits, às vezes chamada de contagem da população ou peso de Hamming, existem algoritmos sem ramificação eficientes que podem calcular o número de bits em uma palavra usando uma série de operações simples de bits. Simplesmente executamos esse algoritmo em cada palavra e mantemos um total em execução. A contagem de zeros é semelhante. Consulte o artigo sobre peso de Hamming para obter exemplos de uma implementação eficiente.

Inversão

A inversão vertical de uma imagem de um bit por pixel, ou alguns algoritmos FFT, requer a inversão dos bits de palavras individuais (assim b31 b30 ... b0se torna b0 ... b30 b31). Quando esta operação não está disponível no processador, ainda é possível proceder por passes sucessivos, neste exemplo em 32 bits: 

exchange two 16-bit halfwords
exchange bytes by pairs (0xddccbbaa -> 0xccddaabb)
...
swap bits by pairs
swap bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)

The last operation can be written ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)).

Encontre o primeiro

O primeiro conjunto localizar ou localizar primeiro uma operação identifica o índice ou posição do 1-bit com o menor índice em uma matriz e tem amplo suporte de hardware (para matrizes não maiores que uma palavra) e algoritmos eficientes para sua computação. Quando uma fila de prioridade é armazenada em uma matriz de bits, localizar primeiro pode ser usado para identificar o elemento de maior prioridade na fila. Para expandir um tamanho de palavra, encontre primeiro um para matrizes mais longas, pode-se encontrar a primeira palavra diferente de zero e, em seguida, executar encontrar primeiro nessa palavra. As operações afins encontrar zero, primeiro , contar zeros , contar os principais , contar zeros à direita , Quantidade de fuga aqueles , e log na base 2 (ver encontrar primeiro conjunto ) também pode ser estendido para uma matriz de bits de uma maneira simples.

Compressão

Uma matriz de bits é o armazenamento mais denso para bits "aleatórios", ou seja, onde cada bit tem a mesma probabilidade de ser 0 ou 1, e cada um é independente. Mas a maioria dos dados não é aleatória, portanto, pode ser possível armazená-los de forma mais compacta. Por exemplo, os dados de uma imagem típica de fax não são aleatórios e podem ser compactados. A codificação de comprimento de execução é comumente usada para compactar esses fluxos longos. No entanto, a maioria dos formatos de dados compactados não são tão fáceis de acessar aleatoriamente; também, ao compactar arrays de bits de maneira muito agressiva, corremos o risco de perder os benefícios devido ao paralelismo de nível de bits ( vetorização ). Assim, em vez de compactar matrizes de bits como fluxos de bits, podemos compactá-los como fluxos de bytes ou palavras (consulte Índice de bitmap (compactação) ).

Vantagens e desvantagens

Matrizes de bits, apesar de sua simplicidade, têm uma série de vantagens marcantes sobre outras estruturas de dados para os mesmos problemas:

  • Eles são extremamente compactos; nenhuma outra estrutura de dados pode armazenar n dados independentes em n / w palavras.
  • Eles permitem que pequenos arranjos de bits sejam armazenados e manipulados no conjunto de registros por longos períodos de tempo sem nenhum acesso à memória.
  • Por causa de sua capacidade de explorar o paralelismo de nível de bit, limitar o acesso à memória e usar ao máximo o cache de dados , eles geralmente superam muitas outras estruturas de dados em conjuntos de dados práticos, mesmo aqueles que são mais assintoticamente eficientes.

No entanto, as matrizes de bits não são a solução para tudo. Em particular:

  • Sem compactação, eles são estruturas de dados de conjuntos inúteis para conjuntos esparsos (aqueles com poucos elementos em comparação com seu intervalo) no tempo e no espaço. Para tais aplicativos, arrays de bits compactados, arrays Judy , try ou mesmo filtros Bloom devem ser considerados.
  • O acesso a elementos individuais pode ser caro e difícil de expressar em alguns idiomas. Se o acesso aleatório for mais comum do que sequencial e a matriz for relativamente pequena, uma matriz de bytes pode ser preferível em uma máquina com endereçamento de bytes. Uma matriz de palavras, no entanto, provavelmente não se justifica devido ao enorme overhead de espaço e às perdas de cache adicionais que ela causa, a menos que a máquina tenha apenas endereçamento de palavras.

Formulários

Por causa de sua compactação, as matrizes de bits têm uma série de aplicações em áreas onde espaço ou eficiência são escassos. Mais comumente, eles são usados ​​para representar um grupo simples de sinalizadores booleanos ou uma seqüência ordenada de valores booleanos.

Matrizes de bits são usadas para filas de prioridade , onde o bit no índice k é definido se e somente se k estiver na fila; essa estrutura de dados é usada, por exemplo, pelo kernel do Linux e se beneficia fortemente de uma operação de localização de zero no hardware.

Matrizes de bits podem ser usadas para a alocação de páginas de memória , inodes , setores de disco, etc. Nesses casos, o termo bitmap pode ser usado. No entanto, este termo é freqüentemente usado para se referir a imagens raster , que podem usar vários bits por pixel .

Outra aplicação de matrizes de bits é o filtro Bloom , uma estrutura de dados de conjuntos probabilísticos que pode armazenar grandes conjuntos em um pequeno espaço em troca de uma pequena probabilidade de erro. Também é possível construir tabelas de hash probabilísticas com base em matrizes de bits que aceitam falsos positivos ou falsos negativos.

Matrizes de bits e as operações nelas também são importantes para a construção de estruturas de dados sucintas , que usam quase o mínimo de espaço possível. Neste contexto, as operações de como encontrar o n ° 1 bit ou contando o número de bits 1 até uma determinada posição tornam-se importantes.

Matrizes de bits também são uma abstração útil para examinar fluxos de dados compactados , que geralmente contêm elementos que ocupam porções de bytes ou não são alinhados por byte. Por exemplo, a representação de codificação Huffman compactada de um único caractere de 8 bits pode ter de 1 a 255 bits de comprimento.

Na recuperação de informações , os arrays de bits são uma boa representação para as listas de postagem de termos muito frequentes. Se nós calcular as diferenças entre valores adjacentes na lista de números inteiros estritamente crescente e codificá-los usando unária codificação , o resultado é uma matriz de bits com um bit 1, no n ° posição, se e somente se n estiver na lista. A probabilidade implícita de uma lacuna de n é 1/2 n . Este também é o caso especial da codificação Golomb, onde o parâmetro M é 1; este parâmetro só é normalmente selecionado quando -log (2- p ) / log (1- p ) ≤ 1, ou aproximadamente o termo ocorre em pelo menos 38% dos documentos.

Suporte de linguas

A linguagem de programação APL oferece suporte total a matrizes de bits de formato e tamanho arbitrários como um tipo de dados booleano distinto de inteiros. Todas as principais implementações ( Dyalog APL, APL2, APL Next, NARS2000, Gnu APL , etc.) compactam os bits densamente em qualquer tamanho que seja a palavra da máquina. Os bits podem ser acessados ​​individualmente por meio da notação de indexação usual (A [3]), bem como por meio de todas as funções e operadores primitivos usuais, onde são frequentemente operados usando um algoritmo de caso especial, como somar os bits por meio de uma tabela de consulta de bytes .

A linguagem de programação C 's campos de bits , pseudo-objectos encontrados em estruturas com tamanho igual a algum número de bits, são na verdade matrizes bit pequenas; eles são limitados porque não podem abranger palavras. Embora eles forneçam uma sintaxe conveniente, os bits ainda são acessados ​​usando operadores bytewise na maioria das máquinas, e eles só podem ser definidos estaticamente (como os arrays estáticos do C, seus tamanhos são fixos em tempo de compilação). Também é um idioma comum para programadores C usar palavras como pequenos arrays de bits e acessar bits deles usando operadores de bits. Um arquivo de cabeçalho amplamente disponível incluído no sistema X11 , xtrapbits.h, é “uma maneira portátil para os sistemas definirem a manipulação do campo de bits de matrizes de bits”. Uma descrição mais explicativa da abordagem mencionada pode ser encontrada em comp.lang.c faq .

Em C ++ , embora bools individuais normalmente ocupem o mesmo espaço que um byte ou um inteiro, o tipo STLvector<bool> é uma especialização de modelo parcial na qual os bits são compactados como uma otimização de eficiência de espaço. Uma vez que bytes (e não bits) são a menor unidade endereçável em C ++, o operador [] não retorna uma referência a um elemento, mas em vez disso retorna uma referência de proxy . Isso pode parecer um ponto secundário, mas significa que nãovector<bool> é um contêiner STL padrão, razão pela qual o uso de geralmente é desencorajado. Outra classe STL exclusiva , cria um vetor de bits fixado em um tamanho específico no tempo de compilação e, em sua interface e sintaxe, se assemelha mais ao uso idiomático de palavras como conjuntos de bits por programadores C. Ele também tem algum poder adicional, como a capacidade de contar com eficiência o número de bits definidos. As Bibliotecas Boost C ++ fornecem uma classe cujo tamanho é especificado em tempo de execução. vector<bool>bitsetdynamic_bitset

A linguagem de programação D fornece arrays de bits em sua biblioteca padrão, Phobos, em std.bitmanip. Como em C ++, o operador [] não retorna uma referência, uma vez que bits individuais não são endereçáveis ​​diretamente na maioria do hardware, mas em vez disso retorna a bool.

Em Java , a classe BitSetcria uma matriz de bits que é então manipulada com funções nomeadas após operadores de bits familiares aos programadores C. Ao contrário do bitsetC ++, o Java BitSetnão tem um estado de "tamanho" (ele tem um tamanho efetivamente infinito, inicializado com 0 bits); um bit pode ser definido ou testado em qualquer índice. Além disso, existe uma classe EnumSet, que representa um conjunto de valores de um tipo enumerado internamente como um vetor de bits, como uma alternativa mais segura aos campos de bits.

O .NET Framework fornece uma BitArrayclasse de coleção. Ele armazena bits usando uma matriz do tipo int(cada elemento na matriz geralmente representa 32 bits). A classe suporta acesso aleatório e operadores bit a bit, pode ser iterada e sua Lengthpropriedade pode ser alterada para aumentar ou truncar.

Embora o Standard ML não tenha suporte para matrizes de bits, o Standard ML de New Jersey tem uma extensão, a BitArrayestrutura, em sua biblioteca SML / NJ. Ele não tem tamanho fixo e oferece suporte a operações de conjunto e operações de bit, incluindo, de maneira incomum, operações de deslocamento.

Haskell da mesma forma atualmente carece de suporte padrão para operações bit a bit, mas tanto GHC quanto Hugs fornecem um Data.Bitsmódulo com diversas funções e operadores bit a bit, incluindo operações de deslocamento e rotação e uma matriz "unboxed" sobre valores booleanos pode ser usada para modelar uma matriz de bits, embora isso carece de suporte do módulo anterior.

Em Perl , as strings podem ser usadas como matrizes de bits expansíveis. Eles podem ser manipulados usando os operadores bit a bit usuais ( ~ | & ^), e bits individuais podem ser testados e configurados usando a função vec .

Em Ruby , você pode acessar (mas não definir) um bit de um inteiro ( Fixnumou Bignum) usando o operador colchete ( []), como se fosse um array de bits.

Da Apple Núcleo Fundação biblioteca contém CFBitVector e CFMutableBitVector estruturas.

PL / I oferece suporte a matrizes de sequências de bits de comprimento arbitrário, que pode ser de comprimento fixo ou variável. Os elementos da matriz podem ser alinhados - cada elemento começa em um byte ou limite de palavra - ou desalinhados - os elementos seguem imediatamente uns aos outros sem preenchimento.

PL / pgSQL e PostgreSQL's SQL suportam cadeias de bits como tipo nativo. Existem dois tipos de bits SQL: e , onde é um número inteiro positivo. bit(n)bit varying(n)n

Linguagens de descrição de hardware como VHDL , Verilog e SystemVerilog oferecem suporte nativo a vetores de bits, pois são usados ​​para modelar elementos de armazenamento como flip-flops , barramentos de hardware e sinais de hardware em geral. Em linguagens de verificação de hardware, como OpenVera , e e SystemVerilog , os vetores de bits são usados ​​para amostrar valores dos modelos de hardware e para representar dados que são transferidos para o hardware durante as simulações.

Common Lisp fornece uma bit-vectorimplementação unidimensional como um caso especial do embutido array, agindo em uma capacidade dual como uma classe e um especificador de tipo. Sendo um derivado do array, ele depende da make-arrayfunção geral de ser configurado com um tipo de elemento de bit, que opcionalmente permite que o vetor de bits seja designado como redimensionável dinamicamente. O bit-vector, entretanto, não é infinito em extensão. Existe um simple-bit-vectortipo mais restrito , que exclui explicitamente as características dinâmicas. Os vetores de bits são representados e podem ser construídos de maneira mais concisa pela macro do leitor . Além das funções gerais aplicáveis ​​a todas as matrizes, existem operações dedicadas para vetores de bits. Bocados individuais podem ser acedidos e modificados utilizando o e funções e um grande número de operações lógicas é suportado. #*bitsbitsbit

Veja também

Referências

links externos