Computing the day of the week in three CPU instructions

Ben Joffe dismantles the assumption that converting a day-count (rata-die) into a weekday is a trivial modulo operation. Because the divisor 7 is a Mersenne number of the form 2^N − 1, its magic reciprocal doesn’t fit cleanly in a 32-bit register, so conventional approaches — the naive double-mod, Rust’s rem_euclid, Howard Hinnant’s bit-width-independent method (2014), and Cassio Neri’s full-range solution (2024) — all pay for it with extra correction steps. Neri’s trick of casting signed to unsigned before any arithmetic elegantly sidesteps overflow, but the compiled code still spends four serially dependent operations just to refine an approximate division by 7.

Joffe’s payoff is a sequence of a multiply, an add, and a right-shift that computes the weekday over a restricted-but-practical range (roughly ±89 million days, spanning hundreds of thousands of years). It exploits the identity N % 7 = floor(N × 8 / 7) % 8, approximating ×8/7 with a single multiply-shift that reads the low bits so the final %8 falls out for free from the three surviving bits. A tuned three-instruction x86 variant is accurate across the full signed 32-bit range and, notably, an added constant acts as a rotation offset that lets you emit ISO weekday numbering [1‥7] instead of [0‥6] with identical instructions and zero speed penalty.

The significance is narrow but real for anyone writing high-performance date libraries, database engines, or compiler backends: each full-range 32-bit variant beats existing implementations, with several hitting latencies of one multiplication plus two cycles. The underlying techniques generalize to any x % (2^N − 1) modulus, and Joffe extends them to fast reductions like x % 24 and x % 60 that are directly useful for timekeeping code.