A manipulação de bits é uma habilidade essencial em C, especialmente em sistemas embarcados, drivers, protocolos de rede e otimizações de baixo nível. Nesta aula, vamos aprofundar técnicas avançadas para trabalhar com bits individuais em inteiros, utilizando operadores bit a bit (&, |, ^, ~, <<, >>). Dominar essas operações permite que você escreva código mais eficiente, compacto e com controle preciso sobre dados binários.

Vamos explorar como usar bits como flags booleanas, como criar macros para setar, limpar e alternar bits, como contar bits de forma eficiente e como aplicar essas técnicas em problemas reais. Cada seção incluirá exemplos práticos e explicações detalhadas para que você possa aplicar imediatamente.

Flags com bits

Flags são variáveis que armazenam múltiplos estados booleanos em bits individuais de um mesmo inteiro. Em vez de usar várias variáveis bool ou int, você pode usar um único inteiro (por exemplo, unsigned int ou uint8_t) e usar cada bit para representar uma condição. Isso economiza memória e permite manipular várias flags de uma só vez.

Por exemplo, em um sistema de permissões, cada bit pode representar uma permissão: bit 0 para leitura, bit 1 para escrita, bit 2 para execução. Usando operadores bit a bit, podemos verificar rapidamente se uma permissão está ativa.

#include <stdio.h>
#include <stdint.h>

// Definição das flags
#define FLAG_READ   (1U << 0)  // 0b0001
#define FLAG_WRITE  (1U << 1)  // 0b0010
#define FLAG_EXEC   (1U << 2)  // 0b0100

int main() {
    uint8_t permissions = 0;  // nenhuma permissão

    // Conceder leitura e execução
    permissions |= FLAG_READ | FLAG_EXEC;

    // Verificar se tem permissão de escrita
    if (permissions & FLAG_WRITE) {
        printf("Tem permissão de escrita\n");
    } else {
        printf("Não tem permissão de escrita\n");
    }

    // Verificar se tem permissão de leitura
    if (permissions & FLAG_READ) {
        printf("Tem permissão de leitura\n");
    }

    return 0;
}

Usar flags com bits é comum em APIs de sistemas operacionais, como as flags de abertura de arquivos (O_RDONLY, O_WRONLY, etc.) e em bibliotecas gráficas. A vantagem é que você pode combinar várias flags com | e testar com &, tornando o código legível e eficiente.

Set/clear/toggle

Operações básicas de manipulação de bits: definir (set) um bit, limpar (clear) um bit e alternar (toggle) um bit. Vamos ver como cada uma é feita usando operadores bit a bit.

  • Set (definir bit para 1): use | com uma máscara que tem 1 na posição desejada.
  • Clear (definir bit para 0): use & com uma máscara que tem 0 na posição desejada (e 1 nas demais).
  • Toggle (inverter bit): use ^ com uma máscara que tem 1 na posição desejada.

Vamos definir macros para facilitar essas operações:

#include <stdio.h>
#include <stdint.h>

#define BIT(n) (1U << (n))

#define SET_BIT(x, n)   ((x) |= BIT(n))
#define CLEAR_BIT(x, n) ((x) &= ~BIT(n))
#define TOGGLE_BIT(x, n) ((x) ^= BIT(n))

int main() {
    uint8_t value = 0b0000;

    SET_BIT(value, 2);  // agora 0b0100
    printf("Após set bit 2: %u\n", value);

    CLEAR_BIT(value, 2); // volta a 0b0000
    printf("Após clear bit 2: %u\n", value);

    TOGGLE_BIT(value, 3); // agora 0b1000
    printf("Após toggle bit 3: %u\n", value);

    return 0;
}

Essas macros são seguras se os argumentos forem expressões simples (sem efeitos colaterais). Em código crítico, considere usar funções inline ou operações diretas para evitar múltiplas avaliações. Por exemplo, SET_BIT(x++, 3) causaria comportamento indefinido.

Contagem de bits

Contar o número de bits 1 em um número é uma operação comum em algoritmos como criptografia, codificação e jogos. Existem várias técnicas, desde a mais simples (loop) até métodos mais rápidos usando tabelas ou operações aritméticas.

Método ingênuo: percorrer cada bit e contar.

