Determinar o número de bits '1' (também conhecidos como bits setados ou popcount) em um número binário é uma operação fundamental em diversas áreas da computação, desde criptografia e processamento de imagens até otimização de algoritmos. Este artigo explora duas abordagens avançadas para realizar essa contagem de forma eficiente, utilizando manipulações de bits.

Algoritmo Paralelo (Soma em Árvore)

Este método, muitas vezes chamado de "soma em árvore" ou algoritmo paralelo, funciona dividindo o número em grupos de bits e somando os bits setados dentro de cada grupo recursivamente. A cada passo, o tamanho dos grupos é dobrado, até que o resultado final seja a soma total de todos os bits '1'.

unsigned int contarBitsParalelo(unsigned int num) {
    // Passo 1: Soma bits em pares (2 bits por grupo). Ex: ...DCBA -> (...(D+C))(B+A)
    // A máscara 0x55555555 isola bits em posições ímpares (0, 2, 4, ...).
    // O deslocamento e a máscara permitem somar o bit em posição 'i' com o bit em 'i+1'.
    num = (num & 0x55555555) + ((num >> 1) & 0x55555555);
    
    // Passo 2: Soma grupos de 4 bits. Ex: ... (DC)(BA) -> (...(DC+BA))
    // A máscara 0x33333333 isola grupos de 2 bits em posições específicas.
    num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
    
    // Passo 3: Soma grupos de 8 bits
    // A máscara 0x0F0F0F0F isola grupos de 4 bits.
    num = (num & 0x0F0F0F0F) + ((num >> 4) & 0x0F0F0F0F);
    
    // Passo 4: Soma grupos de 16 bits (para 32-bit unsigned int)
    // A máscara 0x00FF00FF isola grupos de 8 bits.
    num = (num & 0x00FF00FF) + ((num >> 8) & 0x00FF00FF);
    
    // Passo 5: Soma grupos de 32 bits (para 32-bit unsigned int)
    // A máscara 0x0000FFFF isola grupos de 16 bits.
    num = (num & 0x0000FFFF) + ((num >> 16) & 0x0000FFFF);

    return num; // O resultado final na parte menos significativa
}

Princípio de Funcionamento Detalhado

O algoritmo opera em múltiplos estágios, cada um realizando uma soma paralela de bits. O padrão num = (num & MASK) + ((num >> SHIFT) & MASK) é fundamental. A máscara (MASK) após o deslocamento (SHIFT) é crucial para garantir que as somas dos bits de um grupo não se "espalhem" para o grupo adjacente.

Vamos ilustrar com um número de 8 bits, num = 01100001 (97 decimal), que possui 3 bits setados.

Número Inicial:

num = 01100001

1. Após o Passo 1 (Soma de pares de bits):

num = (num & 0x55) + ((num >> 1) & 0x55);

• num & 0x55 (01010101): 01000001 (isolando bits nas posições 0, 2, 4, 6)

• (num >> 1) & 0x55 (01010101):

  • 01100001 >> 1 resulta em 00110000
  • 00110000 & 0x55 (01010101) resulta em 00010000 (isolando e deslocando bits das posições 1, 3, 5, 7)

• Soma: 01000001 + 00010000 = 01010001. Neste ponto, num é 01010001. Interpretando em grupos de 2 bits, cada grupo agora contém a soma de bits '1' de seu par original:

  • 01 (esquerda): (do original 01) → 1 bit setado
  • 01: (do original 10) → 1 bit setado
  • 00: (do original 00) → 0 bits setados
  • 01 (direita): (do original 01) → 1 bit setado

  Representação conceitual das contagens: [1][1][0][1].

2. Após o Passo 2 (Soma de grupos de 4 bits):

num = (num & 0x33) + ((num >> 2) & 0x33);

• num atual: 01010001

• num & 0x33 (00110011): 00010001

• (num >> 2) & 0x33 (00110011):

  • 01010001 >> 2 resulta em 00010100
  • 00010100 & 0x33 (00110011) resulta em 00010000

• Soma: 00010001 + 00010000 = 00100001. Agora, num é 00100001. Interpretando em grupos de 4 bits:

  • 0010 (esquerda): (soma de [1][1]) → 2 bits setados
  • 0001 (direita): (soma de [0][1]) → 1 bit setado

  Representação conceitual das contagens: [2][1].

3. Após o Passo 3 (Soma de grupos de 8 bits):

num = (num & 0x0F) + ((num >> 4) & 0x0F);

• num atual: 00100001
• num & 0x0F (00001111): 00000001
• (num >> 4) & 0x0F (00001111):
  • 00100001 >> 4 resulta em 00000010
  • 00000010 & 0x0F (00001111) resulta em 00000010
• Soma: 00000001 + 00000010 = 00000011. O resultado final é 00000011, que é 3 em decimal. Corretamente, 01100001 tem 3 bits setados.

