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, 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.

É possível fazermos 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..12      4   
year   unsigned short   16         0..3000   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 ;  // 12 = ceil( log(3000) )
  unsigned char  month:4 ;  //  4 = ceil( log(12) )
  unsigned char  day:5 ;    //  5 = ceil( log(31) )
  unsigned char  hour:5 ;   //  5 = ceil( log(24) )
  unsigned char  min:6 ;    //  6 = ceil( log(60) )
  unsigned char  sec:6 ;    //  6 = ceil( log(60) )
} 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 ;         // TRUE/FALSE
     unsigned error_occured:1 ; // TRUE/FALSE
     unsigned disk_spinning:1 ; // TRUE/FALSE
     unsigned write_protect:1 ; // TRUE/FALSE
     unsigned head_loaded:1 ;   // TRUE/FALSE
     unsigned error_code:8 ;    // 256 erros
     unsigned track:9 ;         // 512 trilhas 
     unsigned sector:5 ;        // 32 setores
     unsigned command:5 ;       // 32 comandos
};

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  (MIPS)
    unsigned int negative:1 ;
    unsigned int exponent:8 ;
    unsigned int mantissa:23 ;
#endif
#if __BYTE_ORDER == __LITTLE_ENDIAN  (x86)
    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 é 1.

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 ligar 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 desligar 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 ;   // liga 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, no qual cada bit individual pode ser lido ou definido como 0 ou 1.

Estruturas de bitmaps são muito úteis para representar conjuntos. Por 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);                   // ligar  o bit 23
if (BITTEST(bitarray, 35)) { ... }      // testar o bit 35

Exercícios

(sugeridos pelo monitor Eric Low Schmidt)

1. Projete uma estrutura para analisar uma letra, e através de bitfields, armazene 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):
   • um valor correspondente a letra (Ex.: a=0, b=1, c=2... );
   • se a letra é vogal;
   • se a letra é maiúscula;
   • se a letra vem depois da letra M;
   • se a letra é a última ou a primeira do alfabeto;
   • se a letra possui uma letra vizinha que é vogal;
   • o número de letras até a última letra do alfabeto.

2. Sem utilizar a operação módulo (%), escreva uma função que calcula o módulo de um número por 2, por 4 ou por 16.

3. Sem utilizar a operação de maior (>), escreva uma função que determina se um número é maior que 7, 31 ou 63.

4. Sem utilizar a operação de divisão, escreva uma função que determina o resultado da operação de divisão de um número por 16 e o resto dessa divisão.

5. Escreva uma função que determine 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. Escreva uma função que indica quando um número é uma potência de dois.