A faster way to compute signed 64-bit floor division by constants

See also, other optimisation articles:Faster day-of-week functionsFaster time-of-day functionsThe missing chapter of Hacker's Delight27 October 2026What is signed integer floor division?Signed integer floor division is where you do a/b and get a result that rounds towards −∞,whereas standard (“truncated”) signed division rounds towards 0.As stated in Hacker's Delight: “[I suspect that] floor division more often gives the result you want”.This article is about full-range floor division where the divisor is known at compile time.Despite the usefulness of this function, the world of integer floor division is in shambles:Mainstream compilers and many languages do not provide it natively (eg. C/C++/Go/Swift).Languages and software libraries that do implement it seem to almost never use the fastest algorithms.At least one highly prominent software library had a buggy overflowing implementation for over 4 years! (detailed later)Typical online searches and LLM prompts usually only surface the slow algorithmsAnd finally, Hacker's Delight (basically the bible on low-level computer math), has almost nothing to say about it!This blog post aims to not only shine light on the fast algorithms, but will also introduce a new fast approach which, with ideal compilation:On ARM, benches 10–20% faster throughput than existing algorithms for most 64-bit divisors (occasionally tied), with equal or better latencyOn x86, benches:~5-10% faster throughput for around 80% of positive 64-bit divisors (60% of negative divisors)slower in the remaining x86 cases, and usually worse (but competitive) latencyThe benchmark section has a detailed overview showing per-divisor results over many platforms, for throughput and latency.It works in all bit-widths, and may find use on some 32-bit or SIMD applications, but the biggest benefit is in 64-bit.It also can be used for faster positive-modulus, and faster "Euclidean" division (differs to floor division for negative divisors).Floor division can be much faster than you probably realise.Below is a snapshot throughput benchmark for division by 86400 (the number of seconds in one day), the kind of performance you can expect using most languages' built-in methods, vs fast alternatives outlined in this blog.Note: in the bar chart: lower = faster. ARM x86Floor Div 86400 throughput - ARM64 ChipsAs tested on MacBook Pro M4 Proand Snapdragon X1-26-100Common(Rust*, Zig, etc.)~2×Robison(2005)~1.1×Granlund-Montgomery(1994)1×New Algo(2026)~0.8× ARM x86Floor Div 86400 throughput - X86 ChipsAs tested on AMD Ryzen 9 9950X3Dand Intel Core i7 (MacBook Pro 2016)Common(Rust*, Zig, etc.)~2×Granlund-Montgomery(1994)1.05×Robison(2005)~1×New Algo(2026)~0.95×*Rust provides "div_euclid", which matches floor-div for positive divisors.See the benchmark section for a deeper comparison across over 40 divisors.Since some people visiting this page will be just looking to copy/paste code, I'll start with this function builder on the right:New Fast Division Functions:Bit-Width: 64-bit32-bit16-bit8-bitDivisor: inline int64_t fast_i64_floordiv_86400(int64_t x) { const int64_t M = ((__int128(1) << 79) / 86400 + 1); const int64_t m = M + (x >> 63); return (__int128) x * m >> 79;}For the avoidance of doubt, the license only applies if you copy/paste the comment and code verbatim. No license is required if you re-write the same logic in your code.TestingA set of 65535 divisors from -32768 to 32767 for 64-bit can be generated into a single self-contained C++ file. It includes a boundary test in the same file.See the comment at the top of the download for how to build and run it.Using this form, you can choose any bit-width and any divisor to get a copy/paste function ready to go.There is also reference algorithm (a reusable C++ template with additional microarchitectural performance tweaks).As you can see, the technique is so simple that I'd expect that somebody has done this before, but I've looked around and not found it documented anywhere. If it turns out to have been done before, at least this page will make it discoverable.For the rest of us, I'll cover a narrative about floor division, which matches my process of discovery... And if you want to create a fast library or compiler/language implementation, this will be your one-stop shop.If you want to skip the history lesson, you can jump straight to the new stuff.Article Sections:Starting with Truncated (Standard) DivisionFixing the BugWhat Hacker's Delight Has to Say About ItFaster TechniquesThe Positive Divisor XOR TrickRobison’s Multiply-Add TechniqueFinally, on to the New StuffNever Roll Your Own Fast Floor Division AlgorithmBenchmarksWhich Algorithm Should I Use?Annexure A. ProofStarting with Truncated (Standard) Division Deep linkLet's suppose you want to convert a Unix timestamp measured in seconds, to rata-die (a day count). And let's also suppose you forgot how to do this properly, and you use standard ("truncated") division.We need to divide by 86400 (60×60×24). We'll use a 64-bit timestamp, since a 32-bit timestamp can only hold about ±68 years.You'll be very happy with this implementation on the right until somebody hands you a timestamp before 1970!C++ Standard Division (not floor-div)Given: x — signed 64-bit integerconst int64_t rd = x / 86400;return rd;The above function returns incorrect results for most negative values.Of course, you should be using floor division, the type of division that's useful for tracking repeating patterns like timestamps, angle rotations, tile positions etc. This is the type of division where the associated "%" operation is a proper positive modulus, not that fake modulus that "%" provides in C++, JavaScript etc.Nonetheless, it's useful to understand what is going on under the hood when doing standard division like this. The pseudocode below shows what the compiled assembly is actually doing. It's essentially a mul‑shift and bump-by-1 for negatives.Standard Division Compiled Steps (pseudocode)const i64 M = (i128(1) << 77) / 86400 + 1 const i128 wide = i128(x) * Mconst i64 tbit = wide >> 77 const i64 sign = u64(x) >> 63 return tbit + signx86-64 Latency StepsStepComputation 1Computation 21wide = ts * M2mul-latencysign = u64(ts) >> 633mul-latency4high64bits(wide) >> 135... + signIf you haven't bit twiddled much, the step u64(ts) >> 63 might seem odd. This is just moving the highest-bit down to the bottom. Since the top bit is the sign-bit on 2's complement computers, this leaves a 1 for negative numbers and a 0 for positive numbers.Aside on Uncooperative Divisors Deep linkBtw, if you're new to all this, you might think: "Great! I now understand how signed division works at the compiler level!"Sorry to burst the bubble, but here's what the same thing looks like for 64-bit division by 100:Divide by 100 (C++)Given: x — signed 64-bit integerreturn x / 100;Divide by 100 low level steps (pseudocode)Given: x — signed 64-bit integerconst i64 M = (i128(1) << 70) / 100 + 1const i128 wide = i128(x) * Mconst i64 tbit = ((wide >> 64) + x) >> 6const i64 sign = u64(x) >> 63return tbit + signYou should notice we now have some extra junk in there: ((wide >> 64) + x) >> 6.This is required because the magic multiplier for 100 happens to require all 64-bits for M.This causes the top bit to be 1, making M a negative number, and as computed, the value of M ends up2^64 lower than it should be. Since we compute x * M, the value of wide is thus 2^64 * x lower than it should be. By adding x to the upper-register of the wide double-register result, we correct for it perfectly.Divisors that require these corrections are referred to by some authors as uncooperative divisors.x86-64 Latency StepsStepComputation 1Computation 21wide = x * M2mul-latencysign = u64(x) >> 633mul-latency4high64bits(wide) + x5... >> 66... + signThe main takeaway here is that regular division is usually the cost of around 1 multiplication + 2-3 cycles.Fixing the Bug Deep linkOkay, back to div 86400; you get bitten by the bug, and decide to patch it. It's pretty clear that the bug can occur when x < 0, but not always. If it's negative and divisible by 86400, it still works.So therefore, it needs adjusting when rem < 0, like so:C++const int64_t div = x / 86400;const int64_t rem = x % 86400;return div - (rem < 0);But you think to yourself, surely there must be a faster way? Computing the modulus is almost as expensive as the division itself, and it gets thrown away after the bump in our theoretical use-case.The 2nd example below is perhaps the first simplification that may come to mind, but it's actually slower! You can visit the Godbolt link to see that it produces more assembly lines...Okay, screw this unintuitive nonsense, let's Google "fast floor division in c++", and get an AI summary like this (cached PDF export).This AI summary is very misleading, as it falsely claims "Here are the fastest, branchless methods for each scenario.", before presenting a constant floor division routine that is no better than our attempt here, despite faster ways being known for 30 years+ (although it handles negative divisors at least).In any case, the code to the right is what it suggests.At least now we can have a flexible utility function, and it seems GCC and Clang can compile this into the same assembly as our previous version when the divisor is hard-coded (see on Godbolt ).This is basically the same function used by Java Math.floorDiv , Python's numpy , Zig , Ruby and many other libraries.Common Solution for signed divisorsGiven: x, y — Signed Integers Compute x FLOOR_DIV yconst int64_t div = x / y;const int64_t rem = x % y;return div - (rem != 0 && (x ^ y) < 0);What Hacker's Delight Has to Say About It Deep linkHacker's Delight, 2nd Edition, has a section listed in the table of contents: "10–12 Applicability to Modulus and Floor Division". That sounds promising!It comes immediately after dozens of awesome pages with fancy tricks for other types of division (signed, unsigned etc.).The entire contents of