如何在无128位整数支持且不使用除法时计算64位无符号整数乘积除以2^64的商

相信不少人在Visual Studio这类不支持内置128位整数的环境里，都遇到过这个需求：要算两个64位无符号数相乘后除以2^64的商，还得避开耗时的除法，只用加减、乘法和位运算。我之前也折腾过这个问题，最终用分治法找到了完美的解决方案，全程不需要依赖128位类型。

首先明确一个关键点：对于无符号整数来说，(a * b) / 2^64 的商，其实就是它们乘积的高64位——因为两个64位无符号数相乘会得到128位结果，除以2^64相当于直接丢弃低64位，剩下的就是我们要的商。

原理推导 #

我们可以把每个64位无符号数拆成高32位和低32位的组合：

a = a_high * 2^32 + a_low
b = b_high * 2^32 + b_low

这里的 a_high, a_low, b_high, b_low 都是32位无符号整数，拆分起来很简单，用右移和强制类型转换就能搞定。

把乘积展开后会得到：

a * b = (a_high*b_high) * 2^64 + (a_high*b_low + a_low*b_high) * 2^32 + a_low*b_low

我们需要的是除以2^{64的商，也就是把上面式子中低于2}64的部分处理后，加到高64位的基础上。具体来说：

1. a_low*b_low 是64位结果，它的高32位会进位到2^32的层级；
2. a_high*b_low + a_low*b_high 也是64位结果，加上刚才的进位后，它的高32位会进位到2^64的层级；
3. 最后加上最顶层的 a_high*b_high，就是我们要的商。

具体实现（Visual Studio C++） #

#include <cstdint>

uint64_t mul_div_u64(uint64_t a, uint64_t b) {
    // 拆分64位数为高低32位
    const uint32_t a_low = static_cast<uint32_t>(a);
    const uint32_t a_high = static_cast<uint32_t>(a >> 32);
    const uint32_t b_low = static_cast<uint32_t>(b);
    const uint32_t b_high = static_cast<uint32_t>(b >> 32);

    // 计算四个32位乘32位的结果（都是64位）
    const uint64_t low_low = static_cast<uint64_t>(a_low) * b_low;
    const uint64_t low_high = static_cast<uint64_t>(a_low) * b_high;
    const uint64_t high_low = static_cast<uint64_t>(a_high) * b_low;
    const uint64_t high_high = static_cast<uint64_t>(a_high) * b_high;

    // 计算中间层的总和：交叉乘积之和 + 低低乘积的高32位
    const uint64_t middle_sum = low_high + high_low + (low_low >> 32);

    // 最终商 = 高高乘积 + 中间层总和的高32位
    return high_high + (middle_sum >> 32);
}

为什么这个方法靠谱？ #

• 兼容性拉满：所有运算都基于64位及以下的无符号整数，完全适配VS这类不支持128位的环境；
• 性能达标：全程只用了乘法、加法、右移（位运算），没有除法，完全符合你对低耗时的要求；
• 无溢出隐患：无符号整数的溢出会自动按模2^n处理，刚好契合我们需要的进位逻辑，不需要额外写溢出判断代码。

测试用例验证 #

举个极端例子测试：

#include <iostream>
#include <cstdint>

int main() {
    // 两个最大的64位无符号数相乘
    uint64_t a = UINT64_MAX;
    uint64_t b = UINT64_MAX;
    uint64_t result = mul_div_u64(a, b);
    // 预期结果：UINT64_MAX - 1 = 0xFFFFFFFFFFFFFFFE
    std::cout << std::hex << result << std::endl;
    return 0;
}

运行后输出的结果会和预期一致，证明这个实现是正确的。

内容的提问来源于stack exchange，提问作者square1001