BitSet representando o conjunto {0, 2, 5, 7, 10, 15}:

Bits:   1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1
Índice: 0 1 2 3 4 5 6 7 8 9 10 . . . 15

Armazenamento em u64:
  Palavra 0: 0b1000_0100_1010_0101 = {0,2,5,7,10,15}

Operações bitwise em palavras inteiras:
  A ∪ B = A | B  (união)
  A ∩ B = A & B  (interseção)
  A \ B = A & ~B (diferença)
  A △ B = A ^ B  (diferença simétrica)

const std = @import("std");
const Allocator = std.mem.Allocator;

/// BitSet de tamanho fixo (comptime).
pub fn BitSet(comptime tamanho_max: usize) type {
    const num_palavras = (tamanho_max + 63) / 64;

    return struct {
        const Self = @This();

        palavras: [num_palavras]u64,
        contagem_bits: usize,

        pub fn init() Self {
            return .{
                .palavras = [_]u64{0} ** num_palavras,
                .contagem_bits = 0,
            };
        }

        /// Define o bit na posição dada.
        pub fn definir(self: *Self, pos: usize) void {
            std.debug.assert(pos < tamanho_max);
            const palavra = pos / 64;
            const bit: u6 = @intCast(pos % 64);
            if ((self.palavras[palavra] >> bit) & 1 == 0) {
                self.palavras[palavra] |= @as(u64, 1) << bit;
                self.contagem_bits += 1;
            }
        }

        /// Limpa o bit na posição dada.
        pub fn limpar(self: *Self, pos: usize) void {
            std.debug.assert(pos < tamanho_max);
            const palavra = pos / 64;
            const bit: u6 = @intCast(pos % 64);
            if ((self.palavras[palavra] >> bit) & 1 == 1) {
                self.palavras[palavra] &= ~(@as(u64, 1) << bit);
                self.contagem_bits -= 1;
            }
        }

        /// Alterna o bit na posição dada.
        pub fn alternar(self: *Self, pos: usize) void {
            std.debug.assert(pos < tamanho_max);
            const palavra = pos / 64;
            const bit: u6 = @intCast(pos % 64);
            const era_set = (self.palavras[palavra] >> bit) & 1 == 1;
            self.palavras[palavra] ^= @as(u64, 1) << bit;
            if (era_set) {
                self.contagem_bits -= 1;
            } else {
                self.contagem_bits += 1;
            }
        }

        /// Verifica se o bit está definido.
        pub fn contem(self: *const Self, pos: usize) bool {
            if (pos >= tamanho_max) return false;
            const palavra = pos / 64;
            const bit: u6 = @intCast(pos % 64);
            return (self.palavras[palavra] >> bit) & 1 == 1;
        }

        /// Número de bits definidos.
        pub fn contagem(self: *const Self) usize {
            return self.contagem_bits;
        }

        /// Conta bits definidos (via popcount — mais confiável).
        pub fn popcountTotal(self: *const Self) usize {
            var total: usize = 0;
            for (self.palavras) |p| {
                total += @popCount(p);
            }
            return total;
        }

        /// União (OR) — modifica self.
        pub fn uniao(self: *Self, outro: *const Self) void {
            for (&self.palavras, outro.palavras) |*a, b| {
                a.* |= b;
            }
            self.recalcularContagem();
        }

        /// Interseção (AND) — modifica self.
        pub fn intersecao(self: *Self, outro: *const Self) void {
            for (&self.palavras, outro.palavras) |*a, b| {
                a.* &= b;
            }
            self.recalcularContagem();
        }

        /// Diferença (A \ B) — modifica self.
        pub fn diferenca(self: *Self, outro: *const Self) void {
            for (&self.palavras, outro.palavras) |*a, b| {
                a.* &= ~b;
            }
            self.recalcularContagem();
        }

        /// Diferença simétrica (XOR) — modifica self.
        pub fn diferencaSimetrica(self: *Self, outro: *const Self) void {
            for (&self.palavras, outro.palavras) |*a, b| {
                a.* ^= b;
            }
            self.recalcularContagem();
        }

        /// Verifica se é subconjunto de outro.
        pub fn ehSubconjunto(self: *const Self, outro: *const Self) bool {
            for (self.palavras, outro.palavras) |a, b| {
                if (a & ~b != 0) return false;
            }
            return true;
        }

        /// Limpa todos os bits.
        pub fn limparTudo(self: *Self) void {
            @memset(&self.palavras, 0);
            self.contagem_bits = 0;
        }

        fn recalcularContagem(self: *Self) void {
            self.contagem_bits = self.popcountTotal();
        }

        /// Iterador sobre bits definidos.
        pub fn iterador(self: *const Self) Iterador {
            return .{ .bitset = self, .pos = 0 };
        }

        pub const Iterador = struct {
            bitset: *const Self,
            pos: usize,

            pub fn next(self: *Iterador) ?usize {
                while (self.pos < tamanho_max) {
                    const p = self.pos;
                    self.pos += 1;
                    if (self.bitset.contem(p)) return p;
                }
                return null;
            }
        };

        /// Formata como conjunto {1, 3, 5}.
        pub fn imprimir(self: *const Self, writer: anytype) !void {
            try writer.writeAll("{");
            var primeiro = true;
            var iter = self.iterador();
            while (iter.next()) |pos| {
                if (!primeiro) try writer.writeAll(", ");
                try writer.print("{d}", .{pos});
                primeiro = false;
            }
            try writer.writeAll("}");
        }
    };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    // BitSet com capacidade para 256 elementos
    var pares = BitSet(256).init();
    var mult3 = BitSet(256).init();

    // Define pares e múltiplos de 3 até 30
    for (0..31) |i| {
        if (i % 2 == 0) pares.definir(i);
        if (i % 3 == 0) mult3.definir(i);
    }

    try stdout.writeAll("Pares até 30:        ");
    try pares.imprimir(stdout);
    try stdout.print(" ({d} elementos)\n", .{pares.contagem()});

    try stdout.writeAll("Múltiplos de 3:      ");
    try mult3.imprimir(stdout);
    try stdout.print(" ({d} elementos)\n", .{mult3.contagem()});

    // Operações de conjunto
    var inter = pares;
    inter.intersecao(&mult3);
    try stdout.writeAll("\nInterseção (div 6):  ");
    try inter.imprimir(stdout);
    try stdout.writeAll("\n");

    var uni = pares;
    uni.uniao(&mult3);
    try stdout.writeAll("União:               ");
    try uni.imprimir(stdout);
    try stdout.writeAll("\n");

    var dif = pares;
    dif.diferenca(&mult3);
    try stdout.writeAll("Pares \\ Múlt3:       ");
    try dif.imprimir(stdout);
    try stdout.writeAll("\n");

    // Crivo de Eratóstenes com BitSet
    try stdout.writeAll("\n=== Crivo de Eratóstenes (até 100) ===\n");
    var primos = BitSet(101).init();
    for (2..101) |i| primos.definir(i);

    var p: usize = 2;
    while (p * p <= 100) : (p += 1) {
        if (primos.contem(p)) {
            var multiplo = p * p;
            while (multiplo <= 100) {
                primos.limpar(multiplo);
                multiplo += p;
            }
        }
    }

    try stdout.writeAll("Primos: ");
    try primos.imprimir(stdout);
    try stdout.print("\nTotal: {d} primos\n", .{primos.contagem()});
}