The missing chapter of Hacker's Delight
27 October 2026
What is signed integer floor division?
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 algorithms
- And 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 latency
- On 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) latency
The 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.
Floor division can be much faster than you probably realise.
Note: in the bar chart: lower = faster.
Floor Div 86400 throughput - ARM64 ChipsAs tested on MacBook Pro M4 Pro
Common
(Rust*, Zig, etc.)
~2×
Floor Div 86400 throughput - X86 ChipsAs tested on AMD Ryzen 9 9950X3D
Common
(Rust*, Zig, etc.)
~2×
*Rust provides "div_euclid", which matches floor-div for positive 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:
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) Division
- Fixing the Bug
- What Hacker's Delight Has to Say About It
- Faster Techniques
- The Positive Divisor XOR Trick
- Robison’s Multiply-Add Technique
- Finally, on to the New Stuff
- Never Roll Your Own Fast Floor Division Algorithm
- Benchmarks
- Which Algorithm Should I Use?
- Annexure A. Proof
Starting with Truncated (Standard) Division Deep link
Let'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 integer
const 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) * M
const i64 tbit = wide >> 77const i64 sign = u64(x) >> 63
return tbit + sign
| x86-64 Latency Steps | ||
|---|---|---|
| Step | Computation 1 | Computation 2 |
| 1 | wide = ts * M | |
| 2 | mul-latency | sign = u64(ts) >> 63 |
| 3 | mul-latency | |
| 4 | high64bits(wide) >> 13 | |
| 5 | ... + sign | |
If 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 link
Btw, if you're new to all this, you might think: "Great! I now understand how signed division works at the compiler level!"
Divide by 100 (C++)Given: x — signed 64-bit integer
Divide by 100 low level steps (pseudocode)Given: x — signed 64-bit integer
const i64 M = (i128(1) << 70) / 100 + 1
const i128 wide = i128(x) * M
const i64 tbit = ((wide >> 64) + x) >> 6
const i64 sign = u64(x) >> 63
return tbit + sign
You should notice we now have some extra junk in there: ((wide >> 64) + x) >> 6.
| x86-64 Latency Steps | ||
|---|---|---|
| Step | Computation 1 | Computation 2 |
| 1 | wide = x * M | |
| 2 | mul-latency | sign = u64(x) >> 63 |
| 3 | mul-latency | |
| 4 | high64bits(wide) + x | |
| 5 | ... >> 6 | |
| 6 | ... + sign | |
The main takeaway here is that regular division is usually the cost of around 1 multiplication + 2-3 cycles.
Fixing the Bug Deep link
Okay, 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.
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 y
const 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 link
Hacker'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 Section 10–12: