Ferramentas do usuário

Ferramentas do site


prog2:operacoes_com_bits

Operações com bits

Bit fields

Muitas vezes não precisamos de muitos bits para representar uma informação. Por exemplo, basta 1 bit para armazenar um valor lógico (true/false); uma variável com 10 valores possíveis necessitaria apenas 4 bits (pois 24 = 16), e assim por diante.

Por exemplo, o struct abaixo permite armazenar um valor de data e hora:

typedef struct
{
  unsigned char  hour, min, sec ;
  unsigned char  month, day ;
  unsigned short year ;
} date_t ;

Em máquinas com arquitetura de 32 ou 64 bits, cada variável to tipo date_t ocupa 8 bytes de memória:

  • 5 bytes para os 5 unsigned char
  • 1 byte de padding (“enchimento”)
  • 2 bytes para o unsigned short

O padding é necessário porque o inteiro deve estar “alinhado” na memória, ou seja, seu primeiro byte deve estar em um endereço par (word-size = 2 bytes), para ser lido corretamente pelo processador. Além disso, a estrutura em si também deve estar alinhada em words, da mesma forma.

Entretanto, há espaço para alguma economia de memória, pois os campos não usam toda a faixa de valores oferecida por seus tipos:

campo tipo bits usados faixa bits necessários
hour unsigned char 8 0 … 23 5
min unsigned char 8 0 … 59 6
sec unsigned char 8 0 … 59 6
day unsigned char 8 0 … 31 5
mon unsigned char 8 0 … 11 4
year unsigned short 16 0 … 40001) 12
TOTAL 38

A linguagem C permite definir variáveis inteiras com um número específico de bits dentro de structs, através de uma funcionalidade chamada bitfield:

typedef struct
{
  unsigned short year:12 ;
  unsigned char  month:4 ;
  unsigned char  day:5 ;
  unsigned char  hour:5 ;
  unsigned char  min:6 ;
  unsigned char  sec:6 ;
} date_t ;

Essa nova estrutura demanda 38 bits, ou 4,75 bytes. Devido à necessidade de usar bytes inteiros e do alinhamento, na realidade a estrutura ocupa 6 bytes de memória, ou seja, 2 bytes a menos que no caso anterior.

Bitfields são muito úteis quando é necessário ler ou manipular bits individuais na memória. Uma aplicação frequente é no acesso a estruturas de dados de baixo nível, em drivers de acesso ao hardware. Por exemplo, o struct abaixo representa um registrador de 32 bits da interface de um controlador de disco rígido:

struct DISK_REGISTER  {
     unsigned ready:1 ;
     unsigned error_occured:1 ;
     unsigned disk_spinning:1 ;
     unsigned write_protect:1 ;
     unsigned head_loaded:1 ;
     unsigned error_code:8 ;
     unsigned track:9 ;
     unsigned sector:5 ;
     unsigned command:5 ;
} ;

Outro exemplo muito interessante de uso de bitfields pode ser encontrado no arquivo ieee754.h do código-fonte do Linux. Esse arquivo define a estrutura em memória dos números de ponto flutuante conforme o padrão IEEE 754.

union ieee754_float
{
  float f ;
 
  struct    /* IEEE 754 single-precision */
  {
#if __BYTE_ORDER == __BIG_ENDIAN
    unsigned int negative:1 ;
    unsigned int exponent:8 ;
    unsigned int mantissa:23 ;
#endif
#if __BYTE_ORDER == __LITTLE_ENDIAN
    unsigned int mantissa:23 ;
    unsigned int exponent:8 ;
    unsigned int negative:1 ;
#endif
  } ieee ;
  // ... conteúdo resumido
} ;

Cuidados a tomar no uso de bitfields:

  • elementos de bitfield não podem ser endereçados por ponteiros, pois podem não começar no início de um byte de memória;
  • muitos compiladores limitam o tamanho de um bitfield ao tamanho máximo de um inteiro (16, 32 ou 64 bits);
  • vetores de bitfields não são permitidos.
  • o uso de bitfields pode tornar o código não-portável entre máquinas com configuração little/big endian distintas.

Acesso a bits individuais

Para testar um bit específico em uma variável inteira, podemos efetuar um AND bit a bit entre essa variável e uma máscara de bits na qual somente o bit a ser testado é verdadeiro.

Por exemplo: para verificar se o 4° bit de value está ativo, pode ser usado:

