@clz em Zig

O @clz (Count Leading Zeros) conta o número de bits zero consecutivos a partir do bit mais significativo (esquerda) de um valor inteiro. É uma operação fundamental para manipulação de bits, cálculo de log2, detecção do bit mais significativo e algoritmos de alocação.

Sintaxe

@clz(value: T) Log2T

Parâmetros

• value (T): Valor inteiro (unsigned ou signed) cujos zeros à esquerda serão contados.

Valor de retorno

Retorna o número de zeros consecutivos do bit mais significativo. Para um tipo de N bits, o resultado varia de 0 (nenhum zero) a N (valor é zero).

Exemplos práticos

Exemplo 1: Contagem básica de leading zeros

const std = @import("std");

pub fn main() void {
    // u8: 8 bits
    std.debug.print("clz(0b10000000) = {}\n", .{@clz(@as(u8, 0b10000000))}); // 0
    std.debug.print("clz(0b00010000) = {}\n", .{@clz(@as(u8, 0b00010000))}); // 3
    std.debug.print("clz(0b00000001) = {}\n", .{@clz(@as(u8, 0b00000001))}); // 7
    std.debug.print("clz(0b00000000) = {}\n", .{@clz(@as(u8, 0b00000000))}); // 8
}

Exemplo 2: Calcular log2 inteiro

const std = @import("std");

fn log2Floor(valor: u32) u5 {
    if (valor == 0) @panic("log2(0) indefinido");
    return 31 - @clz(valor);
}

fn proximaPotenciaDe2(valor: u32) u32 {
    if (valor <= 1) return 1;
    const bits = 32 - @clz(valor - 1);
    return @as(u32, 1) << @intCast(bits);
}

pub fn main() void {
    std.debug.print("log2(1) = {}\n", .{log2Floor(1)});     // 0
    std.debug.print("log2(8) = {}\n", .{log2Floor(8)});     // 3
    std.debug.print("log2(100) = {}\n", .{log2Floor(100)}); // 6

    std.debug.print("prox_pot2(5) = {}\n", .{proximaPotenciaDe2(5)});   // 8
    std.debug.print("prox_pot2(16) = {}\n", .{proximaPotenciaDe2(16)}); // 16
    std.debug.print("prox_pot2(17) = {}\n", .{proximaPotenciaDe2(17)}); // 32
}

Exemplo 3: Número mínimo de bits necessários

const std = @import("std");

fn bitsNecessarios(valor: u64) u7 {
    if (valor == 0) return 1;
    return @intCast(64 - @clz(valor));
}

pub fn main() void {
    std.debug.print("Bits para 255: {}\n", .{bitsNecessarios(255)});   // 8
    std.debug.print("Bits para 256: {}\n", .{bitsNecessarios(256)});   // 9
    std.debug.print("Bits para 1000: {}\n", .{bitsNecessarios(1000)}); // 10
}

Casos de uso comuns

1. log2 inteiro: Calcular logaritmo base 2 eficientemente.
2. Potência de 2 mais próxima: Encontrar próxima potência de 2 acima de um valor.
3. Alocadores: Determinar bucket de tamanho em alocadores por tamanho.
4. Compressão: Codificação de comprimento variável baseada em magnitude.

Equivalente em C e mapeamento para instruções de CPU

Em C, __builtin_clz(x) (GCC/Clang) faz a mesma operação para unsigned int. Para outros tamanhos: __builtin_clzl (long), __builtin_clzll (long long).

O Zig mapeia @clz para instruções nativas quando disponíveis:

Essas são instruções de ciclo único na maioria das CPUs modernas.

@clz vs @ctz — quando usar cada um

Comportamento com zero

Quando o valor de entrada é zero:

• @clz(0) retorna o número total de bits do tipo (ex: 32 para u32)
• @ctz(0) retorna o número total de bits do tipo (ex: 32 para u32)

Isso é diferente do comportamento de BSR/BSF em x86, que produz resultado indefinido para zero. O Zig garante um resultado bem definido em todas as arquiteturas.

std.debug.print("{}\n", .{@clz(@as(u32, 0))}); // 32, sempre

Aplicações práticas adicionais

Tabelas de lookup com indexação por potência de 2:

fn getBucket(tamanho: u32) u5 {
    // Retorna o índice do bucket correspondente à potência de 2 >= tamanho
    if (tamanho == 0) return 0;
    return @intCast(32 - @clz(tamanho - 1));
}
// tamanho 1 -> bucket 0 (2^0 = 1)
// tamanho 5 -> bucket 3 (2^3 = 8)
// tamanho 8 -> bucket 3 (2^3 = 8)
// tamanho 9 -> bucket 4 (2^4 = 16)

Verificar se um valor é potência de 2:

fn isPot2(n: u32) bool {
    if (n == 0) return false;
    // Uma potência de 2 tem exatamente 1 bit ligado
    return (n & (n - 1)) == 0;
    // Alternativa com @clz e @popCount:
    // return @popCount(n) == 1;
}

Erros comuns

Usar @clz com inteiros signed: Embora funcione, @clz em valores negativos (signed) sempre retorna 0 porque o bit de sinal está ligado. Converta para unsigned antes:

const n: i32 = 100;
const zeros = @clz(@as(u32, @bitCast(n))); // correto

Off-by-one em cálculos de log2: 31 - @clz(n) para u32 calcula floor(log2(n)). Para valores que são exatamente potências de 2, o resultado é correto. Para outros valores, é o floor. Documente claramente qual você precisa.

Perguntas Frequentes

@clz funciona com tipos de bits não-padrão como u24?

Sim. @clz(@as(u24, 1)) retorna 23 (23 zeros à esquerda de um u24 com valor 1). O Zig trata corretamente todos os tamanhos de inteiro.

Posso usar @clz em comptime?

Sim. Como todos os builtins aritméticos do Zig, @clz pode ser avaliado em tempo de compilação quando o argumento é comptime.

Builtins relacionados

• @ctz — Contar zeros à direita (trailing zeros)
• @popCount — Contar bits em 1
• @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