Operações com bits

Video desta aula

Neste módulo são abordadas técnicas para acessar e manipular bits. Elas são úteis para armazenar grandes quantidades de informação simples em pouco espaço, como vetores de flags ou inteiros com faixas de valores pequenas. O acesso a bits individuais também é útil em operações de baixo nível, envolvendo registradores, pacotes de rede ou portas de entrada/saída.

Ao construir programas que manipulem muitos dados, é importante escolher o tipo mais adequado para cada variável. Por exemplo, podemos definir uma estrutura de dados para armazenar datas/horas da seguinte forma:

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

Usando essa estrutura, cada variável do tipo date_t ocupa 24 bytes (6 inteiros de 4 bytes).

No entanto, usar int para os campos da estrutura é um desperdício, pois os valores armazenados são pequenos. Podemos usar tipos inteiros menores, como char e short:

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

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

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

O padding é necessário porque as variáveis inteiras deve estar “alinhadas” 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. O alinhamento se aplica às variáveis e aos campos internos das estruturas.

Entretanto, há espaço para economizar mais memória, pois os campos da estrutura não precisam usar toda a faixa de valores oferecida por seus tipos:

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.

O código abaixo apresenta os tamanhos das três estruturas:

struct-size.c

#include <stdio.h>
 
typedef struct
{
  unsigned int year, month, day, hour, min, sec ;
} date_t1 ;
 
typedef struct
{
  unsigned short year ;
  unsigned char  month, day ;
  unsigned char  hour, min, sec ;
} date_t2 ;
 
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_t3 ;
 
int main ()
{
  printf ("date_t1 ocupa %ld bytes\n", sizeof (date_t1)) ;
  printf ("date_t2 ocupa %ld bytes\n", sizeof (date_t2)) ;
  printf ("date_t3 ocupa %ld bytes\n", sizeof (date_t3)) ;
}

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.

Formato do float:

• sinal (1 bit)
• expoente (8 bits)
• mantissa (23 bits)

// extraído (e simplificado) de /usr/include/x86_64-linux-gnu/ieee754.h
 
union ieee754_float
{
  float f;
 
  /* This is the IEEE 754 single-precision format.  */
  struct
  {
    #if __BYTE_ORDER == __BIG_ENDIAN
    unsigned int negative:1;
    unsigned int exponent:8;
    unsigned int mantissa:23;
    #endif                          /* Big endian.  */
    #if __BYTE_ORDER == __LITTLE_ENDIAN
    unsigned int mantissa:23;
    unsigned int exponent:8;
    unsigned int negative:1;
    #endif                          /* Little endian.  */
  } ieee;
};

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.

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 (bitmask), na qual somente o bit a ser testado é verdadeiro.

Por exemplo: para verificar se o 4° bit de value está ativo, usa-se a máscara 0x8:

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

Para ativar um bit específico, efetua-se 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, usa-se a máscara 0x4:

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

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

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

A máscara de bits também pode ser gerada por deslocamentos:

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

O exemplo a seguir imprime os valores binários dos números de 0 a 255. Observe o teste para verificar se um determinado bit é 0 ou 1:

write-bits.c

#include <stdio.h>
 
int main ()
{
  short n, b ;
 
  // para os 256 primeiros inteiros
  for (n = 0; n < 256; n++)
  {
    printf ("%3d: ", n) ;
 
    // testa os 8 bits menos significativos
    for (b = 7; b >= 0 ; b--)
      // testa e imprime o b-ésimo bit
      n & ( 1<<b ) ? putchar ('1') : putchar ('0') ;
 
    putchar ('\n') ;
  }
}

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:

000100101111011010101100100001011001010101011111010100010101011...

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:

// declara um mapa de 12000 bits
char bitarray[BITNSLOTS (12000)] ;
 
// ativa o bit 23
BITSET (bitarray, 23) ;
 
// testa o bit 3451
if (BITTEST (bitarray, 3451))
{
  // ...
}

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