A leap year check in three instructions

&gt; return ((y * 1073750999) &amp; 3221352463) &lt;= 126976;<p>&gt; How does this work? The answer is surprisingly complex.<p>I don&#x27;t think anyone is surprised in the complexity of any explanation for that algorithm :D

&gt; <i>Note that modern compilers like gcc or clang will produce something like is_leap_year2 from is_leap_year1, so there is not much point in doing this in C source, but it might be useful in other programming languages.</i><p>The optimizations that compilers can achieve kind of amaze me.<p>Indeed, the latest version of <i>cal</i> from <i>util-linux</i> keeps it simple in the C source:<p><pre><code> return ( !(year % 4) &amp;&amp; (year % 100) ) || !(year % 400); </code></pre> <a href="https:&#x2F;&#x2F;github.com&#x2F;util-linux&#x2F;util-linux&#x2F;blob&#x2F;v2.41&#x2F;misc-utils&#x2F;cal.c#L633">https:&#x2F;&#x2F;github.com&#x2F;util-linux&#x2F;util-linux&#x2F;blob&#x2F;v2.41&#x2F;misc-uti...</a>

I love these incomprehensible magic number optimizations. Every time I see one I wonder how many optimizations like this we missed back in the old days when we were writing all our inner loops in assembly?<p>Does anyone have a collection of these things?

Part-way through the section on bit-twiddling, I thought to myself &quot;Oh I wonder if we could use a solver here&quot;. Lo and behold, I was pleasantly surprised to see the author then take that exact approach. Love the attention to detail in this post!

Looks like gcc &amp; clang use <i>some</i> of the bit-twiddling tricks when you compile the original function with -O3: <a href="https:&#x2F;&#x2F;godbolt.org&#x2F;z&#x2F;eshd9axod" rel="nofollow">https:&#x2F;&#x2F;godbolt.org&#x2F;z&#x2F;eshd9axod</a><p><pre><code> is_leap_year(unsigned int): xor eax, eax test dil, 3 jne .L1 imul edi, edi, -1030792151 mov eax, 1 mov edx, edi ror edx, 2 cmp edx, 42949672 ja .L1 ror edi, 4 cmp edi, 10737418 setbe al .L1: ret</code></pre>

If you need to know a leap year and it&#x27;s before the year 6000, I made an interactive calculator and visualization [1].<p>It&#x27;s &gt;3 machine instructions (and I admire the mathematical tricks included in the post), but it does do thousands of calculations fairly quickly :)<p>[1] <a href="https:&#x2F;&#x2F;calculang.dev&#x2F;examples-viewer?id=leap-year" rel="nofollow">https:&#x2F;&#x2F;calculang.dev&#x2F;examples-viewer?id=leap-year</a>

There are many cute binary&#x2F;logic tricks, if you like them be sure to read Hackers Delight and <a href="https:&#x2F;&#x2F;graphics.stanford.edu&#x2F;~seander&#x2F;bithacks.html" rel="nofollow">https:&#x2F;&#x2F;graphics.stanford.edu&#x2F;~seander&#x2F;bithacks.html</a> . Once you&#x27;ve studied enough of them you&#x27;ll find yourself easily coming up with more.<p>Warning: This may increase or decrease your popularity with fellow programmers, depending on how lucky you are in encountering problems where they make an important performance difference rather than a readability problem for people who have not deeply internalized bit twiddling.<p>Multiply and mask for varrious purposes is a thing I commonly use in my own code-- it&#x27;s <i>much</i> more attractive now that it was decades ago because almost all computers we target these days have extremely fast multipliers.<p>These full-with logic operations and multipliers give you kind of a very parallel computer packed into a single instruction. The only problem is that it&#x27;s a little tricky to program. :)<p>At least this one was easy to explain mechanically. Some bit hacks require p-adic numbers and other elements of number theory to explain.

This is so cool!<p>Terrible nitpick, but this is actually 3 <i>operations</i>, not instructions. On x86 you get 4:<p><pre><code> is_leap_year_fast: imul eax, edi, 1073750999 and eax, -1073614833 cmp eax, 126977 setb al ret </code></pre> On ARM you get a bit more due to instruction encoding:<p><pre><code> is_leap_year_fast: ldr r1, .LCPI0_0 mul r0, r0, r1 ldr r1, .LCPI0_1 and r1, r0, r1 mov r0, #0 cmp r1, #126976 movwls r0, #1 bx lr .LCPI0_0: .long 1073750999 .LCPI0_1: .long 3221352463 </code></pre> Compiler explorer reference: <a href="https:&#x2F;&#x2F;godbolt.org&#x2F;z&#x2F;7ajYqbT9z" rel="nofollow">https:&#x2F;&#x2F;godbolt.org&#x2F;z&#x2F;7ajYqbT9z</a>

Taking a look at numbers in binary reveals some interesting patterns. Although seems obvious, it was interesting to me when I realized that all prime numbers except 2 end with 1.