if ( value & 0x8 )		// 0x8 = 0000 1000 em binário
{
   ...
}

Para Ativar um bit específico, basta efetuar um OR bit-a-bit entre a variável e a máscara de bits correspondente.

Por exemplo: para ativar o 3° bit de value, pode ser usado:

value = value | 0x4 ;		// 0x4 = 0000 0100 em binário
value |= 0x4 ; 			// versão compacta

Similarmente, para desativar o 3o bit da variável value:

value = value & ~ 0x4 ;		// explique!

A máscara de bits também pode ser gerada por deslocamentos, caso ela não seja fixa:

if ( value & (1 << 4) )		// testa o 4° bit de value
{
   value = value |   1 << 3 ;	// ativa o 3° bit de value
   value = value & ~ 1 << 6 ;	// desliga o 6° bit de value
}

Bitmaps

Bits individuais na memória podem ser utilizados para representar valores true/false com muita economia de memória. Um bitmap é um vetor de bits, onde cada bit individual pode ser lido ou ajustado como 0 ou 1.

Estruturas de bitmaps são muito úteis para representar conjuntos. Po exemplo, em um bitmap com 1000 bits, um bit em 1 na posição 375 indica que o elemento 375 pertence ao conjunto.

Bitmaps não são diretamente suportados pela linguagem C, mas são simples de construir. Bitmaps de pequeno tamanho podem ser implementados diretamente sobre variáveis inteiras, usando os operadores de bits vistos acima. Para bitmaps maiores, podem ser implementadas funções ou macros que operem sobre vetores de inteiros de tamanho adequado.

A implementação a seguir, extraída da questão 20.8 da FAQ de comp.lang.c, foi realizada usando macros de preprocessador, para maior eficiência:

#include <limits.h>		/* for CHAR_BIT */
 
// auxiliar macros
#define BITMASK(b)      (1 << ((b) % CHAR_BIT))	          // generate bit mask
#define BITSLOT(b)      ((b) / CHAR_BIT)                  // in which cell?
#define BITNSLOTS(nb)   ((nb + CHAR_BIT - 1) / CHAR_BIT)  // number of cells
 
// bit operations
#define BITSET(a, b)    ((a)[BITSLOT(b)] |=  BITMASK(b))  // bit = 1
#define BITCLEAR(a, b)  ((a)[BITSLOT(b)] &= ~BITMASK(b))  // bit = 0
#define BITTEST(a, b)   ((a)[BITSLOT(b)] &   BITMASK(b))  // bit == 1 ?
#define BITTOGGLE(a, b) ((a)[BITSLOT(b)] ^=  BITMASK(b))  // bit = ^bit

Exemplos de uso dessa implementação:

char bitarray[BITNSLOTS(47)] ;          // declarar um mapa de 47 bits
BITSET(bitarray, 23) ;                  // ativar o bit 23
if (BITTEST(bitarray, 35)) { ... }      // testar o bit 35

Exercícios

(sugeridos pelo monitor Eric Low Schmidt)

  1. Crie uma estrutura que seja capaz de analisar uma letra e, através de bitfields, seja capaz de armazenar as seguintes informações SOBRE ELA (utilize a menor quantidade de espaço possível para representar cada informação; utilize 1 para verdadeiro e 0 para falso):
    1. Um valor correspondente a letra ( Ex.: a=0, b=1, c=2… ).
    2. Se a letra é vogal.
    3. Se a letra é maiúscula.
    4. Se a letra vem depois da letra M.
    5. Se a letra é a última ou a primeira do alfabeto.
    6. Se a letra possui uma letra vizinha que é vogal.
    7. O número de letras até a última letra do alfabeto.
  2. Sem utilizar a operação módulo (%), crie uma função capaz de calcular o módulo de um número por 2, por 4 ou por 16.
  3. Sem utilizar a operação de maior (>), crie uma função capaz de determinar se um número é maior que 7, 31 ou 63.
  4. Sem utilizar a operação de divisão, determine o resultado da operação de divisão de um número por 16 e o resto dessa divisão.
  5. Crie uma função capaz de dizer quantos bits “1” existem na representação binária de um determinado número.
  6. É possível descobrir se um número é uma potência de dois se este número possui apenas um bit 1 em sua representação binária. Crie uma função que indica quando um número é uma potência de dois.
1)
O mundo irá acabar antes…
prog2/operacoes_com_bits.txt · Última modificação: 2019/05/21 15:02 por maziero