Hotdry.

Article

C++ 手写 uint128：算术运算的内联优化与除法性能调优

深入探讨手写 uint128 的底层实现，剖析加法、乘法、除法等运算的指令级优化策略，对比 intrinsics 与编译器内置 __uint128_t 的性能差异。

2026-02-02systems

在高性能计算领域，128 位无符号整型是一个有趣的存在。它足够小，CPU 无法原生支持；它又足够大，能够覆盖大多数哈希、几何和数值计算场景。GCC 和 Clang 提供了内置类型 __uint128_t，但在某些场景下，手写实现不仅能获得同等性能，还能解锁定制化的优化空间。本文将聚焦于 x64 平台，探讨如何用现代 C++ intrinsics 实现一个与编译器产物性能持平的 u128 类型，并重点剖析乘法、除法等复杂运算的优化路径。

固定宽度整型的存在价值

在探讨实现细节之前，有必要理解为什么需要手写一个编译器本应支持的类型。动态大整数库如 GMP 解决了通用性问题，但代价是内存分配、分支预测失败和间接调用开销。当你明确知道数值范围时，固定宽度算术是更优选择。一个典型的例子是精确几何计算：多边形布尔运算中的中间结果可能在 64 位范围内溢出，但绝对值始终可预测，使用 128 位固定宽度即可保证正确性，同时将运行时成本压到最低。

另一个关键优势是代码生成的可预测性。内置类型 __uint128_t 的行为由编译器黑盒决定，而手写实现允许你精确控制每条生成的汇编指令。在某些场景下，你可能需要禁用特定优化、强制内联或注入平台特定的加速指令 —— 这些需求手写实现都能优雅满足。

数据表示与基础框架

128 位无符号整型的最简表示是两个字（limb），每个字占用 64 位。我们可以将 u128 视为一个以 $2^{64}$ 为基数的两位数，低位字存储低 64 位，高位字存储高 64 位。这种表示天然适用于 x64 架构的两个通用寄存器，也为后续的逐位运算打下了基础。

#include <cstdint>
#include <immintrin.h>

using u64 = unsigned long long;

struct u128 {
    u64 low = 0;
    u64 high = 0;
};

选择 unsigned long long 而非 uint64_t 是因为某些 intrinsics 签名要求这种类型。immintrin.h 提供了 _addcarry_u64、_subborrow_u64 和 _mulx_u64 等核心 intrinsics，它们直接映射到 x64 指令集中的 adc、sbb 和 mulx。

加法与减法：进位链的精确控制

加法是所有算术运算中最简单的，但仍有优化空间。直接对两个 128 位整数做加法，需要处理 64 位边界的进位。__uint128_t 的加法在编译后生成一条 add 指令加一条 adc（带进位加法）指令，完全没有分支。我们的手写实现也要达到这个水准。

_addcarry_u64 接受两个 64 位操作数、一个输入进位（0 或 1），并通过输出参数返回结果位和一个新的进位。第一次调用时输入进位为 0，随后将第一次的输出进位作为第二次的输入进位，形成完整的进位链。

inline u128 operator+(u128 a, u128 b) {
    u128 r;
    unsigned char c = _addcarry_u64(0, a.low, b.low, &r.low);
    (void)_addcarry_u64(c, a.high, b.high, &r.high);
    return r;
}

查看编译后的汇编，生成的指令正是期望的 add 加上 adc，调用约定产生的 mov 指令属于参数传递的噪音，核心逻辑与编译器生成完全一致。减法同理，只是借位方向相反：sub 后接 sbb（带借位减法）。

inline u128 operator-(u128 a, u128 b) {
    u128 r;
    unsigned char c = _subborrow_u64(0, a.low, b.low, &r.low);
    (void)_subborrow_u64(c, a.high, b.high, &r.high);
    return r;
}

这里选择 intrinsics 而非内联汇编的原因是编译器能够理解 intrinsics 的语义，从而进行指令调度、死代码消除和常量折叠。内联汇编是一个黑盒，编译器无法分析其副作用，往往会导致优化被抑制。

乘法：代数分解与宽乘指令

乘法的复杂性在于 128 位乘以 128 位会产生 256 位结果，而我们只需要低 128 位。现代 x64 处理器通过 BMI2 指令集提供了 _mulx_u64，它执行 64 位乘以 64 位并返回 128 位结果，高低位分别通过输出参数和返回值传递。与 mul 指令不同，mulx 不影响标志位，可以自由与其他指令混合使用。

将 (a.low + 2^64 * a.high) * (b.low + 2^64 * b.high) 展开后，四项乘积中只有前三项影响低 128 位：低 64 位乘积提供低位和高位，两项交叉乘积只贡献高位，高位乘积完全超出范围可直接丢弃。