Para números de 16 ou 32 bits, as etapas adicionais simplesmente continuam esse processo de soma em árvore para cobrir toda a largura do inteiro.

Método da Propriedade Modular (Perpect Method)

Esta abordagem utiliza uma combinação inteligente de manipulações de bits e uma propriedade da aritmética modular para somar os bits setados de forma muito compacta e eficiente, frequentemente vista em bibliotecas de alto desempenho.

// Macro para calcular a soma de bits '1' em cada nibble (4 bits)
#define DECODIFICA_BITS_4X(x) \
    ((x) - (((x) >> 1) & 0x77777777) \
         - (((x) >> 2) & 0x33333333) \
         - (((x) >> 3) & 0x11111111))

unsigned int contarBitsModular(unsigned int num) {
    // Primeiro, calcula a soma dos bits '1' em cada grupo de 4 bits (nibble)
    unsigned int somas_nibbles = DECODIFICA_BITS_4X(num);
    
    // Em seguida, acumula as somas dos nibbles e usa a propriedade modular
    // (somas_nibbles >> 4) efetua uma soma paralela de nibbles.
    // & 0x0F0F0F0F garante que cada byte contenha a soma no nibble inferior.
    // % 255 finaliza a soma de todos os bytes.
    return ((somas_nibbles + (somas_nibbles >> 4)) & 0x0F0F0F0F) % 255;
}

Aálise do DECODIFICA_BITS_4X

A macro DECODIFICA_BITS_4X é projetada para calcular a contagem de bits '1' para cada nibble (4 bits) independentemente dentro de um inteiro de 32 bits. Considere um único nibble N = 8a + 4b + 2c + d, onde a, b, c, d são os bits (0 ou 1) de N. Nosso objetivo é calcular a + b + c + d. A macro faz o seguinte:

N                       = 8a + 4b + 2c + d
- ((N >> 1) & 0x7)     = -(4a + 2b + c)
- ((N >> 2) & 0x3)     = -(2a + b)
- ((N >> 3) & 0x1)     = -(a)
--------------------------------------
Resultado               = a + b + c + d

• (N >> 1) & 0x7: Desloca N um bit para a direita (removendo d) e aplica a máscara 0x7 (0111) para isolar os 3 bits restantes. Isso resulta em 4a + 2b + c.
• (N >> 2) & 0x3: Desloca N dois bits para a direita (removendo c e d) e aplica a máscara 0x3 (0011) para isolar os 2 bits restantes. Isso resulta em 2a + b.
• (N >> 3) & 0x1: Desloca N três bits para a direita (removendo b, c e d) e aplica a máscara 0x1 (0001) para isolar o bit mais significativo. Isso resulta em a.

Ao subtrair essas parcelas de N, o resultado algébrico é a + b + c + d. As máscaras 0x77777777, 0x33333333 e 0x11111111 são simplesmente extensões dessas máscaras de nibble para cobrir todos os 32 bits, garantindo que a operação seja aplicada a cada nibble de forma independente.

Após a execução de somas_nibbles = DECODIFICA_BITS_4X(num);, cada nibble em somas_nibbles contém a contagem de bits '1' do nibble correspondente do número original num.

A Mágica do % 255

A etapa final da função contarBitsModular é return ((somas_nibbles + (somas_nibbles >> 4)) & 0x0F0F0F0F) % 255;

Primeiro, (somas_nibbles + (somas_nibbles >> 4)) & 0x0F0F0F0F realiza uma soma parallea similar ao algoritmo anterior, acumulando as contagens de nibbles em grupos de 8 bits. O resultado é um número onde cada byte (de 8 bits) contém a soma dos bits '1' de seus respectivos nibbles. Por exemplo, se o número original tinha 3 bits '1' no primeiro byte e 2 bits '1' no segundo, esta etapa resultaria em 0x0302....

O truque final está na operação de módulo % 255. A propriedade da aritmética modular afirma que N % (2^k - 1) é equivalente a somar as "partes" de N em base 2^k e aplicar o módulo novamente. Para k=8, temos 2^8 - 1 = 255. Considere um número X que é uma concatenação de bytes A, B, C, D (representando as somas dos bits '1' para cada byte), ou seja, X = A * (2^8)^3 + B * (2^8)^2 + C * (2^8)^1 + D.

Como 2^8 ≡ 1 (mod 255), podemos simplificar a expressão modular:

X % 255 = (A * (2^8)^3 + B * (2^8)^2 + C * (2^8)^1 + D) % 255
        = (A * 1^3 + B * 1^2 + C * 1^1 + D) % 255
        = (A + B + C + D) % 255

Isso significa que a operação % 255 soma todas as contagens de bits '1' que estão armazenadas em cada byte do número. Como a contagem máxima de bits '1' para um unsigned int de 32 bits é 32, e 32 é menor que 255, o resultado final do módulo é simplesmente a soma total dos bits '1', sem qualquer "enrolamento" da operação modular.