HN Reader

> return ((y * 1073750999) & 3221352463) <= 126976;

> How does this work? The answer is surprisingly complex.

I don't think anyone is surprised in the complexity of any explanation for that algorithm :D

> 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.

The optimizations that compilers can achieve kind of amaze me.

Indeed, the latest version of cal from util-linux keeps it simple in the C source:

  return ( !(year % 4) && (year % 100) ) || !(year % 400);

https://github.com/util-linux/util-linux/blob/v2.41/misc-uti...

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?

Does anyone have a collection of these things?

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

If you need to know a leap year and it's before the year 6000, I made an interactive calculator and visualization [1].

It's >3 machine instructions (and I admire the mathematical tricks included in the post), but it does do thousands of calculations fairly quickly :)

[1] https://calculang.dev/examples-viewer?id=leap-year

Looks like gcc & clang use some of the bit-twiddling tricks when you compile the original function with -O3: https://godbolt.org/z/eshd9axod

    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

There are many cute binary/logic tricks, if you like them be sure to read Hackers Delight and https://graphics.stanford.edu/~seander/bithacks.html . Once you've studied enough of them you'll find yourself easily coming up with more.

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.

Multiply and mask for varrious purposes is a thing I commonly use in my own code-- it's much more attractive now that it was decades ago because almost all computers we target these days have extremely fast multipliers.

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's a little tricky to program. :)

At least this one was easy to explain mechanically. Some bit hacks require p-adic numbers and other elements of number theory to explain.

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.

>“So, it’s a bug in Lotus 123?”

>“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.”

https://www.joelonsoftware.com/2006/06/16/my-first-billg-rev...

This is so cool!

Terrible nitpick, but this is actually 3 operations, not instructions. On x86 you get 4:

  is_leap_year_fast:
        imul    eax, edi, 1073750999
        and     eax, -1073614833
        cmp     eax, 126977
        setb    al
        ret

On ARM you get a bit more due to instruction encoding:

  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

Compiler explorer reference: https://godbolt.org/z/7ajYqbT9z

Interesting. In one place the author argues: 0 is missing, but we already know...

The is no year 0, it goes 1 BC, 1 AD. So testing whether 0 is a leap year is moot.

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): https://www.youtube.com/watch?v=0s9F4QWAl-E

It's rare to read code that makes me literally laugh out loud. What a delight.

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.

It’s also worth calling out angr as an interface between capstone and z3, which can take this to another level.

They should add that to https://github.com/alexmacarthur/current-time-api

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.

At first I thought it would be using the BCD instructions in some way, as shown near the bottom of this article: https://news.ycombinator.com/item?id=8477254

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 "fast" version from the article there are 4 instructions with each depending on the previous instruction. I'm not surprised it lost in the benchmark.

If the author ever reads this: The hyperlink to Jacob Pratt'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'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- 'Hold my beer and see what I can do!'

I'd be impressed if an LLM derived this independently.

> whether a year 0 ≤ y ≤ 102499

or equal to 0?

This reminds me of once when I was giving an algo/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.

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.

But do you know what's not free? Memory accesses[1]. So when I'm optimizing things, I focus on making things more cache friendly.

[1] http://gec.di.uminho.pt/discip/minf/ac0102/1000gap_proc-mem_...

This is fast, READABLE, and accurate:

bool is_leap_year(uint32_t y) { // Works for Gregorian years in range [0, 65535] return ((!(y & 3)) && ((y % 25 != 0) || !(y & 15))); }