Somewhat relevant and related.<p>&gt;“So, it’s a bug in Lotus 123?”<p>&gt;“Yeah, but probably an intentional one. Lotus had to fit in 640K. That’s not a lot of memory. If you ignore 1900, you can figure out if a given year is a leap year just by looking to see if the rightmost two bits are zero. That’s really fast and easy. The Lotus guys probably figured it didn’t matter to be wrong for those two months way in the past. It looks like the Basic guys wanted to be anal about those two months, so they moved the epoch one day back.”<p><a href="https:&#x2F;&#x2F;www.joelonsoftware.com&#x2F;2006&#x2F;06&#x2F;16&#x2F;my-first-billg-review&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.joelonsoftware.com&#x2F;2006&#x2F;06&#x2F;16&#x2F;my-first-billg-rev...</a>

Interesting. In one place the author argues: 0 is missing, but we already know...<p>The is no year 0, it goes 1 BC, 1 AD. So testing whether 0 is a leap year is moot.

It&#x27;s rare to read code that makes me literally laugh out loud. What a delight.

This is gold! HN Kino! Taking the hardest problem in the world, date checking, and casually bitflipping the hell out of it. Hats off man :D

Interesting cppcon talk related to this (author is cited in TFA): <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=0s9F4QWAl-E" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=0s9F4QWAl-E</a>

They should add that to <a href="https:&#x2F;&#x2F;github.com&#x2F;alexmacarthur&#x2F;current-time-api">https:&#x2F;&#x2F;github.com&#x2F;alexmacarthur&#x2F;current-time-api</a>

Knowing how to use z3 for stuff like this is a superpower that not a lot of people have, but is definitely worth knowing if you work with code that needs to be optimized at this level. I have an mcp script that interfaces with z3, and this comment is a reminder to myself to find some time to expand it in the future for this specific flow.<p>It’s also worth calling out angr as an interface between capstone and z3, which can take this to another level.

One of these days, someone will get creative and do this sort of thing for the leap year algorithm of the Revised Julian Calendar instead of the Gregorian one.

The original function is likely only going to be 3 instructions. xor, test, jne and only 1 of these is dependent on a previous instruction. In the &quot;fast&quot; version from the article there are 4 instructions with each depending on the previous instruction. I&#x27;m not surprised it lost in the benchmark.

At first I thought it would be using the BCD instructions in some way, as shown near the bottom of this article: <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=8477254">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=8477254</a>

<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=42915723#42924485">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=42915723#42924485</a>

If the author ever reads this: The hyperlink to Jacob Pratt&#x27;s article has the hyperlink URL and text swapped.

tha page seems to have problems with layout overflow in equation blocks on mobile. It seems that because spans are inline elements they won&#x27;t overflow. I think you can make them block elements and enable some form of overflow to solve it.

Code is written not just for computer to execute, but for other people to read and understand. If you put such code readability will suffer tremendously. Beside that, what are you doing in your code that you need to optimize leap year check?! This clever tricks it remind me phrase that lead to many accidents- &#x27;Hold my beer and see what I can do!&#x27;

I&#x27;d be impressed if an LLM derived this independently.

&gt; whether a year 0 ≤ y ≤ 102499<p><i>or equal to</i> 0?

This reminds me of once when I was giving an algo&#x2F;ds interview (in Java) and the interviewer started asking me questions where one of the answers usually was “to be memorised” shit like this and he started pestering me to give him those answers (even though I said I don’t know and definitely don’t recall) and that too in C. As per him “everyone who coded knew C.. at least in college” and started becoming a bit more hostile. I think it was the first interview that I had ended as an interviewee.<p>And I call this thing “bit gymnastics”.

Never thought a leap year check could be this interesting. Maybe low-level programmers had already discovered tricks like this long ago，they just never got written down? Feels like there’s still so much like this, hidden in old code, waiting to be rediscovered. If anyone has a collection of these kinds of techniques, I’d really love to dig into it.

I tend to be of the opinion that for modern general purpose CPUs in this era, such micro-optimizations are totally unnecessary because modern CPUs are so fast that instructions are almost free.<p>But do you know what&#x27;s not free? Memory accesses[1]. So when I&#x27;m optimizing things, I focus on making things more cache friendly.<p>[1] <a href="http:&#x2F;&#x2F;gec.di.uminho.pt&#x2F;discip&#x2F;minf&#x2F;ac0102&#x2F;1000gap_proc-mem_speed.pdf" rel="nofollow">http:&#x2F;&#x2F;gec.di.uminho.pt&#x2F;discip&#x2F;minf&#x2F;ac0102&#x2F;1000gap_proc-mem_...</a>

This is fast, READABLE, and accurate:<p>bool is_leap_year(uint32_t y) { &#x2F;&#x2F; Works for Gregorian years in range [0, 65535] return ((!(y &amp; 3)) &amp;&amp; ((y % 25 != 0) || !(y &amp; 15))); }