inline u128 operator*(u128 a, u128 b) {
    u128 r;
    u64 p0_hi;
    r.low = _mulx_u64(a.low, b.low, &p0_hi);
    
    u64 t1_hi;
    u64 t1_lo = _mulx_u64(a.low, b.high, &t1_hi);
    
    u64 t2_hi;
    u64 t2_lo = _mulx_u64(a.high, b.low, &t2_hi);
    
    r.high = p0_hi + t1_lo + t2_lo;
    return r;
}

注意这里不需要处理向更高位的进位，因为任何超出 127 位的进位都会被自然丢弃。编译器生成的代码使用了 mulx 加上两条 imul（用于交叉项）和三条 add 指令，与 __uint128_t 的乘法在指令数量上完全一致。

比较运算：借位标志的分支消除

朴素的比较实现是先比较高位，高位相等再比较低位。这会产生分支预测失败的开销，而且生成的代码较为冗长。一种更优的策略是利用减法产生的借位标志：无符号比较 a < b 等价于检查 a - b 是否产生借位。

inline bool operator<(u128 a, u128 b) {
    u64 dont_care;
    unsigned char borrow = _subborrow_u64(0, a.low, b.low, &dont_care);
    borrow = _subborrow_u64(borrow, a.high, b.high, &dont_care);
    return borrow != 0;
}

生成的汇编仅包含一条 cmp、一条 sbb 和一条 setb（设置字节，如果借位则置位），没有任何分支。这种模式对于循环内部的比较操作特别有价值，因为分支预测失败在热路径上的代价可能被放大数十倍。

除法：性能关键路径

如果说加法、减法和乘法都能在几条指令内完成，除法则完全是另一个故事。x86-64 没有 128 位除法指令，编译器只能生成对 __udivmodti4 库函数的调用。这个函数通常实现为移位减法算法，最坏情况下需要 128 次迭代，每一次迭代都涉及多个寄存器的移位和比较操作。

在 Intel Xeon W-2135 上的基准测试显示，未优化的 128 位除以 64 位除法耗时约 169 纳秒，而 128 位除以 128 位也要 13.7 纳秒。这与单条 64 位除法指令约 20 纳秒的延迟形成了鲜明对比 ——128 位除法的开销是原生的 8 倍以上。

一种有效的优化策略是利用 x64 的 divq 指令。它执行 128 位除以 64 位，商放在 rax，余数放在 rdx，被除数由 rdx:rax 组合提供。关键约束是：当被除数的高 64 位小于除数时，商必然能装入 64 位，此时 divq 是安全的。基于这一观察，我们可以为 128 除以 64 的场景设计快速路径。

#if defined(__x86_64__)
inline uint64_t divide_128_by_64(uint64_t high, uint64_t low,
                                  uint64_t divisor, uint64_t* remainder) {
    uint64_t result;
    __asm__("divq %[v]"
            : "=a"(result), "=d"(*remainder)
            : [v] "r"(divisor), "a"(low), "d"(high));
    return result;
}
#endif

在 128 位除以 128 位的场景中，如果除数的高 64 位为零（实际上是个 64 位除数），可以直接调用上述快速路径。优化后的性能从 169 纳秒降至 26 纳秒，提升约 6 倍。对于真正的 128 除以 128 场景，也可以采用类似的分解策略：先除高 64 位得到商的高半部，再用余数与低 64 位组合后除以除数得到商的低半部。这种两次 128 除以 64 的方案，在很多情况下比通用的移位减法更快。

需要注意的是，内联汇编的使用需要格外谨慎。编译器无法推断 divq 的副作用，因此需要确保在调用前后没有依赖标志位的操作，且函数调用的开销在热路径上是可以接受的。

性能对比与工程建议

手写 u128 的核心目标是代码生成与 __uint128_t 等效，同时保留定制化的能力。实测表明，在 -O2 或 -O3 优化级别下，GCC 和 Clang 为手写运算符生成的指令与内置类型的指令在数量和类型上几乎一致。唯一的例外是除法：内置类型仍然依赖运行时库的通用实现，而手写实现可以注入平台特定的优化路径。

工程实践中有几个关键建议。首先是条件编译：MSVC 不支持 _mulx_u64，需要使用 _umul128，平台检测宏可以优雅处理这种差异。其次是内联建议：将所有运算符声明为 inline 或 constexpr，确保编译器能够在调用点完全展开，避免函数调用的固定开销。第三是特殊函数：对于 abs、clz、popcount 等位操作，直接复用编译器内置函数即可，它们通常有对应的单指令实现。

手写 u128 是一个通往更宽整数类型的起点。从双 limb 的模式出发，将相同的技术扩展到 192 位或 256 位只需增加指令数量，核心逻辑完全一致。更重要的是，这种实现展示了如何将高级语言与底层硬件特性结合，在保持代码可读性的同时榨取每一纳秒的性能。

参考资料

  • Solidean, "Building Your Own Efficient uint128 in C++" (2026)
  • Dan Larkin, "Optimizing 128-bit Division" (2020)

systems