Ferramentas do usuário

Ferramentas do site


prog2:operacoes_com_bits

Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
prog2:operacoes_com_bits [2019/05/21 15:00]
maziero
prog2:operacoes_com_bits [2019/05/21 15:02] (atual)
maziero
Linha 1: Linha 1:
 +====== 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 2<​sup>​4</​sup>​ = 16), e assim por diante.
 +
 +Por exemplo, o //struct// abaixo permite armazenar um valor de data e hora:
 +
 +<code c>
 +typedef struct
 +{
 +  unsigned char  hour, min, sec ;
 +  unsigned char  month, day ;
 +  unsigned short year ;
 +} date_t ;
 +</​code>​
 +
 +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 ... 4000((O mundo irá acabar antes...)) |  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//:​
 +
 +<code c>
 +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 ;
 +</​code>​
 +
 +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:
 +
 +<code c>
 +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 ;
 +} ;
 +</​code>​
 +
 +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 [[https://​pt.wikipedia.org/​wiki/​IEEE_754|padrão IEEE 754]].
 +
 +<code c>
 +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
 +} ;
 +</​code>​
 +
 +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 [[https://​en.wikipedia.org/​wiki/​Endianness|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:
 +
 +<code c>
 +if ( value & 0x8 ) // 0x8 = 0000 1000 em binário
 +{
 +   ...
 +}
 +</​code>​
 +
 +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:
 +
 +<code c>
 +value = value | 0x4 ; // 0x4 = 0000 0100 em binário
 +value |= 0x4 ; // versão compacta
 +</​code>​
 +
 +Similarmente,​ para desativar o 3o bit da variável ''​value'': ​
 +
 +<​code>​
 +value = value & ~ 0x4 ; // explique!
 +</​code>​
 +
 +A máscara de bits também pode ser gerada por deslocamentos,​ caso ela não seja fixa:
 +
 +<code c>
 +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
 +}
 +</​code>​
 +
 +===== 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 [[http://​c-faq.com/​misc/​bitsets.html|questão 20.8 da FAQ de comp.lang.c]],​ foi realizada usando macros de preprocessador,​ para maior eficiência:​
 +
 +<code c>
 +#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
 +</​code>​
 +
 +Exemplos de uso dessa implementação:​
 +
 +<code c>
 +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
 +</​code>​
 +
 +===== Exercícios =====
 +
 +(sugeridos pelo monitor Eric Low Schmidt)
 +
 +  - 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):
 +    - 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.
 +  - 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.
 +  - Sem utilizar a operação de maior (>), crie uma função capaz de determinar se um número é maior que 7, 31 ou 63.
 +  - 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.
 +  - Crie uma função capaz de dizer quantos bits "​1"​ existem na representação binária de um determinado número.
 +  - É 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.
prog2/operacoes_com_bits.txt · Última modificação: 2019/05/21 15:02 por maziero