一种更快的有符号64位常量向下取整除法计算方式

# 一种更快的计算有符号64位常量向下取整除法的方法 来源：https://www.benjoffe.com/fast-floordiv **另见其他优化文章：** - 更快的星期几函数 (https://www.benjoffe.com/fast-day-of-week) - 更快的一天中的时间函数 (https://www.benjoffe.com/fast-time-of-day) ## *《Hacker's Delight》中缺失的一章* 2026年10月27日 **什么是有符号整数向下取整除法？** *有符号整数向下取整除法*是指你执行 `a/b` 得到的结果向 `−∞` 方向取整，而标准的*「截断」*有符号除法则向 `0` 方向取整。正如《Hacker's Delight》中所述：*「\[我怀疑\] 向下取整除法更常给出你想要的结果。」* 本文讨论的是**除数在编译时已知**的向下取整除法。尽管这个函数非常有用，但*整数向下取整除法*的现状却一片混乱： - 主流编译器和许多语言并未原生提供此功能*（如 C/C++/Go/Swift）*。 - 那些*确实*实现了它的语言和软件库似乎几乎从不使用最快的算法。 - 至少有一个非常知名的软件库存在有缺陷的溢出实现，持续了四年以上！*（后文详述）* - 典型的网络搜索和 LLM 提示通常只会浮现出慢速算法。 - 最后，《Hacker's Delight》*（基本上是底层计算机数学的圣经）*对此几乎没有提及！ 这篇博文不仅旨在揭示快速算法，还将**引入一种新的快速方法**，在理想的编译条件下： - **在 ARM 上**，对于大多数64位除数，吞吐量比现有算法快10–20%*（偶尔持平）*，延迟相同或更好。 - **在 x86 上**，基准测试结果为： - 对于约80%的正64位除数（60%的负除数），吞吐量快约5–10%。 - 在剩余的 x86 情况下更慢，且*通常*延迟更差（但仍有竞争力）。 [基准测试](https://www.benjoffe.com/fast-floordiv#benchmarks)章节提供了详细的概述，展示了多个平台上每个除数的吞吐量和延迟结果。它适用于所有位宽，在一些32位或SIMD应用中也可能有用，但最大的收益在64位场景中。它还可以用于更快的正模运算，以及更快的"欧几里得"除法*（对于负除数，与向下取整除法不同）*。 **向下取整除法可以比你想象的快得多。** 下面是除以**86400**的*吞吐量*基准测试快照*（一天的秒数）*，展示了大多数语言的内置方法与本文所述的快速替代方案之间的性能差异。注意：在条形图中，越低越快。 ARM x86 ***向下取整除 86400 吞吐量 - ARM64 芯片*** 在 MacBook Pro M4 Pro 和 Snapdragon X1-26-100 上测试 **常见方法**（Rust\*、Zig 等） **~2×** **Granlund-Montgomery**（1994） **1×** ARM x86 ***向下取整除 86400 吞吐量 - x86 芯片*** 在 AMD Ryzen 9 9950X3D 和 Intel Core i7（MacBook Pro 2016）上测试 **常见方法**（Rust\*、Zig 等） **~2×** **Granlund-Montgomery**（1994） **1.05×** *\*Rust 提供了 "div_euclid"，它在正除数时等同于向下取整除法。请参阅[基准测试章节](https://www.benjoffe.com/fast-floordiv#benchmarks)，了解40多个除数的更深入比较。* 由于访问此页面的一些人可能只想复制粘贴代码，我将从右侧的这个函数生成器开始： **新的快速除法函数：** 位宽：64位 32位 16位 8位 除数： ```cpp 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; } ``` 为避免歧义，许可证仅在你逐字复制注释和代码时适用。如果你在自己的代码中重写相同的逻辑，则不需要许可证。 **测试** 一组从 -32768 到 32767 的65535个除数可以生成为一个自包含的C++文件。它在同一个文件中包含边界测试。请参阅下载文件顶部的注释，了解如何构建和运行它。 使用此表单，你可以选择任何位宽和任何除数，获得一个即用的复制粘贴函数。 还有一个[参考算法](https://github.com/benjoffe/fastdiv/blob/main/algorithms/benjoffe.hpp)*（一个可复用的 C++ 模板，包含额外的微架构性能调优）*。 *如你所见，这个技术如此简单，以至于我预计*有人*已经做过了，但我搜索了一番，没有在任何地方找到相关文档。如果确实有人做过，至少这个页面可以让它被发现。* 对于其余的读者，我将讲述一个关于向下取整除法的故事，它与我的探索过程一致…… 如果你想创建一个快速的库或编译器/语言实现，这里将是你的一站式资源。如果你想跳过历史回顾，可以直接[跳到新内容](https://www.benjoffe.com/fast-floordiv#new)。 **文章章节：** - 从截断（标准）除法开始 (https://www.benjoffe.com/fast-floordiv#starting) - 修复 Bug (https://www.benjoffe.com/fast-floordiv#fixing-the-bug) - 《Hacker's Delight》怎么说 (https://www.benjoffe.com/fast-floordiv#hackers-delight) - 更快的技术 (https://www.benjoffe.com/fast-floordiv#other) - 正除数 XOR 技巧 (https://www.benjoffe.com/fast-floordiv#xor) - Robison 的乘加技术 (https://www.benjoffe.com/fast-floordiv#robison) - **终于，新内容** (https://www.benjoffe.com/fast-floordiv#new) - 切勿自己编写快速向下取整除法算法 (https://www.benjoffe.com/fast-floordiv#tensorflow-bug) - 基准测试 (https://www.benjoffe.com/fast-floordiv#benchmarks) - 我应该使用哪种算法？ (https://www.benjoffe.com/fast-floordiv#which) - 附录 A. 证明 (https://www.benjoffe.com/fast-floordiv#proof) --- ## 从截断（标准）除法开始 [直达链接](https://www.benjoffe.com/fast-floordiv#starting) 假设你想将以秒为单位的 Unix 时间戳转换为*rata die*（天数计数）。再假设你忘记了正确的做法，使用了标准的*（"截断"）*除法。我们需要除以 `86400`*（60×60×24）*。我们将使用64位时间戳，因为32位时间戳只能存储大约±68年。 在有人递给你一个1970年之前的时间戳之前，你会对右边的这个实现非常满意！ **C++ 标准除法（非向下取整除法）** 给定：`x` — *有符号64位整数* ```cpp const int64_t rd = x / 86400; return rd; ``` 上面的函数对大多数负值返回错误的结果。当然，你应该使用*向下取整除法*，这种除法类型对于跟踪重复模式非常有用，如时间戳、角度旋转、瓦片位置等。这种除法类型对应的 `"%"` 操作是正确的*正模运算*，而不是 C++、JavaScript 等语言中 `"%"` 提供的那种假模运算。 尽管如此，了解执行此类标准除法时底层发生了什么还是很有用的。下面的伪代码展示了编译后的汇编实际上在做什么。它本质上是一个乘法-移位，以及对负数的加一。 **标准除法编译后的步骤（伪代码）** ```cpp const i64 M = (i128(1) << 77) / 86400 + 1 const i128 wide = i128(x) * M const i64 tbit = wide >> 77 const i64 sign = u64(x) >> 63 return tbit + sign ``` x86-64 延迟步骤： | 步骤 | 计算 1 | 计算 2 | |------|--------|--------| | 1 | `wide = ts * M` | | | 2 | *乘法延迟* | `sign = u64(ts) >> 63` | | 3 | *乘法延迟* | | | 4 | `high64bits(wide) >> 13` | | | 5 | `... + sign` | | 如果你不太熟悉位操作，步骤 `u64(ts) >> 63` 可能看起来很奇怪。这只是将最高位移到最低位。在二进制补码计算机上，最高位是符号位，所以负数会留下1，正数会留下0。 ### 关于*不配合*除数的题外话 [直达链接](https://www.benjoffe.com/fast-floordiv#uncooperative-aside) 顺便说一下，如果你是新手，你可能会想：*"太好了！我现在理解有符号除法在编译器层面是如何工作的了！"* 不好意思打破你的幻想，以下是64位除以100的相同操作： **除以 100（C++）** 给定：`x` — *有符号64位整数* ```cpp return x / 100; ``` **除以 100 的底层步骤（伪代码）** 给定：`x` — *有符号64位整数* ```cpp 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 ``` 你应该注意到现在多了一些额外的东西：`((wide >> 64) + x) >> 6`。这是必需的，因为 `100` 的魔法乘数恰好需要 `M` 使用全部64位。这导致最高位为 `1`，使得 `M` 成为一个负数，按照计算方式，`M` 的值最终比应有的值低 `2^64`。由于我们计算 `x * M`，`wide` 的值也因此比应有的值低 `2^64 * x`。通过将 `x` 加到宽双寄存器结果的上半部分，我们可以完美地修正它。 需要这些修正的除数被一些作者称为*不配合除数*。 x86-64 延迟步骤： | 步骤 | 计算 1 | 计算 2 | |------|--------|--------| | 1 | `wide = x * M` | | | 2 | *乘法延迟* | `sign = u64(x) >> 63` | | 3 | *乘法延迟* | | | 4 | `high64bits(wide) + x` | | | 5 | `... >> 6` | | | 6 | `... + sign` | | 这里的主要结论是，常规除法的代价通常是大约1次乘法 + 2-3个周期。 ## 修复 Bug [直达链接](https://www.benjoffe.com/fast-floordiv#fixing-the-bug) 好的，*回到除以 86400*；你被这个 bug 咬了，决定修补它。很明显，当 `x < 0` 时 bug 会发生，但并非总是如此。如果它是负数*且*能被86400整除，它仍然能正常工作。因此，当 `rem < 0` 时需要调整，如下所示： **C++** ```cpp const int64_t div = x / 86400; const int64_t rem = x % 86400; return div - (rem < 0); ``` 但你心想，肯定有更快的方法吧？计算模几乎和除法本身一样昂贵，而且在我们的理论用例中，在加一之后模就被丢弃了。 下面的第二个例子可能是首先想到的简化方式，但实际上它更慢！你可以访问 GodBolt 链接查看它产生了更多的汇编行…… 好吧，算了，这种不直观的废话，我们去谷歌搜索*"C++ 中快速向下取整除法"*，然后得到类似这样的 AI 摘要（https://www.benjoffe.com/resources/FastDivision-GoogleAISummary.pdf）*（缓存的 PDF 导出）*。 **这个 AI 摘要非常误导**，因为它声称*"以下是每种场景的最快无分支方法。"*，然后展示了一个常量向下取整除法例程，其效果并不比我们这里的尝试好，尽管更快的方法已经为人所知30多年*（虽然它至少处理了负除数）*。无论如何，右边的代码就是它的建议。 至少现在我们有一个灵活的实用函数，而且看起来 GCC 和 Clang 在除数硬编码时能将这个编译成与之前版本相同的汇编*（在 Godbolt 上查看 (https://godbolt.org/z/jvqv4b74a)）*。 这基本上就是 [Java Math.floorDiv](https://github.com/openjdk/jdk/blob/2365ecc5fd83cf27c6c55aaca5aa6bad6ae9dbbf/src/java.base/share/classes/java/lang/Math.java#L1475)、[Python 的 numpy](https://github.com/numpy/numpy/blob/2f1eca306857b641fb0fef0ab854a2d4137e1581/numpy/_core/src/umath/loops_arithmetic.dispatch.c.src#L346-L369)、[Zig](https://codeberg.org/ziglang/zig/src/tag/0.17.0/src/codegen/llvm/FuncGen.zig#L3535)、[Ruby](https://github.com/ruby/ruby/blob/v4.0.7/internal/fixnum.h#L122) 和许多其他库使用的相同函数。 **有符号除数的通用方案** 给定：`x, y` — *有符号整数* 计算 `x FLOOR_DIV y` ```cpp const int64_t div = x / y; const int64_t rem = x % y; return div - (rem != 0 && (x ^ y) < 0); ``` ## 《Hacker's Delight》怎么说 [直达链接](https://www.benjoffe.com/fast-floordiv#hackers-delight) 《Hacker's Delight》第二版的目录中有一个章节：*"10-12 对模和向下取整除法的适用性"*。这听起来很有希望！它紧随*数十页*精彩内容之后，那些页面讲述了其他类型除法（有符号、无符号等）的各种巧妙技巧。 **第 10-12 节的全部内容：** > *"将常量的模或向下取整除法转换为乘法似乎应该更简单，因为'如果被除数为负则加1'的步骤可以省略。但事实并非如此。上述方法不能以任何明显的方式应用于模和向下取整除法。也许可以想出一些办法；这可能涉及根据被除数的符号稍微调整乘数 m。"* 这就是整个章节…… 通常，复制整本书的整个章节可能构成版权侵权，但在这个案例中它太短了，我认为属于合理使用。虽然 Warren 没有提供任何解决方案，但黄色高亮部分完美地预测了我稍后将介绍的新方法。 ## 更快的技术 [直达链接](https://www.benjoffe.com/fast-floordiv#other) 到这个时候，你可能会觉得这已经无法进一步优化了；也许对于运行时除数确实如此（我没有研究过，因为我主要关注编译时场景）。 再往下看，Google 搜索的第一条结果：曾经繁忙的 Stack Overflow 的考古遗迹。标题看起来很有希望：[C/C++ 中有符号整数除法的快速向下取整](https://stackoverflow.com/questions/46265403/fast-floor-of-a-signed-integer-division-in-c-c)。帖子发布于2017年，有6个答案。发帖者和前五个高票回答都使用了上述技术的变体。 最后，如果你滚动到底部，你会看到在七年后，用户*ufoguy*终于发布了一个答案，对于编译时除数来说明显更快： *"不太确定为什么这个方法没有被提及；只需一次除法，无模运算，无分支："* **C++ - 向下取整除法**（其中 b > 0） ```cpp int floor_div(int a, int b) { return (a + (a < 0)) / b - (a < 0); } ``` 根据我的基准测试，这是一个不错的改进，在大多数设备上运行**吞吐量提高了约50%**。 *ufoguy*加这个答案得到了什么？没有感谢，没有点赞，只有一条评论指出这没有考虑负数。这是一个合理的警告。如果我们打算制作一个快速的通用库，它应该尽可能灵活。 幸运的是，通用情况至少在90年代就被解决了。它在[《使用乘法的不变整数除法》](https://gmplib.org/~tege/divcnst-pldi94.pdf) - Granlund, Montgomery, 1994的第6页有清晰的文档。 使用那篇论文中的技术，我们可以创建一个简单的灵活模板函数（非零除数在编译时已知）。我用该技术准备了一个例子，在 C++ 中可以这样调用：`floor_div(timestamp);` 注意，论文展示了一个完全无分支的版本，但我更喜欢上面的版本用于常量除法，因为它的逻辑非常清晰明了，而且分支是在编译时的，保证会被优化掉。编译器很容易识别重复的比较，例如 `(x < 0)`，并重用结果。 不过，请看这个 [GodBolt (https://godbolt.org/z/K56YedWGe)] 对比，看看 MSVC 在简化完全无分支版本时有多挣扎。 看起来向下取整除法已经解决了，对吧？我们才刚刚开始…… **C++ Granlund Montgomery 向下取整除法（v1）** ```cpp #include template <typename D, D D> constexpr decltype(D) floor_div(decltype(D) x) { static_assert(std::is_integral_v<D> && std::is_signed_v<D> && D != 0, "divisor must be a signed non-zero integer"); if constexpr (D > 0) return ```