indexação bit a bit em C?

Question

Estou tentando implementar uma ideia de compactação de dados que tive e, como estou imaginando executá-la em um grande corpus de dados de teste, pensei em codificá-la em C (tenho experiência principalmente em linguagens de script como Ruby e Tcl.)

Olhando os livros de 'vaca' da O'Reilly sobre C, percebo que não posso simplesmente indexar os bits de uma variável simples do tipo 'char' ou 'int' como gostaria de fazer comparações e operadores bit a bit.

Estou correto nesta percepção?É razoável usar um tipo enumerado para representar um bit (e criar uma matriz deles e escrever funções para converter de e para char)?Em caso afirmativo, esse tipo e funções já estão definidos em uma biblioteca padrão em algum lugar?Existem outras abordagens (melhores?)?Existe algum exemplo de código em algum lugar que alguém possa me indicar?

Obrigado -

Answer 1

Seguindo o que Kyle disse, você pode usar uma macro para fazer o trabalho pesado para você.

É possível.

Para definir o enésimo bit, use OR:

x |= (1 << 5);// define o sexto à direita

Para esclarecer um pouco, use AND:

x&= ~(1 << 5);// Limpa o 6º da direita

Para virar um pouco, use XOR:

x^= (1 << 5);// vira 6º da direita

Ou...

#define GetBit(var, bit) ((var & (1 << bit)) != 0) // Returns true / false if bit is set
#define SetBit(var, bit) (var |= (1 << bit))
#define FlipBit(var, bit) (var ^= (1 << bit))

Então você pode usá-lo em código como:

int myVar = 0;
SetBit(myVar, 5);
if (GetBit(myVar, 5))
{
  // Do something
}

Answer 2

É possível.

Para definir o enésimo bit, use OR:

x |= (1 << 5); // sets the 5th-from right

Para esclarecer um pouco, use AND:

x &= ~(1 << 5); // clears 5th-from-right

Para virar um pouco, use XOR:

x ^= (1 << 5); // flips 5th-from-right

Para obter o valor de um bit, use shift e AND:

(x & (1 << 5)) >> 5 // gets the value (0 or 1) of the 5th-from-right

observação:o deslocamento para a direita 5 é para garantir que o valor seja 0 ou 1.Se você está interessado apenas em 0/não 0, pode passar sem a mudança.

Answer 3

Dê uma olhada nas respostas para essa questão.

Answer 4

Teoria

Não há sintaxe C para acessar ou definir o n-ésimo bit de um tipo de dados integrado (por exemploum 'caractere').No entanto, você pode acessar bits usando uma operação lógica AND e definir bits usando uma operação lógica OR.

Por exemplo, digamos que você tenha uma variável que contém 1101 e deseja verificar o segundo bit da esquerda.Basta executar um AND lógico com 0100:

1101
0100
---- AND
0100

Se o resultado for diferente de zero, então o segundo bit deve ter sido setado;caso contrário, não foi definido.

Se você deseja definir o terceiro bit da esquerda, execute um OR lógico com 0010:

1101
0010
---- OR
1111

Você pode usar os operadores C && (for e) e || (para ou) para executar essas tarefas.Você mesmo precisará construir os padrões de acesso de bits (0100 e 0010 nos exemplos acima).O truque é lembrar que o bit menos significativo (LSB) conta 1s, o próximo LSB conta 2s, depois 4s etc.Portanto, o padrão de acesso de bits para o n-ésimo LSB (começando em 0) é simplesmente o valor de 2^n.A maneira mais fácil de calcular isso em C é deslocar o valor binário 0001 (neste exemplo de quatro bits) para a esquerda pelo número necessário de casas.Como esse valor é sempre igual a 1 em quantidades semelhantes a inteiros sem sinal, isso é apenas '1 << n'

Exemplo

unsigned char myVal = 0x65; /* in hex; this is 01100101 in binary. */

/* Q: is the 3-rd least significant bit set (again, the LSB is the 0th bit)? */
unsigned char pattern = 1;
pattern <<= 3; /* Shift pattern left by three places.*/

if(myVal && (char)(1<<3)) {printf("Yes!\n");} /* Perform the test. */

/* Set the most significant bit. */
myVal |= (char)(1<<7);

Este exemplo não foi testado, mas deve servir para ilustrar a ideia geral.

Answer 5

Para consultar o estado do bit com índice específico:

int index_state = variable & ( 1 << bit_index );

Para definir o bit:

varabile |= 1 << bit_index;

Para reiniciar o bit:

variable &= ~( 1 << bit_index );

Answer 6

Bits individuais podem ser indexados da seguinte maneira.

Defina uma estrutura como esta:

struct
{
  unsigned bit0     : 1;
  unsigned bit1     : 1;
  unsigned bit2     : 1;
  unsigned bit3     : 1;
  unsigned reserved : 28;
} bitPattern;   

Agora, se eu quiser saber os valores dos bits individuais de uma var chamada "valor", faça o seguinte:

CopyMemory( &input, &value, sizeof(value) );

Para ver se o bit 2 é alto ou baixo:

int state = bitPattern.bit2;

Espero que isto ajude.

Answer 7

Tente usar campos de bits.Tenha cuidado, pois a implementação pode variar de acordo com o compilador.

http://publications.gbdirect.co.uk/c_book/chapter6/bitfields.html

Answer 8

SE você quiser indexar um pouco, você pode:

bit = (char & 0xF0) >> 7;

obtém o msb de um caractere.Você pode até deixar de fora o turno certo e fazer um teste em 0.

bit = char & 0xF0;

se o bit estiver setado o resultado será > 0;

obviamente, você precisa alterar a máscara para obter bits diferentes (NB:o 0xF é a máscara de bits se não estiver claro).É possível definir inúmeras máscaras, por ex.

#define BIT_0 0x1 // or 1 << 0
#define BIT_1 0x2 // or 1 << 1
#define BIT_2 0x4 // or 1 << 2
#define BIT_3 0x8 // or 1 << 3

etc...

Isso lhe dá:

bit = char & BIT_1;

Você pode usar essas definições no código acima para indexar com êxito um bit dentro de uma macro ou função.

Para definir um pouco:

char |= BIT_2;

Para esclarecer um pouco:

char &= ~BIT_3

Para alternar um pouco

char ^= BIT_4

Esta ajuda?

Answer 9

Existe um contêiner de biblioteca padrão para bits:std::vetor.É especializado na biblioteca para economizar espaço.Há também uma classe boost dynamic_bitset.

Isso permitirá que você execute operações em um conjunto de valores booleanos, usando um bit por valor de armazenamento subjacente.

Aumente a documentação do bitset dinâmico

Para obter a documentação STL, consulte a documentação do compilador.

Claro, você também pode endereçar manualmente os bits individuais em outros tipos de integrais.Se você fizer isso, deverá usar tipos não assinados para não obter um comportamento indefinido se decidir fazer uma mudança para a direita em um valor com o bit alto definido.No entanto, parece que você quer os contêineres.

Para o comentarista que afirmou que isso ocupa 32 vezes mais espaço do que o necessário:boost::dynamic_bitset e vector são especializados para usar um bit por entrada e, portanto, não há penalidade de espaço, assumindo que você realmente deseja mais do que o número de bits em um tipo primitivo.Essas classes permitem endereçar bits individuais em um contêiner grande com armazenamento subjacente eficiente.Se você deseja apenas (digamos) 32 bits, use um int.Se você quiser um grande número de bits, poderá usar um contêiner de biblioteca.