Como calcular o dia da semana mais rápido com bit tricks

Problema e ponto de partida

Calcular o dia da semana a partir de um contador de dias parece simples, mas a operação normalmente envolve divisão ou resto por 7, tratamento de números negativos e, em alguns casos, riscos de overflow. O texto compara abordagens conhecidas e apresenta funções especializadas para diferentes objetivos: menor latência, maior vazão, plataformas distintas e intervalos de datas mais ou menos amplos.

A solução básica para um contador rd com a época Unix - 1º de janeiro de 1970, uma quinta-feira - soma 4 e calcula o resto positivo por 7. Ela é recomendada quando a facilidade de manutenção importa mais que a micro-otimização. A técnica de Howard Hinnant amplia a compatibilidade entre larguras de inteiros e evita conversões de sinal e overflow, mas não cobre formalmente os quatro maiores valores positivos de um inteiro de 32 bits em C/C++. A solução de Cassio Neri resolve esse problema em todo o intervalo de 32 bits ao converter o valor assinado para sem sinal antes do cálculo.

Multiplicação, deslocamento e o papel do número 7

O artigo explora o fato de 7 ser um número de Mersenne, da forma 2^N − 1. Essa propriedade permite transformar o resto por 7 em uma operação relacionada ao resto por 8, que pode ser obtido observando apenas três bits. Uma aproximação fixa de 2^32 / 7, combinada com uma soma constante que “gira” os resultados para alinhar a época Unix, produz uma função de apenas multiplicação, soma e deslocamento à direita.

A versão mais simples é correta em um intervalo restrito, aproximadamente entre 242 mil anos antes e depois da época Unix. Segundo o texto, ela pode ser especialmente eficiente em ARM, onde multiplicação, soma e deslocamento podem ser fundidos; a biblioteca Rust Jiff obteve uma melhoria de 40% em funções como nth_weekday_of_month após adotar essa abordagem. Para cobrir todo o domínio assinado de 32 bits, o autor apresenta uma ampliação para 64 bits e três variantes: uma que usa correções por deslocamentos, outra que emprega duas multiplicações independentes e uma terceira que aproveita simultaneamente as partes alta e baixa do produto.

A terceira variante chega a três instruções x86, além do carregamento de constantes, usando LEA para combinar a parte baixa, quatro vezes a parte alta e uma constante. O resultado é fornecido tanto no formato Unix, de 0 a 6, quanto no formato ISO, de 1 a 7, sem penalidade de velocidade segundo a análise. A escolha entre as variantes depende de latência, vazão, compilador, processador e intervalo de datas exigido; os compiladores testados nem sempre geram a sequência ideal manualmente descrita.

Generalização e evidências

As técnicas são estendidas a outros divisores relacionados a números de Mersenne e a divisores da forma 2^N − 2^K. O texto propõe, por exemplo, fórmulas rápidas para x % 24 e x % 60, substituindo o resto por uma soma com um quociente e uma máscara de bits. A justificativa matemática é uma identidade geral que transforma o módulo por um divisor em módulo por uma potência de dois após adicionar um múltiplo do quociente.

O explorador de funções reúne 280 combinações testadas. Os benchmarks, realizados em Apple M4 Pro, processadores AMD Ryzen, Intel Core i7 e Raspberry Pi Zero, mostram que as novas variantes são substancialmente mais rápidas que métodos ingênuos, rem_euclid, Hinnant e Neri em vários cenários, embora os resultados variem por arquitetura, compilador e modo de medição. O texto conclui que a técnica deve ser escolhida conforme as exigências da biblioteca, e anuncia sua aplicação futura ao cálculo rápido de horários.