O processamento de dados ao nível de bits é uma técnica fundamental em computação de baixo nível e programação competitiva. Compreender como convertre bases numéricas e manipular bits individualmente permite otimizações significativas de memória e performance.

Conversão de Decimal para Binário

Existem diversas abordagens para convreter um número inteiro em sua representação binária. Uma das formas mais eficientes utiliza o deslocamento de bits (bit shifting) para verificar cada posição individualmente.

#include <iostream>
#include <vector>

void imprimirBinario(int valor) {
    // Array para armazenar os bits (32 bits para um int padrão)
    for (int i = 31; i >= 0; i--) {
        int bit = (valor >> i) & 1;
        std::cout << bit;
    }
    std::cout << std::endl;
}

int main() {
    int entrada;
    if (std::cin >> entrada) {
        imprimirBinario(entrada);
    }
    return 0;
}

Outro método comum utiliza divisões sucessivas por 2, o que é útil quando se deseja aramzenar os bits em um array para manipulação posterior:

#include <vector>

std::vector<int> converterParaBinario(int n) {
    std::vector<int> bits;
    if (n == 0) bits.push_back(0);
    while (n > 0) {
        bits.push_back(n % 2);
        n /= 2;
    }
    return bits; // Note: os bits estarão na ordem inversa
}

Conversão de Binário para Decimal

Para transformar uma sequência de bits de volta em um valor inteiro, percorremos o array multiplicando cada bit pela sua respectiva potência de 2.

long long binarioParaDecimal(const std::vector<int>& bits) {
    long long resultado = 0;
    for (size_t i = 0; i < bits.size(); ++i) {
        if (bits[i] == 1) {
            resultado += (1LL << i);
        }
    }
    return resultado;
}

Propriedades da Operação XOR (OU Exclusivo)

A operação XOR (^) possui propriedades matemáticas únicas, como a ^ a = 0 e a ^ 0 = a. Isso a torna ideal para algoritmos de criptografia simples e resolução de problemas de lógica.

Exemplo: Localizando um Número Ausente

Dado um array contendo uma sequência de 1 a N, onde um número foi removido e a ordem foi alterada, podemos encontrar o elemento faltante usando XOR em tempo linear O(n) e espaço constante O(1).

#include <iostream>

int encontrarElementoFaltante(int arr[], int tamanho) {
    int xorTotal = 0;
    
    // XOR de todos os números que deveriam existir (1 até tamanho + 1)
    for (int i = 1; i <= tamanho + 1; ++i) {
        xorTotal ^= i;
    }
    
    // XOR de todos os elementos presentes no array
    for (int i = 0; i < tamanho; ++i) {
        xorTotal ^= arr[i];
    }
    
    return xorTotal;
}

int main() {
    int dados[] = {1, 2, 3, 5, 6}; // O número 4 está faltando
    std::cout << "Número ausente: " << encontrarElementoFaltante(dados, 5) << std::endl;
    return 0;
}

Truques Rápidos de Manipulação de Bits

Abaixo estão listadas operações frequentes para manipular bits específicos de um número x na posição k (considerando k=1 como o bit menos significativo):

• Inverter o último bit: x ^ 1
• Inverter o k-ésimo bit: x ^ (1 << (k - 1))
• Definir o k-ésimo bit como 1: x | (1 << (k - 1))
• Definir o k-ésimo bit como 0: x & ~(1 << (k - 1))
• Inverter os últimos k bits: x ^ ((1 << k) - 1)

Uso da Classe std::bitset em C++

A biblioteca padrão do C++ oferece o std::bitset, uma estrutura otimizada para lidar com coleções de bits fixas. Ele fornece métodos integrados que facilitam a manipulação e visualização de dados binários.

#include <iostream>
#include <bitset>
#include <string>

int main() {
    // Inicialização
    std::bitset<8> bits1(42); // De um inteiro
    std::bitset<8> bits2("101010"); // De uma string
    
    std::cout << "Representação de 42: " << bits1 << std::endl;

    // Métodos úteis
    std::cout << "Quantidade de bits ativos (1): " << bits1.count() << std::endl;
    std::cout << "Tamanho do bitset: " << bits1.size() << std::endl;
    std::cout << "Existe algum bit em 1? " << (bits1.any() ? "Sim" : "Não") << std::endl;
    std::cout << "Todos os bits são 0? " << (bits1.none() ? "Sim" : "Não") << std::endl;

    // Modificação
    bits1.set(0);    // Define o bit 0 como 1
    bits1.reset(1);  // Define o bit 1 como 0
    bits1.flip();    // Inverte todos os bits
    
    // Acesso e Conversão
    bool status = bits1.test(3); // Verifica se o bit 3 está ativo
    unsigned long valorNumerico = bits1.to_ulong();
    
    std::cout << "Valor final: " << valorNumerico << std::endl;

    return 0;
}

O bitset é particularmente útil em algoritmos de Grafos (como o Fecho Transitivo de Warshall) e problemas de compressão de estado, onde o uso de memória precisa ser minimizado.