Diferenças

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

--- c:operacoes_com_bits [2023/08/01 18:12] – criada maziero
+++ c:operacoes_com_bits [2023/08/01 20:16] (atual) – edição externa 127.0.0.1
@@ Linha 1: / Linha 1: @@
+====== Operações com bits ======
+{{ progc_bits.mkv |Video desta aula}}
+{{ bits.png?96|http://www.freepik.com}} 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.
+===== Bit fields =====
+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:
+<code c>
+typedef struct
+{
+  unsigned int year, month, day, hour, min, sec ;
+} date_t ;
+</code>
+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'':
+<code c>
+typedef struct
+{
+  unsigned short year ;
+  unsigned char  month, day ;
+  unsigned char  hour, min, sec ;
+} date_t ;
+</code>
+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:
+^ campo ^ faixa ^ bits necessários ^
+|  ''year''  |  0 ... 4000((O mundo irá acabar antes...))  |  12  |
+|  ''mon''  |  0 ... 11  |  4  |
+|  ''day''  |  0 ... 31  |  5  |
+|  ''hour''  |  0 ... 23  |  5  |
+|  ''min''  |  0 ... 59  |  6  |
+|  ''sec''  |  0 ... 59  |  6  |
+|  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.
+O código abaixo apresenta os tamanhos das três estruturas:
+<code c 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)) ;
+}
+</code>
+//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]].
+Formato do ''float'':
+  * sinal (1 bit)
+  * expoente (8 bits)
+  * mantissa (23 bits)
+<code c>
+// 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;
+};
+</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 (//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'':
+<code c>
+if ( value & 0x8 )		// 0x8 = 0000 1000 em binário
+{
+   ...
+}
+</code>
+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'':
+<code c>
+value = value | 0x4 ;		// 0x4 = 0000 0100 em binário
+value |= 0x4 ; 			// versão compacta
+</code>
+Similarmente, para desativar o 3° bit da variável ''value'':
+<code>
+value = value & ~ 0x4 ;		// explique!
+</code>
+A máscara de bits também pode ser gerada por deslocamentos:
+^  bit  ^  máscara  ^  hexa  ^  deslocamento ^
+|  0  |  0000 0001  |  ''0x1''  |  ''1<<0''  |
+|  1  |  0000 0010  |  ''0x2''  |  ''1<<1''  |
+|  2  |  0000 0100  |  ''0x4''  |  ''1<<2''  |
+|  3  |  0000 1000  |  ''0x8''  |  ''1<<3''  |
+|  4  |  0001 0000  |  ''0x10''  |  ''1<<4''  |
+|  5  |  0010 0000  |  ''0x20''  |  ''1<<5''  |
+|  6  |  0100 0000  |  ''0x40''  |  ''1<<6''  |
+|  7  |  1000 0000  |  ''0x80''  |  ''1<<7''  |
+<code c>
+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
+}
+</code>
+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:
+<code c 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') ;
+  }
+}
+</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:
+  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 [[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>
+// 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))
+{
+  // ...
+}
+</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.