A bit-twiddling marvel

Pop quiz: what does the following code do?

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

It determines whether the year y is a leap year in the Gregorian calendar, of course. :)

It's very efficient, though I don't image that would ever matter. But it's very clever.

Gregorian vs Julian calendar

A year is a leap year in the Julian calendar if and only if it is a multiple of 4. But the Julian year is a bit too long on average to match the earth's orbit around the sun. You get a much better fit if you add the complication that years divisible by 100 but not by 400 are not leap years.

Presumably no one reading this recalls 1900 not being a leap year, but some of you may need to know some day that 2100 is not a leap year either.

C code

The cryptic function above comes from the recent post A leap year check in three instructionsby Falk Huffner. The function is correct for the next 100 thousand years (more precisely, through 103499) and correct if we anachronistically extent the Gregorian calendar back to the year 0.

The following C code shows empirically that Huffner's code is correct, but you'll have to read his post to understand why it is correct.

#include <stdio.h>#include <stdbool.h>#include <stdint.h>bool is_leap_year_fast(uint32_t y) { return ((y * 1073750999) & 3221352463) <= 126976;}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;}int main() { for (uint32_t y = 0; y <= 102499; y++) if (is_leap_year_fast(y) != is_leap_year(y)) printf("Exception: %d\n", y); return 0;}

Related posts

• Perpetual calndars
• Martian leap years
• Year share

The post A bit-twiddling marvel first appeared on John D. Cook.