Verificando se é ano bissexto com 3 instruções

• Implementa uma função que determina se um ano é bissexto usando apenas 3 instruções de CPU
• Esse método usa operações de bits e multiplicação para funcionar sem a abordagem tradicional com desvios
• Essa técnica é precisa no intervalo de 0 a 102499 anos
• Resultados de benchmark mostram desempenho cerca de 3,8 vezes mais rápido que o método convencional

---

Visão geral e apresentação do problema

• Para anos entre 0 e 102499, há uma função que determina se o ano é bissexto usando apenas 3 instruções de CPU
  • A função usada de fato tem a forma ((y * 1073750999) & 3221352463) <= 126976
• Explica o princípio, o funcionamento e a utilidade prática dessa técnica de bit-twiddling

Método tradicional para determinar anos bissextos

• Normalmente, a verificação de ano bissexto é implementada com divisão modular e desvios condicionais
  • Verifica-se se é divisível por 4, se não é divisível por 100 e se é divisível por 400
  • Código de exemplo:

    if ((y % 4) != 0) return false  
    if ((y % 100) != 0) return true  
    if ((y % 400) == 0) return true  
    return false  
    

Otimização da abordagem padrão

• A verificação de (y % 100) pode ser substituída por (y % 25), e a de (y % 400) por (y % 16)
  • Isso é possível porque o número já foi previamente dividido por 4, permitindo a troca para a relação com 25 e 16
• Há uma constante mágica que converte a operação (y % 25) em multiplicação e comparação, sem divisão
  • Exemplo: pode ser transformada em x * 3264175145 > 171798691
• Com uma máscara de bits adicional, (y & 3) ou (y & 15) pode substituir a divisão por 4 ou 16
• Compiladores automatizam essas transformações, mas elas também podem ser aplicadas manualmente em outras linguagens

Implementação sem desvios (branchless)

• Também é possível converter para uma forma sem desvios:

  return !(y & ((y % 25) ? 3 : 15))  
  

• Esse tipo de abordagem é adequado para code golf, em que se busca reduzir o tamanho do código

Encontrando constantes mágicas: abordagem de bit-twiddling

• Para tornar a expressão de verificação de ano bissexto ainda mais simples, foram usados busca combinatória e o Z3, um SMT Solver
  • Forma: ((y * f) & m) <= t
• As constantes f, m e t que satisfazem os requisitos foram buscadas com o Z3
  • Foram encontrados valores que produzem resultados corretos no intervalo de 0 a 102499
  • O resultado final é (y * 1073750999) & 3221352463 <= 126976

Explicação do princípio da função e da estrutura interna

• Ao analisar as constantes em binário, elas são divididas em três regiões principais de bits: A, B e C
  • Dependendo do estado dos bits em cada região, elas cobrem as 3 condições da verificação de ano bissexto
• Decomposição lógica da função:
  • Região A: verifica a condição de múltiplo de 4, incluindo se (y % 4) != 0
  • Região B: filtra se (y % 100) != 0 com vários padrões, como finais 14, 57, 71 etc.
  • Região C: verifica se (y % 16) == 0, ou seja, se é múltiplo de 16
• Explica o princípio pelo qual a multiplicação combina várias condições sem calcular restos diretamente
  • Ao multiplicar pela constante mágica, formam-se padrões de bits característicos em múltiplos de 100 e outros casos
  • O texto também inclui uma análise matemática da estrutura interna, incluindo erros de multiplicação e padrões em vários dígitos

Possibilidade de expandir o intervalo e a largura de bits

• Também é apresentado um método para buscar combinações adequadas de constantes mágicas ao expandir para 64 bits
  • É possível variar os valores de f, m e t para encontrar o maior intervalo possível
  • Há também, no StackExchange, casos com combinações ótimas e provas de uso do Z3

Benchmark e comparação de desempenho real

• Resultados de benchmark:
  • Em valores previsíveis, como 2025, a diferença é quase nula, com 0,65~0,69ns
  • Com entradas aleatórias, is_leap_year_fast mostra desempenho cerca de 3,8 vezes mais rápido
  • Quando o padrão de entrada torna a abordagem com desvios imprevisível, há uma vantagem significativa

Conclusão e aplicabilidade prática

• Em aplicações reais, o ganho é pequeno quando os valores são previsíveis, mas a técnica é muito útil em cenários com grande volume de dados aleatórios
• Ao substituir bibliotecas padrão reais em Python, C# etc., é necessário fazer um benchmark realista do programa como um todo
• A ideia e a implementação em si são interessantes e, em situações específicas, constituem uma solução atraente em termos de desempenho

[chickendreamtree]

Um texto que lembra o fast inverse sqrt

