Manipulação de bits

Versão para impressão

Manipulação de bits

• O que é manipulação de bits (em inglês: "bit twiddling")?

• Da Wikipedia:

  • "Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization."

Revisando bases numéricas

Revisando bases numéricas

• Dados numéricos podem ser representados através de várias bases:

  • Decimal
  • Binária
  • Hexadecimal
  • ...

• Uma base numérica é apenas uma forma de interpretar os dados, mas isso não altera o valor armazenado

  • Não existe um número "em base 10" que é diferente de um número "em base 2"

• Algumas bases são mais adequadas para programação em baixo nível

Revisando bases numéricas

Decimal

• Bom para humanos, ruim para programadores

• Experimente converter de decimal... para qualquer outra base!

  • Decimal para binário

  • Decimal para hexadecimal

  • ...

Revisando bases numéricas

Binário (base 2)

• Bom para computadores, ruim para todo o resto

  • ✔ Nos permite ver claramente como um computador armazena de fato um determinado valor

  • ☹ Mas você trabalharia com valores do tipo 11110000101011100001010011101100?

• Um pouco de terminologia:

  • LSB: least significant bit, i.e. o bit que contribui menos para o valor (menos significativo, bit 0)

  • MSB: most significant bit, i.e. o bit que contribui mais para o valor (mais significativo, bit 31)

Revisando bases numéricas

Hexadecimal (base 16)

• Oferece um bom equilíbrio entre a facilidade do decimal e a visão direta do binário

Revisando bases numéricas

Hexadecimal (cont.)

• Base 16 é uma potência de 2 (2⁴), portanto a conversão entre binário e hex é simples

• A partir do bit mais significativo, lê-se 4 bits de cada vez:

  binário: 1111 0000 1010 1110 0001 0100 1110 1100
  hex:       F    0    A    E    1    4    E    C

• O mesmo número em hex é: F0AE14EC

  • Mais curto que o número binário!
  • Mais legível que o número binário!

Revisando bases numéricas

De hex para decimal

• Converter de volta para decimal é simples:

Exercício: experimentando com conversões de base

• Para praticar conversões de base, podemos usar Python

• Python é uma excelente linguagem para prototipar aplicações com rapidez... ou para fazer cálculos simples

• Para executar o interpretador Python no Linux, digite o seguinte comando no shell:

  python

• Para sair do interpretador, pressione CTRL+D

Exercício: experimentando com conversões de base

• Para exibir o valor decimal a partir de uma entrada binária, use o prefixo "0b":

  >>> 0b1111
  15

• Para exibir o valor decimal a partir de uma entrada em hex, use o prefixo "0x":

  >>> 0xFF
  255

• Tente converter os seguintes números para decimal:

  >>> 0b10101010
  >>> 0x00FF
  >>> 0xF000
  >>> 0b11110000

Exercício: experimentando com conversões de base

• Para ver o número hex a partir de qualquer entrada, use a função hex():

  >>> hex(0b1111)
  '0xf'

• Outra forma é usar o comando print com o modificador de formato X:

  >>> print "{0:X}".format(0b1111)
  F

• Se você deseja obter um valor com dois dígitos, use 02X:

  >>> print "{0:02X}".format(0b1111)
  0F

Exercício: experimentando com conversões de base

• Um recurso útil é a função bin(), que converte qualquer coisa para binário:

  >>> bin(255)
  '0b11111111'

• Outra forma é usar o comando print com o modificador b:

  >>> print "{0:b}".format(15)
  1111

• Se você quiser, por exemplo, obter um byte completo, use 08b:

  >>> print "{0:08b}".format(15)
  00001111

Usando bases numéricas em C

• Em um programa C, você pode usar exatamente a mesma notação:

  unsigned int var;
  var = 254;         // decimal
  var = 0xFE;        // mesmo em hex
  var = 0b11111110   // mesmo em binário

• Obs: suporte para binário só está disponível no GCC 4.7+ e alguns outros compilador (não é padrão)

• Para exibir a saída em hex, use o modificador %X na função printf:

  printf("%02X\n", var);

• Obs: não existe modificador para exibir números em binário!

Entendendo o armazenamento de dados em C

• Podemos usar o operador sizeof para obter o tamanho em bytes de qualquer variável ou valor

• Por exemplo, supondo o seguinte programa:

   ...
   int main() {
       printf("sizeof(int)    = %d\n", sizeof (int));
       printf("sizeof(char)   = %d\n", sizeof(char));
       printf("sizeof(float)  = %d\n", sizeof(float));
       printf("sizeof(double) = %d\n", sizeof(double));
       return 0;
   }

• Você pode explicar a saída?

• sizeof é essencial para manipulação de bits, de forma que se possa saber qual é o bit mais significativo

Operadores bitwise

Operadores bitwise

• Operadores bitwise são aqueles que manipulam individualmente cada bit dos operandos

• Podem ser usados com valores inteiros: int, char, short int, long int, de preferência unsigned (e.g, unsigned int var)

• Dois tipos:

  • Operadores lógicos

  • Operadores de deslocamento

Operadores bitwise lógicos

• Aplicam operações lógicas usuais, mas bit a bit

  • AND

  • OR

  • NOT

  • XOR

AND bitwise

• Em C/Python: o operador &

• Exemplo:

• Tente no interpretador Python:

  x = 0b01001010
  y = 0b10010010
  print "{0:08b}".format(x & y)

OR bitwise

• Em C/Python: o operador |

• Exemplo:

• Tente no interpretador Python:

  x = 0b01001010
  y = 0b10010010
  print "{0:08b}".format(x | y)

XOR bitwise

• Em C/Python: o operador ^ (mesmo que OR, mas gera 0 se ambos forem 1)

• Exemplo:

• Tente no interpretador Python:

  x = 0b01001010
  y = 0b10010010
  print "{0:08b}".format(x ^ y)

NOT bitwise

• Em C/Python: o operador ~

• Exemplo:

• Tente no interpretador Python:

  x = 0b01001010
  print "{0:08b}".format(~x & 0xFF)

• O AND bitwise no final é apenas para garantir que teremos 8 bits no resultado

Operadores de deslocamento (shifting)

• Recebem este nome porque deslocam os bits para a direita ou para a esquerda

• Espaços "vazios" são preenchidos com zeros

• São particularmente úteis quando combinados com operadores lógicos (a seguir)

Shift para a esquerda

• Em C/Python: o operador <<

• Argumentos: valor a ser deslocado e quantidade de bits para deslocar para a esquerda (o valor original fica inalterado)

• Exemplo: considere x armazenando 23 (0x17):

  unsigned char x = 0x17;   // 23 em decimal
  unsigned char y = x << 1; // left shift por 1 bit
  // agora y armazenará 46 (0x2E)

• Deslocando vários bits de cada vez:

  y = x << 2; // y armazenará 92  (0x5C)
  y = x << 3; // y armazenará 184 (0xB8)

Shift para a direita

• Em C/Python: o operador >>

• Argumentos: valor a ser deslocado e quantidade de bits para deslocar para a direita (o valor original fica inalterado)

• Exemplo: considere x armazenando 23 (0x17):

  unsigned char x = 0x17;   // 23 em decimal
  unsigned char y = x >> 1; // shift right por 1 bit
  // agora y armazenará 11 (0x0B)

• Como antes, pode-se deslocar vários bits de cada vez:

  y = x >> 2; // y armazenará 5 (0x5)
  y = x >> 3; // y armazenará 2 (0x2) 

Exercício

• Using operadores lógicos e de deslocamento, tente imaginar como implementar as seguintes operações

• Cria uma função para cada uma (a função deve retornar o valor alterado):

  • Zera todos os bits: unsigned int clear(unsigned int val)
  • Seta um único bit: unsigned int setbit (unsigned int x, int bit)
  • Resseta um único bit: unsigned int clearbit (unsigned int x, int bit)
  • Inverte o valor de um único bit: unsigned int invertBit (unsigned int x, int bit)
  • Retorna o estado de um determinado bit: int testBit (unsigned int x, int bit) (retorna 0 ou 1)

Campos de bit

Campos de bit

• Denomina-se campo de bit ou palavra parcial (bit field, partial word) quando extraímos apenas um grupo de bits de uma palavra

• Por exemplo, suponha que desejamos armazenar uma cor através dos seus componentes RGB (red, green, blue)

  • Cada componente pode armazenar um valor de 0 a 1023 (1024 valores diferentes)

  • A solução mais simples é criar uma struct:

    typedef struct {
        int red;
        int green;
        int blue;
    } RGB;

  • Qual é o problema?

Primeira solução

• Quanto espaço precisamos para essa struct?

  typedef struct {
      int red;
      int green;
      int blue;
  } RGB;

  • 3 variáveis int * sizeof(int) = 3 * 4 = 12 bytes

• Mas isso é apenas UM ponto - e se tiveremos uma matriz de... 1024 x 768 pontos?

  • 1024 x 768 x 12 = 9437184 bytes ~ 9 Mb

• Dependendo da aplicação e do hardware, pode ser demais!

Segunda solução

• Agora tentaremos usar campos de bit:

  • 1024 = 2¹⁰, então precisamos pelo menos 10 bits por componente de cor

  • 3 componentes (R, G, B) x 10 bits = 30 bits

    • Red: bits 0 a 9
    • Green: bits 10 a 19
    • Blue: bits 20 a 29

  • Tudo caberia em um único int (e ainda teríamos 2 bits sem uso!)

    • 00000000000000000000000000000000

Operações comuns

• Mas como poderíamos...

  • Armazenar um valor específico no campo de bits do componente verde?

  • Extrair o valor dos campos de bits dos componentes vermelho ou azul?

  • ...?

Armazendo um valor em um campo de bits

• Exemplo: supondo que desejamos armazenar o valor 500 no campo de bits da componente verde

  • 500 é 0x1F4 (hex)

    unsigned int colour = ...; // algum valor inicial
    unsigned int newgreen = 0x1F4; // novo valor para armazenar no verde

• Primeiro, precisamos limpar os 10 bits "verdes"

  • Que operação lógica pode ser usada para zerar um conjunto de bits?

Zerando um campo de bits

• Um AND bitwise pode ser usado

• Precisamos de uma máscara, onde os bits desejados devem ser zeros

  • 00111111111100000000001111111111

• Primeiro criamos uma máscara com 10 bits setados:

  • 00000000000000000000001111111111

• Agora deslocamos para a esquerda por 10 bits:

  • 00000000000011111111110000000000

    unsigned int mask = 0x3FF << 10;

Zerando um campo de bits

• Finalmente, precisamos inverter a máscara, pois os bits do meio precisam ser ressetados

  • 00111111111100000000001111111111

• Para isso, usamos o operador NOT bitwise:

  unsigned int mask = ~mask;

Armazenando em um campo de bits

• Agora precisamos apenas deslocar o valor desejado à posição correta

• Isto significa que devemos deslocar newgreen à esquerda em 10 bits:

  • 00000000000000000000000111110100

    newgreen = newgreen << 10;

  • 00000000000001111101000000000000

Armazenando em um campo de bits

• E finalmente, para combinar com o valor atual precisamos:

  • Zerar os bits "verdes" com a máscara:

    colour = colour & mask;

  • Modificar os bits "verdes" com o newgreen deslocado:

    colour = colour | newgreen;

• Obs: se você souber exatamente o que está fazendo, é possível fazer tudo de uma vez só!

      colour = colour & ~(0x3FF << 10) | (newgreen << 10);

Exercícios

1. Crie um programa completo que defina uma varíavel colour como um unsigned int

   • Em uma repetição:

     • Mostre o valor atual na tela, em binário e hex

     • Permite ao usuário escolher o componente de cor desejado (red, green ou blue)

     • Pergunte o valor novo e armazene no campo de bits correto