Bit array
Um bit array, ou arranjo de bit (também conhecido como bitmap, bitset, bit string ou bit vector) é um arranjo que armazena bits compactadamente, podendo ser usado para implementar um simples conjunto. O bit array é efetivo ao explorar paralelismo à "nível bit" em um hardware para executar operações rapidamente. Um típico arranjo armazena kw bits, onde w é o número de bits n unidade de armazenamento, como um byte ou palavra e k é algum inteiro não negativo. Se w não divide o número de bits a ser armazenados algum espaço é desperdiçado devido a fragmentação.
Definição
Um bit array é um mapeamento de algum domínio (quase sempre uma variedade de inteiros) para valores no conjunto {0, 1}. Os valores podem ser interpretados como claro/escuro, presente/ausente, travado/destravado, válido/inválido, etc. O ponto é que há somente duas possibilidades de valores que serão armazenados em um bit. Assim como em outros arranjos, o acesso a um único bit pode ser gerenciado por aplicar um índice ao arranjo. Assumindo que seu tamanho (ou comprimento) será n bits o arranjo pode ser usado para especificar um subconjunto do domínio (ex: [0, 1, 2, ..., n−1]), onde o primeiro bit indica a presença de um bit "zero", a ausência de um número no conjunto. Esse conjunto de estrutura de dados usam cerca de n/w palavras de espaço, onde w é o número de cada palavra. Se ao menos um bit significativo (da palavra) ou o bit mais significativo indica o numero de menor índice é largamente relevante, mas o primeiro tende a ser mais preferido (em uma extremidade).
Ligações externas
- mathematical bases por Pr. D.E.Knuth
- vector<bool> Is Nonconforming, and Forces Optimization Choice
- vector<bool>: More Problems, Better Solutions
