Na computação de baixo nível, determinar a quantidade de bits definidos como "1" (conhecido como Hamming Weight) em um número inteiro é uma tarefa fundametnal, com aplicações que variam de criptografia a algoritmos de compressão. Veremos como resolver esse problema de forma eficiente, evoluindo de uma abordagem básica para uma solução otimizada utilizando programação dinâmica e manipulação de bits.

Abordagem de Complexidade O(log n)

A maneira mais intuitiva de contar os bits ativos é percorrer o número binário da direita para a esquerda, verificando o bit menos significativo em cada iteração.

Considere os seguintes exemplos:

• O número 3 em binário é 011 (2 bits ativos).
• O número 4 em binário é 100 (1 bit ativo).
• O número 7 em binário é 111 (3 bits ativos).

Para implementar isso, podemos utilizar o operador de deslocamento (shift) e o operador de módulo (ou AND binário):

int calcularBitsAtivos(int valor) {
    int soma = 0;
    while (valor > 0) {
        // Verifica se o bit atual é 1
        if (valor % 2 == 1) {
            soma++;
        }
        // Desloca um bit para a direita
        valor >>= 1;
    }
    return soma;
}

Nesta implementação, o tempo de execução é proporcional ao número de bits necessários para representar o valor, resultando em uma complexidade O(log n). Se precisarmos aplicar essa função para todos os números de 1 até N, a complexidade total subiria para O(n log n).

Otimização para Itnervalos com Complexidade O(n)

Quando o objetivo é calcular a quantidade de bits para uma sequência de números (de 1 a N), podemos utilizar uma propriedade matemática da manipulação de bits para evitar cálculos redundantes. A expressão chave é:

resultado = x & (x - 1);

O efeito da operação x & (x - 1) é a remoção do bit "1" menos significativo do número x. Por exemplo, se x for 6 (110 em binário), x - 1 será 5 (101). A operação 110 & 101 resulta em 100 (4). Note que o último bit "1" desapareceu.

Com base nisso, podemos formular que o número de bits de i é igual ao número de bits de i & (i - 1) mais um. Isso nos permite construir uma solução de Programação Dinâmica onde cada estado depende de um valor já calculado.

#include <stdio.h>

void gerarContagemBits(int limite) {
    int memoria[limite + 1];
    memoria[0] = 0; // Caso base: zero tem zero bits ativos

    printf("Resultados:\n");
    for (int i = 1; i <= limite; i++) {
        // O número de bits de 'i' é o número de bits de 'i' sem o seu bit mais baixo + 1
        memoria[i] = memoria[i & (i - 1)] + 1;
        printf("Número %d: %d bits\n", i, memoria[i]);
    }
}

int main() {
    int n = 10; 
    gerarContagemBits(n);
    return 0;
}

Nesta versão, percorremos o intervalo de 1 a N apenas uma vez. Como cada operação interna (o acesso ao array e a manipulação de bits) ocorre em tempo constante O(1), a complexidade total do algoritmo é reduzida para O(n). Esta abordagem é extremamente eficiente para processar grandes volumes de dados ou preencher tabelas de consulta (lookup tables) em sistemas de alto desempenho.