@ctz em Zig
O @ctz (Count Trailing Zeros) conta o número de bits zero consecutivos a partir do bit menos significativo (direita) de um valor inteiro. Mapeia diretamente para instruções de CPU eficientes (TZCNT/BSF em x86). Essencial para verificar alinhamento, encontrar o bit menos significativo e algoritmos de bitmap.
Sintaxe
@ctz(value: T) Log2T
Parâmetros
- value (
T): Valor inteiro cujos zeros à direita serão contados.
Valor de retorno
Retorna o número de zeros consecutivos do bit menos significativo. Para um tipo de N bits, o resultado varia de 0 a N.
Exemplos práticos
Exemplo 1: Contagem básica
const std = @import("std");
pub fn main() void {
// u8: 8 bits
std.debug.print("ctz(0b00000001) = {}\n", .{@ctz(@as(u8, 0b00000001))}); // 0
std.debug.print("ctz(0b00001000) = {}\n", .{@ctz(@as(u8, 0b00001000))}); // 3
std.debug.print("ctz(0b10000000) = {}\n", .{@ctz(@as(u8, 0b10000000))}); // 7
std.debug.print("ctz(0b00000000) = {}\n", .{@ctz(@as(u8, 0b00000000))}); // 8
}
Exemplo 2: Verificar alinhamento
const std = @import("std");
fn alinhamentoDe(endereco: usize) usize {
if (endereco == 0) return 0;
const zeros = @ctz(endereco);
return @as(usize, 1) << @intCast(zeros);
}
fn estaAlinhado(endereco: usize, alinhamento: usize) bool {
return alinhamentoDe(endereco) >= alinhamento;
}
pub fn main() void {
std.debug.print("Alinhamento de 16: {}\n", .{alinhamentoDe(16)}); // 16
std.debug.print("Alinhamento de 24: {}\n", .{alinhamentoDe(24)}); // 8
std.debug.print("Alinhamento de 4096: {}\n", .{alinhamentoDe(4096)}); // 4096
std.debug.print("16 alinhado a 8? {}\n", .{estaAlinhado(16, 8)}); // true
std.debug.print("24 alinhado a 16? {}\n", .{estaAlinhado(24, 16)}); // false
}
Exemplo 3: Iterar sobre bits ligados
const std = @import("std");
fn iterarBits(mascara: u32) void {
var m = mascara;
while (m != 0) {
const bit = @ctz(m);
std.debug.print("Bit {} está ligado\n", .{bit});
m &= m - 1; // Limpar bit menos significativo
}
}
pub fn main() void {
iterarBits(0b10110100);
// Bit 2 está ligado
// Bit 4 está ligado
// Bit 5 está ligado
// Bit 7 está ligado
}
Casos de uso comuns
- Verificar alinhamento: Determinar o alinhamento de um endereço de memória.
- Bitmap: Encontrar o primeiro bit livre em um bitmap de alocação.
- Fatoração: Encontrar potência de 2 que divide um número.
- Iteração de bits: Percorrer eficientemente todos os bits ligados.
Mapeamento para instruções de CPU
@ctz mapeia para instruções nativas extremamente eficientes:
| Arquitetura | Instrução |
|---|---|
| x86-64 | TZCNT ou BSF |
| ARM/AArch64 | RBIT + CLZ ou extensão |
| RISC-V | CTZ (extensão B) |
| WASM | i32.ctz / i64.ctz |
Em x86-64 moderno (com suporte a BMI1), TZCNT é uma instrução de 1 ciclo. BSF é ligeiramente mais lenta e tem comportamento indefinido para zero, mas o Zig usa TZCNT quando disponível.
Equivalente em C
Em C, __builtin_ctz(x) (GCC/Clang) conta trailing zeros para unsigned int. Para outros tamanhos: __builtin_ctzl (long), __builtin_ctzll (long long). Comportamento indefinido para zero no padrão C, mas GCC/Clang garantem resultado definido.
O Zig garante resultado definido para zero em todas as arquiteturas: retorna o número total de bits do tipo.
Aplicações avançadas
Algoritmo de Kernighan para iterar bits — versão detalhada:
const std = @import("std");
// Contar bits ligados usando @ctz para pular direto ao próximo bit
fn contarBitsLigados(mascara: u64) u7 {
var m = mascara;
var count: u7 = 0;
while (m != 0) : (count += 1) {
m &= m - 1; // Remove o bit menos significativo
}
return count;
}
// Coletar índices de todos os bits ligados
fn coletarIndices(mascara: u32, buf: []u5) usize {
var m = mascara;
var i: usize = 0;
while (m != 0 and i < buf.len) : (i += 1) {
buf[i] = @intCast(@ctz(m));
m &= m - 1; // Remove o bit encontrado
}
return i;
}
pub fn main() void {
var indices: [32]u5 = undefined;
const n = coletarIndices(0b10110100, &indices);
std.debug.print("Bits ligados em posições: ", .{});
for (indices[0..n]) |idx| {
std.debug.print("{} ", .{idx});
}
std.debug.print("\n", .{}); // 2 4 5 7
}
Encontrar o vizinho mais próximo em uma grade de bits (game development):
fn menorDirecao(opcoes: u8) u3 {
// opcoes é um bitmask de direções disponíveis
// Retorna o índice da direção com menor valor de bit
return @intCast(@ctz(opcoes));
}
@ctz em alocadores
Alocadores por bucket usam @ctz (ou @clz) para encontrar a faixa de tamanho correta em O(1):
const BuddyAllocator = struct {
// Encontrar a ordem (potência de 2) para um tamanho
fn ordemParaTamanho(tamanho: usize) u6 {
if (tamanho == 0) return 0;
// Potência de 2 >= tamanho
const potencia = std.math.ceilPowerOfTwo(usize, tamanho) catch return 63;
return @intCast(@ctz(potencia)); // log2 da potência de 2
}
};
Erros comuns
Comportamento com zero: @ctz(0) retorna o número de bits do tipo (ex: 32 para u32), não um valor indefinido. Mas lógicamente “a posição do primeiro bit ligado” não faz sentido para zero. Sempre verifique se o valor é zero antes de interpretar o resultado como índice de bit.
Confundir @ctz com @clz: @ctz conta do bit menos significativo (direita), @clz conta do bit mais significativo (esquerda). Para encontrar o bit mais significativo, use @clz.
Perguntas Frequentes
@ctz funciona com tipos signed?
Sim. @ctz trata os bits como valor binário bruto. Em inteiros signed negativos, o bit de sinal está ligado, então @ctz(-1) em i32 é equivalente a @ctz(0xFFFFFFFF) em u32, que retorna 0.
Posso usar @ctz em comptime?
Sim. @ctz pode ser avaliado em tempo de compilação quando o argumento é comptime conhecido. Isso permite calcular alinhamentos e potências de 2 em constantes comptime.
Builtins relacionados
- @clz — Contar zeros à esquerda (leading zeros)
- @popCount — Contar bits em 1
- @bitReverse — Inverter ordem dos bits
- @byteSwap — Inverter ordem dos bytes