int count_bits_naive(unsigned int x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

Método de Brian Kernighan: usa o truque x & (x-1) para limpar o bit mais baixo. O loop executa uma vez por bit 1.

int count_bits_kernighan(unsigned int x) {
    int count = 0;
    while (x) {
        x &= x - 1;
        count++;
    }
    return count;
}

Usando tabela de consulta: para números de 8 bits, podemos ter uma tabela pré-computada.

static const int lookup[256] = {
    // ... preenchido com contagens de 0 a 255
};

int count_bits_lookup(unsigned int x) {
    int count = 0;
    while (x) {
        count += lookup[x & 0xFF];
        x >>= 8;
    }
    return count;
}

Essa abordagem é muito rápida pois faz poucas iterações (1 por byte). Em sistemas embarcados, a tabela pode ser carregada em ROM.

Para números maiores, você pode usar a função intrínseca do compilador, como __builtin_popcount no GCC, que utiliza instruções de hardware quando disponíveis:

#include <stdio.h>

int main() {
    unsigned int x = 0b101101;
    printf("Número de bits 1: %d\n", __builtin_popcount(x));
    return 0;
}

No C padrão (C23), a função stdc_count_ones pode ser usada de forma portátil, mas ainda não está amplamente disponível.

Casos de uso

A manipulação de bits avançada é amplamente utilizada em:

  • Sistemas embarcados: controlar pinos de microcontroladores, ler sensores, configurar registradores de hardware.
  • Protocolos de rede: extrair campos de cabeçalhos de pacotes, onde informações são compactadas em bits.
  • Compressão de dados: algoritmos como Huffman usam manipulação de bits para codificar símbolos.
  • Grafos e estruturas de dados: usar bitsets para representar conjuntos e fazer operações como interseção e união rapidamente.
  • Otimização de desempenho: substituir multiplicações/divisões por potências de 2 por shifts, e usar máscaras para extrair campos.

Um exemplo prático: extrair os campos de um endereço IP ou de um cabeçalho IPv4. O cabeçalho contém campos como versão (4 bits), IHL (4 bits), etc. Podemos usar máscaras e shifts para extraí-los.

#include <stdio.h>
#include <stdint.h>

int main() {
    uint32_t header = 0x45000028; // exemplo: versão 4, IHL 5, total length 40

    // Versão: primeiros 4 bits
    uint8_t version = (header >> 28) & 0xF;
    // IHL: próximos 4 bits
    uint8_t ihl = (header >> 24) & 0xF;
    // Total length: 16 bits
    uint16_t total_len = (header >> 16) & 0xFFFF;

    printf("Versão: %u, IHL: %u, Total length: %u\n", version, ihl, total_len);
    return 0;
}

Outro caso é usar bits como flags em um sistema de eventos, onde cada bit representa um tipo de evento e podemos verificar rapidamente se um conjunto de eventos ocorreu.

Boas práticas e observações finais

Ao manipular bits, sempre use tipos sem sinal (unsigned) para evitar problemas com o bit de sinal e deslocamentos à direita. Prefira usar constantes com sufixo U para evitar warnings. Documente o significado de cada bit com defines ou enums. Teste exaustivamente, pois erros de bit são sutis. Considere usar funções intrínsecas do compilador para operações comuns como contagem de bits. Sempre que possível, use a menor quantidade de bits necessária, mas com atenção à portabilidade.

Exercícios

  1. Escreva uma função que verifica se um número é potência de 2 usando manipulação de bits. A função deve retornar 1 se for potência de 2, 0 caso contrário. Dica: use o truque x & (x-1).

    2. ✓ Resposta:
    int is_power_of_two(unsigned int x) {
    return x && !(x & (x - 1));
}
  2. Implemente uma função que rotaciona os bits de um número inteiro para a esquerda por n posições. A rotação deve ser circular, ou seja, os bits que saem pela esquerda entram pela direita. Teste com exemplos.

    3. ✓ Resposta:
    unsigned int rotate_left(unsigned int x, int n) {
    int bits = sizeof(x) * 8;
    n %= bits;
    return (x << n) | (x >> (bits - n));
}
  3. Dado um inteiro de 32 bits, escreva uma função que extrai um campo de bits de largura L começando na posição p (da direita para esquerda, p=0 é o bit menos significativo). Retorne o valor do campo como inteiro sem sinal.

    4. ✓ Resposta:
    unsigned int get_bits(unsigned int x, int p, int L) {
    return (x >> p) & ((1U << L) - 1);
}
  4. Escreva uma função que inverte os bits de um número (reflexão). Por exemplo, para 0b1101 (13) deve retornar 0b1011 (11). Use um loop ou uma técnica mais eficiente.

    5. ✓ Resposta:
    unsigned int reverse_bits(unsigned int x) {
    unsigned int result = 0;
    int bits = sizeof(x) * 8;
    for (int i = 0; i < bits; i++) {
        result = (result << 1) | (x & 1);
        x >>= 1;
    }
    return result;
}
  5. Usando a contagem de bits, implemente uma função que calcula a distância de Hamming entre dois inteiros (número de bits em que eles diferem).

    6. ✓ Resposta:
    int hamming_distance(unsigned int a, unsigned int b) {
    unsigned int xor = a ^ b;
    int count = 0;
    while (xor) {
        xor &= xor - 1;
        count++;
    }
    return count;
}

Referências