概要

• is_leap_year_fast 関数は、3命令ほどで閏年判定を実現するビット演算トリックを利用
• 標準的な閏年判定ロジックと比較しつつ、最適化・ビット操作の流れを解説
• 魔法定数 の由来・役割、z3による探索方法、ビットパターンの意味を詳細に分析
• 判定範囲（0～102499年）や、なぜこの範囲で正しいかの理由を説明
• 実用性や他の高速化手法への言及も含め、ビット操作による最適化の楽しさを紹介

3命令で閏年判定？ビット演算と魔法定数の仕組み

---

標準的な閏年判定ロジック

• グレゴリオ暦 （proleptic Gregorian calendar）を前提とし、年0～102499の範囲で判定することを想定
• 標準的な実装例：

  bool is_leap_year(uint32_t y) {
    if ((y % 4) != 0) return false;
    if ((y % 100) != 0) return true;
    if ((y % 400) == 0) return true;
    return false;
  }
  

  • 4で割り切れなければ閏年でない（平年）
  • 100で割り切れなければ閏年
  • 400で割り切れれば閏年
  • それ以外は平年とする判定

---

標準ロジックの最適化

• 既知の倍数性を活かし、 (y % 100) != 0 を (y % 25) != 0 に、 (y % 400) == 0 を (y % 16) == 0 に変換することが可能
  • 4の倍数でなければ判定終了、25の倍数でなければ閏年、16の倍数なら閏年
• これにより、4や16での剰余判定はビットマスクで高速化できる（例：y & 3, y & 15）
• 25での剰余判定も、 定数乗算+比較 で高速化できる（論文参照：Daniel Lemireら "Faster remainder by direct computation" など）

---

魔法定数によるビット演算判定

• さらなる高速化を目指し、 ビット演算と定数乗算 による分岐無しの判定式を導出
  • 数式例：((y * f) & m) <= t
    • f, m, tは探索によって得られた「魔法定数」
• z3などのSMTソルバーで定数を探索し、 0～102499 年の範囲で正しい判定式を発見
  • 実際の定数：
    • f = 1073750999u
    • m = 3221352463u
    • t = 126976u
  • 実装例：

    bool is_leap_year_fast(uint32_t y) {
      return ((y * 1073750999u) & 3221352463u) <= 126976u;
    }
    

---

ビット演算の意味と分解

• 乗算後のビット列を3ブロック（A, B, C）に分けて判定を実施
  • Aブロック ：4の倍数判定（(y % 4) != 0）
  • Bブロック ：100の倍数判定（(y % 100) != 0）、ただし25の倍数性を利用
  • Cブロック ：16の倍数判定（(y % 16) == 0）、400の倍数判定に相当
• 3つの条件を1つのビット比較にまとめ、 分岐無し・高速 な判定を実現
• 実際のビット構造や、なぜこの範囲で正しいかは、定数の誤差許容量やビットパターンの周期性に基づく

---

範囲の限界と実用性

• 102499年まで しか正確に判定できない理由：
  • 定数乗算による誤差が、ビットパターンの周期性と一致する上限であるため
  • それ以降は、100の倍数の検出が漏れるため誤判定が生じる
• 実用上、多くのプログラミング言語やアプリケーションは 0～9999年 程度しか扱わないため十分
• モダンなコンパイラは既に類似の最適化を自動で行う場合も多い

---

まとめ・応用

• ビット演算・定数乗算 を活用することで、分岐無し・高速な閏年判定が可能
• 魔法定数やビットパターンの分析は、 カレンダー計算や最適化技法 の面白さ・奥深さを示す好例
• 他のカレンダー計算や周期性判定にも応用可能なテクニックであることを確認

---

参考文献・追加情報

• Daniel Lemire, Owen Kaser, Nathan Kurz: "Faster remainder by direct computation: Applications to compilers and software libraries"
• Cassio Neri, Lorenz Schneider: "Euclidean affine functions and their application to calendar algorithms"
• David Turner: "Identifying leap years"
• Jacob Pratt: "Optimizing with Novel Calendrical Algorithms"
• z3 SMTソルバー：ビットベクトル制約の探索に利用可能

---

このように、 is_leap_year_fast の魔法定数による閏年判定は、ビット操作・数値誤差・周期性を駆使した高度な最適化テクニックの一例であり、実用性とアルゴリズムの面白さを両立していることを確認。