[GN⁺]

Comentários do Hacker News

• Surpresa ao descobrir que compiladores modernos como gcc ou clang otimizam automaticamente um código como is_leap_year1 para algo como is_leap_year2, então talvez não haja tanta necessidade de otimizar manualmente no nível do código-fonte em C, embora isso ainda possa ser útil em outras linguagens; também chamou atenção como a versão mais recente do código-fonte do programa cal trata a verificação de ano bissexto de forma muito simples
  • Gostei do fato de que o código do Linux inverte três condições seguidas toda vez e não usa um valor de retorno padrão, o que o torna muito mais fácil de entender; quando existe uma estrutura de código complicada assim, depurar vira uma experiência enlouquecedora
• Não surpreende nem um pouco que a explicação de como ((y * 1073750999) & 3221352463) <= 126976 funciona acabe sendo complexa; na verdade, isso é o esperado
• Adoro esse tipo de otimização com números mágicos difíceis de entender; sempre que vejo isso fico pensando em quantas técnicas de otimização devo ter perdido na época em que se escreviam loops internos em assembly, e peço que compartilhem alguma coleção desse tipo de técnica, se existir
  • Compartilhamento de links com várias técnicas de otimização: coletâneas de truques de manipulação de bits, uma macro CMP(X, Y) eficiente para comparações no estilo UNIX, exemplos de otimização da função signum, exemplos de código assembly para Motorola 68000, conjuntos de macros de bits originados do OpenSolaris e outras referências; também mencionam com pesar que o blog do Open Solaris desapareceu, e recomendam esse material para quem se interessa por otimização de código
  • Recomendação do livro "Hacker's Delight", cheio de truques com bits e técnicas de otimização de baixo nível
  • Sugestão para procurar a técnica de supercompilation
  • Naquela época, na verdade, essas técnicas não eram algo que se deixava passar; como multiplicação era muito cara, esse tipo de coisa já era a própria otimização
• Nunca imaginei que a verificação de ano bissexto pudesse ser tão interessante; dá a sensação de que programadores de baixo nível já encontraram esses truques há muito tempo, mas não deixaram registros, e que talvez esse tipo de coisa ainda esteja escondido em códigos antigos; muita vontade de explorar uma coleção dessas técnicas, se existir
  • Nos anos 80 eu tinha aprendido algumas coisas assim em casa com o z80, mas esqueci a maior parte; às vezes, quando mostro isso aos meus filhos na faixa dos 20 anos, parece até mágica
• Se você precisa saber anos bissextos antes do ano 6000, use uma calculadora interativa e ferramenta de visualização feita por um dos participantes; embora use um pouco mais de instruções de máquina, ela consegue processar milhares de cálculos muito rapidamente, e os truques matemáticos também impressionam
• Ao ler o capítulo sobre manipulação de bits, surgiu a ideia de "será que não dá para usar um solver?", e causou surpresa descobrir que o autor realmente usou exatamente esse método; satisfação com a abordagem minuciosa
• Sugestão de adicionar uma função assim de verificação de ano bissexto ao current-time-api
• Quando se olha para números em binário, aparecem padrões interessantes; achei curioso que todos os números primos, exceto o 2, terminam em 1
  • Pode parecer interessante à primeira vista, mas como todos os números ímpares terminam em 1 e números primos, por natureza, não podem ser pares exceto o 2, fica a dúvida se isso realmente significa alguma coisa
• Surge a observação de que no problema do ano bissexto não existe 0; na prática, não há "ano 0", e vai-se diretamente de 1 BC para 1 AD, então verificar 0 não faria sentido
  • No começo do texto é explicado que a premissa do algoritmo de ano bissexto é usar o calendário gregoriano proléptico e anos astronômicos; sem isso, a verificação de ano bissexto ficaria complexa dependendo da localidade
  • Se usar notação astronômica de anos, então o ano 0 existe, e para gerenciamento de ano/mês isso acaba sendo até mais limpo; a sugestão é manter os dados internos em notação astronômica e converter para BCE/CE apenas na saída externa
  • Os calendários anteriores à adoção do gregoriano têm critérios ambíguos e variam de região para região; em 1582 houve até a "remoção de 10 dias", então cálculos com datas anteriores a isso não são confiáveis; além disso, sacerdotes romanos às vezes ajustavam anos bissextos arbitrariamente por superstição ou suborno, o que complica ainda mais
  • A norma ISO8601 permite o ano 0, e no calendário astronômico o ano 0 corresponde a 1 BC; todos os anos BCE ficam deslocados em -1
• É raro um código-fonte realmente arrancar uma gargalhada, então isso foi uma experiência muito divertida