@popCount em Zig

O @popCount (Population Count) conta o número de bits com valor 1 em um inteiro. Também conhecido como “Hamming weight”. Mapeia diretamente para instruções de CPU como POPCNT (x86), resultando em operação extremamente eficiente. Usado em bitboards, compressão, hashing e verificação de paridade.

Sintaxe

@popCount(value: T) Log2T

Parâmetros

• value (T): Valor inteiro cujos bits em 1 serão contados.

Valor de retorno

Retorna o número de bits com valor 1 no valor. Para um tipo de N bits, resultado varia de 0 a N.

Exemplos práticos

Exemplo 1: Contagem básica de bits

const std = @import("std");

pub fn main() void {
    std.debug.print("popCount(0b11001010) = {}\n", .{@popCount(@as(u8, 0b11001010))}); // 4
    std.debug.print("popCount(0xFF) = {}\n", .{@popCount(@as(u8, 0xFF))});             // 8
    std.debug.print("popCount(0) = {}\n", .{@popCount(@as(u8, 0))});                   // 0
    std.debug.print("popCount(7) = {}\n", .{@popCount(@as(u32, 7))});                  // 3
}

Exemplo 2: Verificar potência de 2

const std = @import("std");

fn ePotenciaDe2(valor: u64) bool {
    // Potências de 2 têm exatamente 1 bit ligado
    return valor != 0 and @popCount(valor) == 1;
}

pub fn main() void {
    std.debug.print("1 é pot2? {}\n", .{ePotenciaDe2(1)});     // true
    std.debug.print("16 é pot2? {}\n", .{ePotenciaDe2(16)});   // true
    std.debug.print("15 é pot2? {}\n", .{ePotenciaDe2(15)});   // false
    std.debug.print("1024 é pot2? {}\n", .{ePotenciaDe2(1024)}); // true
    std.debug.print("0 é pot2? {}\n", .{ePotenciaDe2(0)});     // false
}

Exemplo 3: Distância de Hamming

const std = @import("std");

fn distanciaHamming(a: u32, b: u32) u6 {
    // Distância de Hamming = número de bits diferentes
    return @popCount(a ^ b);
}

pub fn main() void {
    const d1 = distanciaHamming(0b1011101, 0b1001001);
    std.debug.print("Distância de Hamming: {}\n", .{d1}); // 2

    const d2 = distanciaHamming(0, 0xFF);
    std.debug.print("Distância 0 vs 0xFF: {}\n", .{d2}); // 8
}

Casos de uso comuns

1. Verificar potência de 2: Potências de 2 têm exatamente um bit em 1.
2. Distância de Hamming: Número de bits diferentes entre dois valores.
3. Paridade: Paridade é @popCount(x) % 2.
4. Bitboards: Contar peças em jogos de tabuleiro representados por bits.
5. Hashing: Função auxiliar em algoritmos de hash.

Considerações de desempenho

Em arquiteturas modernas com suporte à instrução POPCNT (x86-64 desde Nehalem/2008, ARM desde ARMv5), @popCount é compilado para uma única instrução de hardware com latência de 1 ciclo. O compilador Zig usa a instrução nativa quando disponível e recorre a uma implementação em software apenas em alvos sem suporte.

Para tipos maiores que o registrador nativo (ex: u128 em plataformas 64-bit), o compilador divide automaticamente em múltiplas operações, mantendo a correção.

Aplicações em bitboards

Bitboards são uma técnica usada em jogos de tabuleiro (xadrez, damas, Go) para representar o estado do tabuleiro como inteiros, onde cada bit corresponde a uma casa. @popCount é essencial para contar peças de forma extremamente eficiente:

const std = @import("std");

const Tabuleiro = struct {
    // Cada bit representa uma casa (8x8 = 64 casas)
    pecas_brancas: u64,
    pecas_pretas: u64,

    pub fn contarPecas(self: Tabuleiro) struct { brancas: u7, pretas: u7 } {
        return .{
            .brancas = @popCount(self.pecas_brancas),
            .pretas = @popCount(self.pecas_pretas),
        };
    }

    pub fn pecasAtivas(self: Tabuleiro) u7 {
        return @popCount(self.pecas_brancas | self.pecas_pretas);
    }
};

Comparação com equivalente em C

Em C moderno, o equivalente é __builtin_popcount (GCC/Clang) ou _mm_popcnt_u32 (MSVC com intrinsics):

// C: não-portável, dependente de compilador
#include <nmmintrin.h>
unsigned int n = __builtin_popcount(valor);    // GCC/Clang
unsigned int n = _mm_popcnt_u32(valor);       // MSVC x86

Em Zig, @popCount é portável, parte da linguagem, e o compilador garante o uso da instrução mais eficiente disponível no alvo:

// Zig: portável e idiomático
const n = @popCount(valor);

Erros comuns

1. Tipo de retorno inesperado: O tipo de retorno de @popCount é Log2T (o menor inteiro capaz de representar o número de bits). Para um u32, o retorno é u6 (porque 0..32 cabe em 6 bits). Isso pode causar surpresa ao tentar misturar com outros tipos:

const bits: u32 = @popCount(@as(u32, 0xFF)); // ERRO: tipo retornado é u6, não u32
const bits: u6 = @popCount(@as(u32, 0xFF));  // CORRETO
const bits = @as(u32, @popCount(@as(u32, 0xFF))); // Ou cast explícito

2. Confundir com contagem de zeros: @popCount conta bits em 1, não zeros. Para contar zeros, use N - @popCount(valor) onde N é o número de bits do tipo.

Perguntas Frequentes

P: @popCount funciona com tipos signed como i32?

R: Sim. Para tipos signed, os bits são contados da mesma forma — incluindo o bit de sinal. Um i8 com valor -1 (representado como 0b11111111) retorna 8.

P: É possível usar @popCount em comptime?

R: Sim. @popCount pode ser avaliado em tempo de compilação com valores conhecidos, útil para cálculos de tabelas e constantes estáticas.

P: Como implementar paridade usando @popCount?

R: Paridade par ocorre quando o número de bits em 1 é par: @popCount(x) % 2 == 0. Em hardware de comunicação serial, isso é usado para detecção de erros simples.

Builtins relacionados

• @clz — Contar zeros à esquerda
• @ctz — Contar zeros à direita
• @bitReverse — Inverter ordem dos bits
• @byteSwap — Inverter ordem dos bytes

Tutoriais relacionados

• Operações Bit a Bit em Zig
• Sistema de Tipos do Zig
• Introdução ao Zig