Existe um limite prático para o tamanho de máscaras de bits?

Question

Há uma maneira comum para armazenar vários valores em uma variável, usando uma máscara de bits. Por exemplo, se um usuário tiver ler, escrever e executar privilégios sobre um item, que pode ser convertido em um único número, dizendo read = 4 (2^2), write = 2 (2^1), execute = 1 (2^0) e adicioná-los em conjunto para obter 7.

Eu uso essa técnica em várias aplicações web, onde eu normalmente armazenam a variável em um campo e dar-lhe um tipo de MEDIUMINT ou qualquer outra coisa, dependendo do número de valores diferentes.

O que eu estou interessado, é se há ou não um limite prático para o número de valores que você pode armazenar como este? Por exemplo, se o número foi de mais de 64, você não poderia usar inteiros (64 bits) mais. Se este fosse o caso, o que você usaria? Como isso afetaria a sua lógica do programa (ou seja: você ainda pode usar comparações bit a bit)?

Eu sei que uma vez que você começar a ficar realmente grandes conjuntos de valores, um método diferente seria a solução ideal, mas estou interessado nas fronteiras de este método.

Answer 1

Em cima da minha cabeça, eu ia escrever uma função set_bit e get_bit que poderia levar uma matriz de bytes e um deslocamento na matriz de bits, e usar algum bit-twiddling para set / get a bit apropriado na matriz . Algo parecido com isto (em C, mas espero que você começa a idéia):

// sets the n-th bit in |bytes|. num_bytes is the number of bytes in the array
// result is 0 on success, non-zero on failure (offset out-of-bounds)
int set_bit(char* bytes, unsigned long num_bytes, unsigned long offset)
{
  // make sure offset is valid
  if(offset < 0 || offset > (num_bytes<<3)-1) { return -1; }

  //set the right bit
  bytes[offset >> 3] |= (1 << (offset & 0x7));

  return 0; //success 
}

//gets the n-th bit in |bytes|. num_bytes is the number of bytes in the array
// returns (-1) on error, 0 if bit is "off", positive number if "on"
int get_bit(char* bytes, unsigned long num_bytes, unsigned long offset)
{
  // make sure offset is valid
  if(offset < 0 || offset > (num_bytes<<3)-1) { return -1; }

  //get the right bit
  return (bytes[offset >> 3] & (1 << (offset & 0x7));
}

Answer 2

Eu usei máscaras de bits no código de sistema de arquivos onde a máscara de bits é muitas vezes maior do que uma palavra de máquina. pense nisso como um "array de booleanos";

(journalling máscaras em memória flash se você quer saber)

muitos compiladores sabem como fazer isto para você . Adda pouco de código OO ter tipos que operam senibly e, em seguida, seu código começa olhando como se fosse a intenção, não um bit-banging.

Os meus 2 centavos.

Answer 3

Com um inteiro de 64 bits, você pode armazenar valores de até 2 ^ 64-1, 64 é de apenas 2 ^ 6. Então, sim, há um limite, mas se precisar de mais do que 64 seu valor de bandeiras, eu estaria muito interessado em saber o que eles estavam fazendo tudo:)

Como muitos estados para que você precisa pensar potencialmente aproximadamente? Se você tem 64 estados potenciais, o número de combinações que podem existir em é o tamanho total de um inteiro de 64 bits.

Se você precisa se preocupar com 128 bandeiras, em seguida, um par de vetores de bits seria suficiente (2 ^ 64 * 2).

Adição : Na programação Pérolas, há uma extensa discussão do uso de uma matriz de bits de comprimento 10 ^ 7, implementado em números inteiros (para exploração utilizada 800 números) - é muito rápido, e muito apropriado para a tarefa descrita nesse capítulo.

Answer 4

Alguns idiomas (Eu acredito perl faz, não tenho certeza) permitir aritmética bit a bit em cordas. Dando-lhe uma gama muito maior eficaz. ((STRLEN * 8bit caracteres) combinações)

No entanto, eu não iria usar um único valor para sobreposição de mais de um tipo / / de dados. A r básico / w / x trio de ints 3 bits provavelmente seria o limite superior "prático", e não por razões de eficiência de espaço, mas por razões práticas de desenvolvimento.

(Php utiliza este sistema para controlar seu erro, mensagens, e eu já descobri que é um pouco over-the-top quando você tem que definir valores, onde constantes do PHP não são residentes e você tem que gerar o inteiro à mão , e para ser honesto, se chmod não suporta a sintaxe do estilo 'ugo + rwx' Eu nunca iria querer usá-lo porque eu nunca consigo lembrar os números mágicos)

O instante em que você tem que se abrir uma tabela de constantes para depurar o código que você sabe que você tenha ido longe demais.

Answer 5

discussão antiga, mas vale a pena mencionar que existem casos que exijam máscaras pouco inchado, por exemplo, impressões digitais moleculares, que são muitas vezes gerados como arrays de 1024 bits que temos embalados em 32 campos bigint (SQL Server não apoiar UInt32). Bit operações sábios funcionar bem - até que seus começos da tabela para crescer e você percebe a lentidão de chamadas de função separadas. O tipo de dados binários iria funcionar, se não fosse pela proibição do T-SQL para os operadores bit a bit com dois operandos binários.

Answer 6

Por exemplo .NET usa matriz de inteiros como um armazenamento interno para a sua classe BitArray. Praticamente não há nenhuma outra maneira ao redor.

Dito isto, no SQL que você vai precisar de mais do que uma coluna (ou use o BLOBS) para armazenar todos os estados.

Answer 7

Você marcado este SQL pergunta, então eu acho que você precisa consultar com a documentação do seu banco de dados para encontrar o tamanho de um inteiro. Em seguida, subtrair um bit para o sinal, apenas para ser seguro.

Editar: O seu comentário diz que você está usando o MySQL. A documentação para MySQL 5.0 tipos numéricos estados que o o tamanho máximo de um código numérico é de 64 ou 65 dígitos. Isso é 212 bits para 64 dígitos.

Lembre-se que o idioma de escolha tem que ser capaz de trabalhar com esses dígitos, então você pode ser limitada a um número inteiro de 64-bit de qualquer maneira.